All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Match The Years (Posted on 2006-01-22)
The days of the week (d.o.w) which are Sunday, Monday, Tuesday,Wednesday,Thursday,Friday and Saturday (in that order) are respectively denoted by the numbers 0,1,2,3,4,5 and 6 . Any given year commencing with a particular d.o.w is assigned that value corresponding to that d.o.w. For example, the value ‘0’ would be assigned to a year commencing with a Sunday.

# A year is defined as ‘Matched’ if the remainder obtained, when the year is divided by 7, corresponds precisely with the value assigned to that particular year. For example, 2003 A.D. is NOT A Matched year since 2003 leaves a remainder of 1 upon division by 7 but January 1,2003 occurred on a Wednesday which is denoted by 3.

Determine the total number of ‘Matched’ years between 1960 A.D. and 2560 A.D.(both years inclusive) in accordance with the Western (Gregorian) Calendar System.

 See The Solution Submitted by K Sengupta Rating: 2.7500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Analytic solution with computer verification | Comment 8 of 16 |

For any series of years in which there is a leap year every four years, there is a 28-year cycle that repeats, as the 4-year cycle of leap years is relatively prime to the 7 that is the number of days in the week.  So during this period each beginning day of the week and each year remainder (and their combinations) are represented equally, so four out of the 28 are 'matched'.  A first approximation to an answer would be (2560-1959) * 4 / 28 ~= 86. However, the fractional cycles need be accounted for.

The 4-year cycle of leap years is interrupted in years ending in 00, but are not divisible by 400. In the time period referenced, these are 2100, 2200, 2300 and 2500.  Each of these is a common, rather than leap, year, even though divisible by 4.

From 1960 through 2100 inclusive, is 141 years, or one more than 5 * 28.  The five 28-year cycles account for 5 * 4 = 20 matches. As the 1960 and 2100 are both at the same position in the 28-year cycle, they are either both matches or both non-matches, so either one can be considered as the extra year (the break in the cycle comes in February, 2100, so Jan 1 is not affected). We'll use 2100: it is 97 years after 2003, or 24 4-year cycles plus 1 year. 24 4-year cycles advance the dow by 24*5 mod 7 = 1. The extra year, being non-leap (Feb. 2003 or Feb 2099) advances one more day, making a total of 2 days. So Jan 1, 2100 is a Friday (dow=5). But 2100 mod 7 = 0, so there is no match. Therefore 1960 through 2100 accounts for just the 20 matches of its five full 28-year cycles.

Then comes 2101 through 2200. Year 2101's dow is 1 past that of 2100 as the latter is non-leap. That makes its dow=6. Its remainder mod 7 is 1. One hundred years is 3*28 + 16. The three 28-year cycles account for 3*4=12 match years. We need the extra 16, which might as well be the first 16:

`dow:       6 0 1 2 4 5 6 0 2 3 4 5 0 1 2 3remainder: 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2`

Thus these years account for four matches, making the total for 2101 through 2200 equal to 16 matches.

Then come 2201 through 2300. Again there are three 28-year cycles accounting for 12 match years, and again we do the first 16 as extra.  As the last of the extra 16 years above, we had calculated dow = 3 for year 2116. So year 2200 also has dow = 3, and 2201 has dow = 4, since 2201 is not a leap year. Also, 2201 mod 7 is 3, so the extra 16 years of this cycle have:

`dow:       4 5 6 0 2 3 4 5 0 1 2 3 5 6 0 1remainder: 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4`

This yields no matches, so 2201 through 2300 account for just 12 match years.

Then years 2301 through 2400 are done similarly. Year 2300 has dow = 1 and 2301 has dow = 2, and 2301 mod 7 = 5:

`dow:       2 3 4 5 0 1 2 3 5 6 0 1 3 4 5 6remainder: 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6`

yielding four more match years, giving a total of 16 for years 2301 through 2400.

You can see that the pattern started with a dow two less than for the preceding century and a remainder two higher.  However, 2400 is a leap year (in contrast to 2300), so we advance dow by one, yielding a net decrease of only 1:

`dow:       1 2 3 4 6 0 1 2 4 5 6 0 2 3 4 5remainder: 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1`

yielding no matches leaving only the 12 from the three 28-year cycles for the period 2401 through 2500.

Finally, we have 2501 through 2560. These 60 years are two 28-year cycles plus four more years.  The dow for the extra years again begins 2 lower than the previous set of extras, as 2500 reverts to non-leap, giving extra four years having:

`dow:       6 0 1 2remainder: 2 3 4 5`

for no matches, but the two 28-year cycles give 8 matches.

So we have 20 + 16 + 12 + 16 + 12 + 8 = 84 as the final answer.

This is confirmed by the following program:

CLS
FOR y = 1960 TO 2560

mo = 1: da = 1: ye = y
GOSUB greg.to.jd
dow = (jd + 1) MOD 7
PRINT y; dow; y MOD 7

IF dow = y MOD 7 THEN ct = ct + 1

NEXT y
PRINT ct

END

greg.to.jd:
10100 REM :greg mo/da/ye --> jd at noon
10110 GOSUB jul.to.jd
10120 jd = jd + 2 - INT(cw(1) / 100) + INT(cw(1) / 400)
10130 RETURN

jul.to.jd:
10150 REM :jul mo/da/ye --> jd at noon
10160 cw(0) = mo: cw(1) = ye: IF mo < 3 THEN cw(0) = mo + 12: cw(1) = ye - 1
10170 jd = INT(365.25 * cw(1)) + INT(30.61 * (cw(0) + 1)) + da + 1720995!
10180 RETURN

The line numbers are left over from an ancient version of Basic. Julian day numbers are used in astronomy and count days from 4713 BC.

 Posted by Charlie on 2006-01-22 16:28:11

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: