Leap year formula to arbitrary precision

Question

Leap years are determined by a scheme in which every $4$th year is a leap year, but every $4\cdot 25$th year is exempted, but every $4\cdot 25 \cdot 4$th year is reinstated $\ldots $ and there we stop, because that's good enough in practice to approximate the actual length of a year in terms of days. But what if we wanted to approximate arbitrarily well? In other words, can any real number $r$, $0<r<1$, be written in the form $$ r=\sum_{n=0}^{\infty} \frac{(-1)^n }{\prod_{i=0}^{n} a_i } $$ with $a_i $ a sequence of positive integers? For the earth at its current rate of rotation, where a fraction $r=0.242375$ of a day has to be represented, the existing sequence $a_0 =4$, $a_1 =25$, $a_2 =4$ merely has to be supplemented by $a_3 =20$ to reproduce this $r$ to the full known precision.

Answer 1

The greedy algorithm always produces a suitable expansion. The proof follows.

Lemma: If $0<x<1$, then $x$ may be written as $\frac 1n(1-y)$ for some $n$ with $0\le y<\frac 1{n+1}$.

Proof: Let $n$ be such that $\frac 1{n+1}<x\le \frac 1n$. Then $0\le \frac 1n-x< \frac 1{n(n+1)}$. In particular, writing $y=n(\frac 1n-x)$, we see $0\le y<\frac 1{n+1}$ as required.

Note that in the above, $n=\lfloor \frac 1x\rfloor$ so that $y=\lfloor\frac 1x\rfloor (1/\lfloor \frac 1x\rfloor-x)=1-x\lfloor \frac 1x\rfloor$. Define the function $f(x)=\lfloor \frac 1x\rfloor$ and $g(x)=1-xf(x)$.

We now apply this inductively: let $x_0=r$, and $x_{n+1}=g(x_n)$ for each $n$ and $a_n=f(x_n)$. We claim that for each $n$, $$ r=\sum_{j=0}^n \frac{(-1)^j}{\prod_{i=0}^j a_i}+\frac{(-1)^{n+1}}{\prod_{i=0}^n a_i}x_{n+1}. $$ Since $x_{n+1}=\frac 1{a_{n+1}}(1-x_{n+2})$, the formula holds immediately by induction, proving the claim.

Answer 2

(Disclaimer: I am not an expert, I just know a few words and how to Google)

This reminds me of the so-called Engel expansion of a real number $x$, which is defined to be the unique non-decreasing sequence of positive integers $a_1, a_2, a_3, \ldots$ such that

$$ x = {1 \over a_1} + {1 \over a_1 a_2} + {1 \over a_1 a_2 a_3} + \cdots $$

So it seems logical to call this the "alternating Engel expansion", and Googling that finds that it also goes by the name "Pierce expansion", for example as used by Fang 2015 or Shallit 1986. The name is after Pierce 1929.

Fang gives an algorithm for finding the expansion: for any real number $x \in (0, 1]$ and $n \ge 1$, we can take $x_1 = x$ and recursively define

$$a_n = \lfloor {1 \over x_n} \rfloor, x_{n+1} = 1 - x_n a_n.$$

However this has the constraint that the $a_i$ be increasing, and in practice this isn't necessary and can force the coefficients to get quite large. For example for r = 0.242375 we get the sequence of $a_i$ as $4, 32, 41, 62, 124, 125$ (leading to a 5043328000-year calendar cycle) whereas you've observed $4, 25, 4, 20$ and an 8000-year calendar cycle suffices to get the same accuracy.

Shallit 1994 has the application to leap years and calls the sequence you've defined an "intercalation sequence". He points out that there always is an intercalation sequence (the Pierce expansion).

This all suggests to me a problem - find the optimal intercalation sequence for a rational number, in the sense that the product $a_1 a_2 \ldots a_n$ is as small as possible. This is not necessarily the result of the greedy expansion. For example

$$ {13 \over 45} = {1 \over 3} - {1 \over 3 \times 7} + {1 \over 3 \times 7 \times 15} = {1 \over 3} - {1 \over 3 \times 5} + {1 \over 3 \times 5 \times 3} $$ where the first expansion is greedy and the second has smaller products. This seems to be related at least in spirit to similar problems for Egyptian fractions.

works cited

Fang, Lulu, Large and moderate deviation principles for alternating Engel expansions, J. Number Theory 156, 263-276 (2015). ZBL1317.60023.

Pierce, T. A., On an algorithm and its use in approximating roots of algebraic equations., Amer. Math. Monthly 36, 523-525 (1929). ZBL55.0305.06.

Shallit, J. O., Metric theory of Pierce expansions, Fibonacci Q. 24, 22-40 (1986). ZBL0598.10057..

Shallit, Jeffrey, Pierce expansions and rules for the determination of leap years, Fibonacci Q. 32, No. 5, 416-423 (1994). ZBL0823.11043.