Keith F. Lynch wrote:

But there's a world about a trillion light years away that by a remarkable coincidence has a calendar almost identical to ours. The one difference is their leap year rules. As with us, their February starts with 28 days. But it gains a day for every odd number that the year is divisible by, and loses a day for every even number that the year is divisible by. Divisors include 1 and the number itself. ... Eventually, they have a crisis. For the first time, February will have a negative length, and there's no provision for dealing with that. Borrow a day from January or March? The puzzle is, in what year does this first happen? Or will this actually never happen?

February in year n has 28 + (1-k)/(1+k).d(n) days, where d(n) is the number of divisors of n and k is the number of times 2 divides n. Equivalently, in year 2^k.m (where m is odd) the length is 28 + (1-k)d(m). In particular, in year 2^30 the number of days will be -1, but we can do better; for instance, in year 2^2.3.5.7.11.13=60060 the number of days will be 28 - 2^5 = -4. The first year with a negative number of days in February is year 2880 = 2^6.3^2.5, with 28-5*3*2=-2 days. If the number of 2s, 3s, 5s, ... dividing n = a, b, c, ... then the number of days we subtract is (a-1)(b+1)(c+1)...; so finding the first year with negative length means finding a,b,c,... to minimize (log 2) a + (log 3) b + ... subject to (a-1)(b+1)(c+1)... >= 366. Super-crudely it seems we want a,b,c,... roughly proportional to 1/log(2) etc., and a bit of fiddling suggests that maybe year 2^11.3^7.5^4 = 2799360000 is the first with negative total length; but I haven't actually checked that nothing earlier works.

Finally, and most interestingly, what is the average length of a year in their calendar? If possible, express it in closed form rather than as a numerical estimate.

Write f(n) for the deficit in the length of February. Then f(2^k.m) = (k-1).d(m) where d is the divisor function. So the sum of f(n) for n <= N is sum {k} sum {n odd, n <= N/2^k} (k-1) d(n) which equals sum {k} (k-1) sum {n odd, n <= N/2^k) d(n). That inner sum is, I think, 1/4 N/2^k log N/2^k + lower-order terms (it's the number of (odd,odd) lattice points below xy=N, which ought to be about 1/4 the total number of lattice points below xy=N, which is famously about N log N; but maybe I need to be more careful about exactly what happens in the tails). In which case our sum is (or is it?) about sum {k} (k-1) N/2^k log N - sum {k} (k-1) N/2^k log 2^k = N log N sum {k} (k-1)/2^k - N sum {k} k(k-1)/2^k log 2 which would be obviously dominated by the first term except that it happens that sum {k} (k-1)/2^k = 0 so we need to be more careful about those lower-order terms. OK. So to count the number of odd lattice points below xy=N, we'll first count the number with x <= sqrt(N). That's sum {x odd, x <= sqrt(N)} floor((N/x-1)/2) = sum {x odd, x <= sqrt(N)} (N/x-1)/2 + O(sqrt(N)) = sum {x odd, x <= sqrt(N)} N/2x + O(sqrt(N)) = N/2 (1 + 1/3 + ... + 1/sqrt(N)ish) + O(sqrt(N)) = N/2 (H(sqrt(N))-(1/2)H(sqrt(N)/2)) + O(sqrt(N)) = N/2 (log(sqrt(N))+g - (1/2)[log(sqrt(N)/2)+g]) + O(sqrt(N)) = N/8 log N + N/4 g + O(sqrt(N)) where g is Euler's constant. Now the number we want is twice this minus the doubly-counted odd lattice points in the square below (sqrt(N),sqrt(N)); that is, N/4 log N + N/2 g - N/4 = N/4 (log N + 2g - 1) + O(sqrt(N)) which is indeed exactly 1/4 what you get when you count all the lattice points instead of only the odd ones. And now the total deficit for years <= N is sum {k} (k-1) sum {n odd, n <= N/2^k) d(n) where the inner sum is given by the calculation we just did; so the total deficit is sum {k} (k-1) (N/2^k)/4 (log (N/2^k) + 2g - 1) plus terms that I hope really are lower-order; that's sum {k} (k-1) (N/2^k)/4 (log N - k log 2 + 2g - 1) = 1/4 sum {k} (k-1)/2^k N (log N - k log 2 + 2g - 1) and now, because sum {k} (k-1)/2^k = 0, everything goes away except for 1/4 sum {k} (k-1)/2^k N . - k log 2 = - N/4 log 2 sum {k} k(k-1)/2^k so that the average year length is 365 + 1/4 log 2 sum {k} k(k-1)/2^k which I think equals 365 + log 2. I estimate an 80% probability that there's at least one mistake in the calculations above, but I'm pretty sure it's morally right :-). -- g