Match The Years (Posted on 2006-01-22)

	Submitted by K Sengupta
Rating: 3.2000 (5 votes)
Solution:	(Hide)
SOLUTION SUMMARY The required number of ‘Matched’ years between 1960 A.D. and 2560 A.D. (both years inclusive) is 84. ANALYTIC SOLUTION (Submitted By Charlie) 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 3 remainder: 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 6 years of this cycle have: dow: 4 5 6 0 2 3 4 5 0 1 2 3 5 6 0 1 remainder: 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 2500 (a 200-year span as 2400 is indeed a leap year) are done similarly. Year 2300 has dow = 1 and 2301 has dow = 2, and 2301 mod 7 = 5, and the span includes 7 28-year cycles plus 4 extra years: dow: 2 3 4 5 remainder: 5 6 0 1 so no matches are in the extra years, but the 7 28-year cycles give 28 matches, which is then the total for years 2301 through 2500. Finally, we have 2501 through 2560. These 60 years are two 28-year cycles plus four more years. As 2500 is non-leap, 2501 has dow one higher than that of 2500 (remember that extra years have matching characteristics at the front or at the end of any span): dow: 6 0 1 2 remainder: 2 3 4 5 for no matches, but the two 28-year cycles give 8 matches. So we have 20 + 16 + 12 + 28 + 8 = 84 as the final answer. COMPUTER SOLUTION (Submitted By Charlie ) We have 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. ANOTHER COMPUTER SOLUTION (Submitted By Richard ) The following bc program define match(n) { auto i,d,y,c scale=0 d=5;y=1959;c=0 for(i=1; i<=n; ++i) { d=d+1;y=y+1 if(y%4==0)d=d+1 if(y%100==0) d=d-1 if(y%400==0) d=d+1 d=d%7 if(i%7==d) {c=c+1; print y+1," ",} } return(c) } produced match(600) 1965 1966 1967 1968 1993 1994 1995 1996 2021 2022 2023 2024 2049 2050 2051 2052 2077 2078 2079 2080 2109 2110 2111 2112 2137 2138 2139 2140 2165 2166 2167 2168 2193 2194 2195 2196 2225 2226 2227 2228 2253 2254 2255 2256 2281 2282 2283 2284 2313 2314 2315 2316 2341 2342 2343 2344 2369 2370 2371 2372 2397 2398 2399 2400 2425 2426 2427 2428 2453 2454 2455 2456 2481 2482 2483 2484 2513 2514 2515 2516 2541 2542 2543 2544 84

	Subject	Author	Date
	re: A solution	Charlie	2006-01-24 09:42:48
	A solution	Dej Mar	2006-01-23 18:50:57
	re(3): Analytical solution	Richard	2006-01-23 15:35:15
	re(2): Analytical solution	Tristan	2006-01-23 15:08:53
	re: Analytic solution with computer verification	Charlie	2006-01-23 08:24:42
	Another Computer Program Solution	Richard	2006-01-22 19:28:32
	re: 1776	Charlie	2006-01-22 17:54:49
	re: Analytical solution -- the x-values	Charlie	2006-01-22 17:13:36
	Analytic solution with computer verification	Charlie	2006-01-22 16:28:11
	re: Analytical solution	Richard	2006-01-22 16:08:07
	Analytical solution	Tristan	2006-01-22 15:43:38
	1776	Justin	2006-01-22 11:57:55
	Why not 1960 to 2571 or 1987 to 2599?	Justin	2006-01-22 11:34:09
	solution	Justin	2006-01-22 11:25:40
	re: computer solution achieved (not posted here)	HarryHotspur	2006-01-22 11:20:58
	computer solution achieved (not posted here)	Justin	2006-01-22 10:58:33