# Formula for occurrence of leap years in the Jewish calendar

Over at Judaism.SE, there was a discussion about a formula to determine leap years in the Jewish calendar. Basically, the calendar follows a 19-year cycle, and seven of those years -- 3, 6, 8, 11, 14, 17, and 19 -- are leap years. Someone reduced this to the simple equation: (7y+1) mod 19 < 7.

My question is whether there is any rhyme or reason as to why this works, and is there a method to go about determining such formulas -- or is it all simply trial and error?

-

Here's "why this works", and also how to find a formula (with exhaustive search, essentially) when one exists. But really, the answer is that no such formula may exist in general; we're just lucky it exists for this particular set of 7 values mod 19.

The basic idea is that for any integer $k$ relatively prime to $19$, the function $y \mapsto ky$ modulo 19 is invertible. In other words, instead of looking at a set of integers $y$ modulo 19, you can look at the corresponding set of integers $ky$ mod 19, and if that set happens to have a simple characterisation for some $k$, it amounts to a characterisation of your original set of values.

So consider a table of $ky \bmod 19$, for $y$ in your list $[0, 3, 6, 8, 11, 14, 17]$, and integers $k$. Only integers $k$ from $1$ to $18$ need be considered, as $(k+19)y \equiv ky \mod 19$. No need to consider $k=0$ as $0$ is not relatively prime to $19$: $0y \bmod 19$ is always $0$, so it doesn't tell you anything about $y$. Now it so happens that for $k=7$, the values modulo 19 that are attained happen to be consecutive modulo 19. For instance, this Python code:

for k in range(1,19):
values = [(k*y)%19 for y in [0, 3, 6, 8, 11, 14, 17]]
attained = ['*' if x in values else '.' for x in range(19)]
print "%2d: %-30s %s" % (k, values, ''.join(attained))


prints

 1: [0, 3, 6, 8, 11, 14, 17]       *..*..*.*..*..*..*.
2: [0, 6, 12, 16, 3, 9, 15]       *..*..*..*..*..**..
3: [0, 9, 18, 5, 14, 4, 13]       *...**...*...**...*
4: [0, 12, 5, 13, 6, 18, 11]      *....**....***....*
5: [0, 15, 11, 2, 17, 13, 9]      *.*......*.*.*.*.*.
6: [0, 18, 17, 10, 9, 8, 7]       *......****......**
7: [0, 2, 4, 18, 1, 3, 5]         ******............*
8: [0, 5, 10, 7, 12, 17, 3]       *..*.*.*..*.*....*.
9: [0, 8, 16, 15, 4, 12, 1]       **..*...*...*..**..
10: [0, 11, 3, 4, 15, 7, 18]       *..**..*...*...*..*
11: [0, 14, 9, 12, 7, 2, 16]       *.*....*.*..*.*.*..
12: [0, 17, 15, 1, 18, 16, 14]     **............*****
13: [0, 1, 2, 9, 10, 11, 12]       ***......****......
14: [0, 4, 8, 17, 2, 6, 10]        *.*.*.*.*.*......*.
15: [0, 7, 14, 6, 13, 1, 8]        **....***....**....
16: [0, 10, 1, 14, 5, 15, 6]       **...**...*...**...
17: [0, 13, 7, 3, 16, 10, 4]       *..**..*..*..*..*..
18: [0, 16, 13, 11, 8, 5, 2]       *.*..*..*..*.*..*..


Now look at each row in the picture on the right, until you notice that for $k=7$, all the asterisks are consecutive (cyclically) — the values taken are $[18, 0, 1, 2, 3, 4, 5]$. You can add 1 to shift it cyclically, then the values will be $[0, 1, 2, 3, 4, 5, 6]$. Thus the set of values $(7y+1) \bmod 19$ for $y$ in your original list is the above, which has a nice simple characterisation as the set of nonnegative integers less than 7. Using this characterisation gives the formula $(7y + 1) \bmod 19 < 7$. (If you look at the table you see that $k=12$ also has the values consecutive; this is not surprising because $12 \equiv -7 \mod 19$.)

We just happened to get lucky. Starting with a different set of 7 integers may not give any such formula. For instance if we change "11" to "12", we get the picture:

 1: [0, 3, 6, 8, 12, 14, 17]       *..*..*.*...*.*..*.
2: [0, 6, 12, 16, 5, 9, 15]       *....**..*..*..**..
3: [0, 9, 18, 5, 17, 4, 13]       *...**...*...*...**
4: [0, 12, 5, 13, 10, 18, 11]     *....*....****....*
5: [0, 15, 11, 2, 3, 13, 9]       *.**.....*.*.*.*...
6: [0, 18, 17, 10, 15, 8, 7]      *......**.*....*.**
7: [0, 2, 4, 18, 8, 3, 5]         *.****..*.........*
8: [0, 5, 10, 7, 1, 17, 3]        **.*.*.*..*......*.
9: [0, 8, 16, 15, 13, 12, 1]      **......*...**.**..


(I've omitted $k=10$ to $k=18$) in which the asterisks are not consecutive for any $k$. This doesn't mean that no clever formula of any sort can exist, but it does mean that no formula of the form $ky + l < m$ will work for any triple $(k, l, m)$.

It may be an interesting probability exercise to calculate how lucky we got. :-) (Given a modulus like $19$, what is the probability that for a set of integers of a certain size, for some $k$ the multiples are consecutive?)

-
Thanks for the detailed answer! –  Dave Jun 22 '11 at 19:38
I haven't thought about it, but I would imagine that for the sets that are likely to occur in calendar applications -- that is, where the leap years are roughly evenly spaced -- you're more likely to get "lucky" than you would than for sets chosen uniformly at random. –  Michael Lugo Jun 23 '11 at 0:04
Indeed Michael is right as I indicate in my answer. –  Johan Aug 22 '11 at 8:47

There is a way to motivate such formulas but not completely get rid of trial and error. For the following I am indebted to "Calendrical Calculation" by Dershowitz and Reingold.

It turns out that the leap year structure of several other calendars, among them the Islamic, also has can be characterized by conditions of the form $(by + c) \bmod l < b$. It turns out that this can be explained if one assumes they have adopted a common method for distributing the leap years as evenly as possible.

Assume we want to have $l$ leap-years among the years $1,2,\ldots n$. (Where $n \geq l$.) One way of accomplishing this is to say that year $y$ is a leap-year if and only if there exists an integer $k$ such that $y-1 < k \frac{n}{l} \leq y$. We can imagine marking out the multiples of $\frac{n}{l}$ on the number line and then our condition means that $y$ is the first integer after one of these multiples.

We can rewrite the condition we impose as $k\frac{n}{l} \leq y < k\frac{n}{l}+1$ which in turn is equivalent to $$kn \leq yl < kn +l.$$ This is true for some integer $k$ if and only if $(yl \bmod n) < l$.

Now you might object that this does not give the right answer and you would of course be correct. However this can be remedied. There is nothing that forces us to start the cycle at year $1$ of the calendar. If we instead start the cycle at year $a$ our formula becomes $$((y-a+1)l \bmod n) < l.$$

Setting $l= 7,$n=19 and $a=9$ we reproduce the right formula after simplification. (The trial and error part is now really only in finding $a$.)

-
A similar argument applies to the location of the black keys on a piano. –  Gerry Myerson Aug 22 '11 at 13:16
@GerryMyerson Indeed the two are parallel judaism.stackexchange.com/a/6517/759 –  Double AA May 21 '13 at 22:55
@DoubleAA, thanks for the link! –  Gerry Myerson May 22 '13 at 12:59