Partition number congruences

[fivemack]

There are Ramanujan's congruences for 5, 7 and 11.

Experimentally (by computing P_N mod 23 for N=0..10^7) it appears that, if N is congruent to [(5^3*23)*J + 599] mod (5^4*23), for J=1..4 but not 0, then NumberOfPartitions(N) is always divisible by 23.

NumberOfPartitions(N) is divisible by 13 for N<10^7 congruent to any of thirty numbers modulo (11^3 * 13); these thirty numbers are precisely those which are 11^2*{1,2,3,5,8}-5 mod 11^3 and {2,3,5,7,9,10} mod 13.

Modulo 17 it looks a bit more fiddly; many more partition numbers with index 2623 mod (17*23^2) are divisible by 17 than would be expected by chance, and factors of 5 in the modulus also help (though the good congruence classes mod 5*17*23^2 are exactly the cover of those mod 17*23^2), but it is a little inconvenient to compute enough partition numbers mod-17 to get a reasonable sample in a bin modulo 5620625.

Modulo 19, 13^2*19 seems quite a promising modulus, and 19*23^2 also, but again getting convincing statistics modulo 1698619 will take a little while.

If anyone wants to have a fiddle, my code for computing partition numbers modulo N is attached. I'm not quite sure what the asymptotic speed is; I suspect it takes O(k^1.5) to calculate up to P(k), and I know it takes about 20 seconds for k=10^6

./party 29 1000000 | awk '$10>3 {print $8/$10,$0}' | sort -n to get an idea of interesting moduli

./party 19 100000000 1698619 to get stats modulo only the modulus 1698619.