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 &lt; 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 &lt; 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 &lt; 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?)
It follows the steps in an octave of music.  Full step, full step, half step, full step, full step, full step, half step.  The full steps the third year is leap year.  The half steps the second year is leap year.  Thus the leap years are in a 19 year cycle are as follows: 3, 6, 8, 11, 14, 17, 19.  No trial and error, just know the scale.