14
\$\begingroup\$

Challenge

Given a non-negative integer, output whether it is possible for two dates (of the Gregorian calendar) differing by exactly that many years to share a day of the week. A year is assumed to be a leap year either if it is divisible by 4 but not by 100, or if it is divisible by 400.

Output may be:

  • falsey/truthy (in either orientation)
  • any two distinct values
  • one distinct value and one being anything else
  • by program return code
  • by success/error
  • by any other reasonable means - just ask if you suspect it may be controversial

But not by two non-distinct sets of values, except for falsey/truthy (as this would allow a no-op!)

Detail

This is whether the input is a member of OEIS sequence A230995.

Members:

0, 5, 6, 7, 11, 12, 17, 18, 22, 23, 28, 29, 33, 34, 35, 39, 40, 45, 46, 50, 51, 56, 57, 61, 62, 63, 67, 68, 73, 74, 78, 79, 84, 85, 89, 90, 91, 95, 96, 101, 102, 106, 107, 108, 112, 113, 114, 117, 118, 119, 123, 124, 125, 129, 130, 131, 134, 135, 136, 140, 141, 142, 145, 146, 147, 151, 152, 153, 157, 158, 159, 162, 163, 164, 168, 169, 170, 173, 174, 175, 179, 180, 181, 185, 186, 187, 190, 191, 192, 196, 197, 198, 202, 203, 204, 208, 209, 210, 213, 214, 215, 219, 220, 221, 225, 226, 227, 230, 231, 232, 236, 237, 238, 241, 242, 243, 247, 248, 249, 253, 254, 255, 258, 259, 260, 264, 265, 266, 269, 270, 271, 275, 276, 277, 281, 282, 283, 286, 287, 288, 292, 293, 294, 298, 299, 304, 305, 309, 310, 311, 315, 316, 321, 322, 326, 327, 332, 333, 337, 338, 339, 343, 344, 349, 350, 354, 355, 360, 361, 365, 366, 367, 371, 372, 377, 378, 382, 383, 388, 389, 393, 394, 395
plus
400, 405, 406, 407, 411, ...

Non-members:

1, 2, 3, 4, 8, 9, 10, 13, 14, 15, 16, 19, 20, 21, 24, 25, 26, 27, 30, 31, 32, 36, 37, 38, 41, 42, 43, 44, 47, 48, 49, 52, 53, 54, 55, 58, 59, 60, 64, 65, 66, 69, 70, 71, 72, 75, 76, 77, 80, 81, 82, 83, 86, 87, 88, 92, 93, 94, 97, 98, 99, 100, 103, 104, 105, 109, 110, 111, 115, 116, 120, 121, 122, 126, 127, 128, 132, 133, 137, 138, 139, 143, 144, 148, 149, 150, 154, 155, 156, 160, 161, 165, 166, 167, 171, 172, 176, 177, 178, 182, 183, 184, 188, 189, 193, 194, 195, 199, 200, 201, 205, 206, 207, 211, 212, 216, 217, 218, 222, 223, 224, 228, 229, 233, 234, 235, 239, 240, 244, 245, 246, 250, 251, 252, 256, 257, 261, 262, 263, 267, 268, 272, 273, 274, 278, 279, 280, 284, 285, 289, 290, 291, 295, 296, 297, 300, 301, 302, 303, 306, 307, 308, 312, 313, 314, 317, 318, 319, 320, 323, 324, 325, 328, 329, 330, 331, 334, 335, 336, 340, 341, 342, 345, 346, 347, 348, 351, 352, 353, 356, 357, 358, 359, 362, 363, 364, 368, 369, 370, 373, 374, 375, 376, 379, 380, 381, 384, 385, 386, 387, 390, 391, 392, 396, 397, 398, 399
plus
401, 402, 403, 404, 408, ...

This is so the shortest answer in each language wins!

\$\endgroup\$
  • \$\begingroup\$ Can output be: program ends (within less than 30 seconds) if input belongs to the sequence, or runs indefinitely (infinite loop) otherwise? \$\endgroup\$ – Luis Mendo Dec 31 '17 at 4:35
  • \$\begingroup\$ @LuisMendo I'll allow a program that does that so long as it is accompanied with a program that provides the time limit (so one may acquire it prior for one's hardware). It is indeed controversial though :) \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 4:57
  • \$\begingroup\$ In which situation is a number divisible by 400 but is not divisible by 100? \$\endgroup\$ – ATaco Dec 31 '17 at 5:20
  • \$\begingroup\$ @ATaco In none. The exception to the every fourth year rule are years that are divisible by 4 and 100, but not by 400. \$\endgroup\$ – Dennis Dec 31 '17 at 5:27
  • \$\begingroup\$ @ATaco maybe the wording is clearer now \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 5:38
4
\$\begingroup\$

MATL, 17 bytes

`0Gv@+5:YcYO8XOda

The program halts if the input belongs to the sequence, or runs indefinitely (infinite loop) otherwise.

Let n be the input. The code executes a loop that tests years 1 and 1+n; then 2 and 2+n; ... until a matching day of the week is found. If no matching exists the loop runs indefinitely.

The membership function for n is periodic with period 400. Therefore, at most 400 iterations are needed if n belongs to the sequence. This requires less than 20 seconds in Try It Online. As a proof of this upper bound, here's a modified program that limits the number of iterations to 400 (by adding @401<* at the end). Note also that this bound is loose, and a few seconds usually suffice.

Try it online!

Explanation

`           % Do...while
  0Gv       %   Push column vector [0; n], where n is the input number
  @+        %   Add k, element-wise. Gives [k; k+n]
  5:        %   Push row vector [1, 2, 3, 4, 5]
  Yc        %   Horizontal "string" concatenation: gives the 2×6 matrix
            %   [k, 1, 2, 3, 4, 5; k+n, 1, 2, 3, 4, 5]. The 6 columns
            %   represent year, month, day, hour, minute, second
  YO        %   Convert each row to serial date number. Gives a column
            %   vector of length 2
  8XO       %   Convert each date number to date string with format 8,
            %   which is weekday in three letters ('Mon', 'Tue', etc).
            %   This gives a 2×3 char matrix such as ['Wed';'Fri']
  d         %   Difference (of codepoints) along each column. Gives a
            %   row vector of length 3
  a         %   True if some element is nonzero, or false otherwise
            % End (implicit). The loop proceeds with the next iteration
            % if the top of the stack is true

Old version, 24 bytes

400:"0G&v@+5:YcYO8XOdavA

Output is 0 if the input belongs to the sequence, or 1 otherwise.

Try it online!

Explanation

400         % Push row vector [1, 2, ..., 400]
"           % For each k in that array
  0G&v      %   Push column vector [0; n], where n is the input number
  @+        %   Add k, element-wise. Gives [k; k+n]
  5:        %   Push row vector [1, 2, 3, 4, 5]
  Yc        %   Horizontal "string" concatenation: gives the 2×6 matrix
            %   [k, 1, 2, 3, 4, 5; k+n, 1, 2, 3, 4, 5]. The 6 columns
            %   represent year, month, day, hour, minute, second
  YO        %   Convert each row to serial date number. Gives a column
            %   vector of length 2
  8XO       %   Convert each date number to date string with format 8,
            %   which is weekday in three letters ('Mon', 'Tue', etc).
            %   This gives a 2×3 char matrix such as ['Wed';'Fri']
  d         %   Difference (of codepoints) along each column. Gives a
            %   row vector of length 3
  a         %   True if some element is nonzero, or false otherwise
  v         %   Concatenate vertically with previous results
  A         %   True if all results so far are true
            % End (implicit). Display (implicit)
\$\endgroup\$
  • \$\begingroup\$ Seems good, my request was really that I'd like to know the worst case input, or have a program which forces the 400 iterations -- that way one could get an upper bound wherever one chooses to run it. (BTW I think the infinite loop is, in practice, ended by an out of bounds error.) \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 18:35
  • 1
    \$\begingroup\$ @JonathanAllan Thanks. I see. I've added a modified program that limits the number of iterations to 400. It takes about 14 seconds, so I'm using 20 seconds as upper bound \$\endgroup\$ – Luis Mendo Dec 31 '17 at 18:59
5
\$\begingroup\$

Python 2, 58 bytes

u=-abs(200-input()%400)-4
print u/100+5>(u-8)*5/4%7>u%4/-3

Try it online!

A direct formula.

\$\endgroup\$
  • \$\begingroup\$ This is nice. I believe you can save 2 bytes with 5*u/4%7-3 instead of (u-8)*5/4%7. \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 3:35
  • \$\begingroup\$ Save 2 more by using the success/error option with 1/(...) instead of print .... \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 4:01
5
\$\begingroup\$

Jelly, 20 18 bytes

99R4ḍj`‘ṡ%4ȷ$S€P7ḍ

Outputs 1 for members, 0 for non-members.

Try it online!

How it works

99R4ḍj`‘ṡ%4ȷ$S€P7ḍ  Main link. Argument: n

99                  Set the return value to 99.
  R                 Range; yield [01, .., 99].
   4ḍ               Test each element in the range for divisibility by 4.
     j`             Join the resulting array, using itself as separator.
                    The result is an array of 9801 Booleans indicating whether the
                    years they represent have leap days.
       ‘            Increment the results, yielding 1 = 365 (mod 7) for non-leap
                    years, 2 = 366 (mod 7) for leap years.
         %4ȷ$       Compute n % 4000.
        ṡ           Take all slices of length n % 4000 of the result to the left.
             S€     Take the sum of each slice.
               P    Take the product of the sums.
                7ḍ  Test for divisibility by 7.
\$\endgroup\$
2
\$\begingroup\$

Python 2, 83 bytes

lambda i:all(c(y)-c(y-i)for y in range(401))
c=lambda n:(5*(n/4)+n%4-n/100+n/400)%7

Try it online!

Direct port of my Haskell answer.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 76 bytes

-35 bytes thanks to Jonathan Allan. -2 bytes thanks to Lynn.

f i=or[c y==c$y+i|y<-[0..400]]
c n=(5*n#4+n%4-n#100+n#400)%7
(%)=mod
(#)=div

Try it online!

Using the OEIS PARI program's algorithm.

\$\endgroup\$
  • 1
    \$\begingroup\$ 5*(n#4) can be 5*n#4 also! \$\endgroup\$ – Lynn Dec 30 '17 at 22:35
1
\$\begingroup\$

Pyth, 32 bytes

iI7*FsM.:hMs.iKiIL4S99*98]K%Q400

Try it here! (Click "Switch to Test Suite" to verify more test cases at once)

How?

Uses a cool trick I just added to the "Tips for golfing in Pyth" thread.

iI7*FsM.:hMs.iKiIL4S99*98]K%Q400 | Full program. Reads from STDIN, outputs to STDOUT.

                   S99           | Generate the integers in 1 ... 99.
                 L               | For each integer N in that list...
               iI 4              | Check if 4 is invariant over applying GCD with N.
                                 | This is equivalent to checking if 4 | N.
              K                  | Store the result in a variable K.
            .i         *98]K     | And interleave K with the elements of K wrapped
                                 | into a list and repeated 98 times.
           s                     | Flatten.
         hM                      | Increment.
       .:                        | And generate all the substrings...
                           %Q400 | Of length  % 400.
     sM                          | Sum each.
   *F                            | And apply folded product.
iI7                              | Check if 7 is invariant when applied GCD with the
                                 | product (basically check whether 7 | product).
                                 | Implicitly output the appropriate boolean value.
\$\endgroup\$
0
\$\begingroup\$

Python 3, 110 107 bytes

from datetime import*
lambda n,d=date:0in[d(i,1,1).weekday()-d(i+n%400,1,1).weekday()for i in range(1,999)]

Try it online!

-3 bytes thanks to Mr. Xcoder.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.