A leap year scheme based on binary expansions

Yesterday I wrote about leap day, and how a different scheme of determining which years are leap years could make calendrical calculation easier. In particular, the number of days in a year is very nearly 365+31/128; how can we pick 31 years out of every 128 to be leap years? (As was pointed out in the comments, 128 is a power of two, which is what makes this whole post work.)

The answer is obvious -- take every fourth year, except don't take years divisible by 128.

But then I asked -- what if we needed to take 33 years out of every 128? We clearly should take every fourth year... and then one more out of every 128. But which one?

I'm implicitly using the fact 31/128 = 1/4 - 1/128 and 33/128 = 1/4 + 1/128. But we can also write:

33/128 = 1/2 - 1/4 + 1/128.

Why would I do this? Because it gives a very good scheme for assigning 33 leap years out of every 128. Include in the set of leap years all years which are even, but not those that are divisble by 4, but do include those which are divisible by 128. So in every 128-year period we include the year 0, and the years 2, 6, 10, ..., 126.

But there's a nicer way to express that. Look at the binary expansion of such a year. Either it ends in exactly one 0 (it's 2 more than a multiple of 4) or it ends in at least seven 0s (it's a multiple of 128). It turns out that for any fraction of the form m/2ⁿ, where 0 ≤ m < 2ⁿ, we can write m/2ⁿ as an alternating sum of powers of 1/2. For example, consider

59/128 = 1/4 + 1/8 + 1/16 + 1/64 + 1/128.

where that's just the ordinary binary expansion. We can group the consecutive powers of 2 in the binary expansion together to get

59/128 = (1/4 + 1/8 + 1/16) + (1/64 + 1/128)

and then each sum of consecutive powers can be written as a difference, giving

59/128 = 1/2 - 1/16 + 1/32 - 1/128.

So let's say we want 59 leap years out of every 128. We include all the even years, but we don't include those that are divisible by 16, but we do include those that are divisible by 32, but then we don't include those that are divisible by 128.

It sounds complicated -- but there's a better way to say it. If you think about it, the rule I just gave says that the binary expansion of a leap year must end in 1, 2, 3, 5, or 6 zeroes. Write 59/128 = .0111011₂. Now, there are 1s in exactly the 2nd, 3rd, 4th, 6th, and 7th places after the decimal point. That's not a coincidence. The proportion 1/2ⁿ⁺¹ of integers will have binary expansions ending in exactly n zeroes. In general, if we want m/2ⁿ of our years to be leap years, then we can determine if any given year k is a leap year via a scheme like this, as follows:
- let p be the number of zeroes terminating the binary expansion of k.
- if the (p+1)st bit of m/2ⁿ after the decimal point is 1, then k is a leap year, otherwise it's a common year.

The years for which we examine the jth bit are exactly 1/2^j of all years, so this works.

For 31/128 = .0011111, this says that a year should be a leap year if its binary expansion ends in exactly 2, 3, 4, 5, or 6 zeroes -- exactly the rule I suggested in the first place. For 33/128 = .0100001, a year is a leap year if its binary expansion ends in exactly 1 or 6 zeroes. That's one flaw with this scheme -- the set of leap years changes radically as m/2ⁿ passes through some small power of (1/2). But that wasn't my aim here; my aim was to be able to read off if a year is a leap year directly from the binary expansion, just as one can almost do with the decimal expansion in the current scheme. The 8/33 scheme I talked about yesterday doesn't have this property in any small base, although I made the argument that since 33 = (100-1)/3 there are worse situations to be in.

(Exercise for the reader: can you come up with a scheme like this in decimal? Calling this an "exercise" isn't quite fair, because I don't know if it's possible.)