Sunday, March 17, 2013

[dmvlfjan] Modern computus

Invent a holiday which is difficult (but possible) to calculate the date each year, a modern version of the herculean effort formerly needed to compute the date of Easter.  One idea:

LPF(x) = Largest Prime Factor of x
d = LPF(2^(year-1024)-1) mod (number of days in February)
Cunningham Day is February (d+1)

We have 2 years to fully factor the current third hole 2^991-1 of the Cunningham Project, leaving unknown the Cunningham dates for 1953 and 1971.  And the next hole after that is 2031.  Is this too easy?  Factoring is subexponential but Moore's Law is less than 1 bit per year.

Maybe simply 2^year-1 leaving many years with unknown dates.  February suggests that the month number could be the base of the exponentiation.  We could also make things tougher by using a formula that requires all factorizations less than the current year; there can be no holes.

Maybe something involving factorials, which grow faster than powers of two.  Factor 1+(year-1900)!  This year is a 613 bit problem or 185 digits, but solved at http://www.asahi-net.or.jp/~kc2h-msm/mathland/matha1/index.htm also http://www.leyland.vispa.com/numth/factorization/main.htm .  2014 and 2015 are unsolved according to that page (and 2003 and 2009), but within the range of large-scale GNFS.  For (y-1900)!-1, 2013 is the first hole.  I'm a little suspicious that the last update was 2006. Little Factorial Day occurs January through June, Big Factorial Day July through December.

Maybe Fibonacci numbers, which grow slower than powers of 2.  The first unfactored hole is 1153.

Inspired by Easter could be, and arguably should be, more difficult to compute if combining the Gregorian cycle and Hebrew molad.  We could go further by incorporating the relatively prime Hindu Surya calendar.

No comments :