Formula for occurrence of leap years in the Jewish calendar

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?)

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$.)