mersenneforum.org > Math Partition number congruences
 Register FAQ Search Today's Posts Mark Forums Read

2007-05-18, 19:39   #1
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

144658 Posts
Partition number congruences

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.
Attached Files
 party.cpp.txt (2.3 KB, 189 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 24 2018-02-27 17:03 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 smslca Math 0 2012-10-12 06:42 fivemack Factoring 57 2007-12-28 10:37 OmbooHankvald Linux 19 2005-11-18 10:39

All times are UTC. The time now is 16:22.

Thu May 19 16:22:26 UTC 2022 up 35 days, 14:23, 1 user, load averages: 2.51, 2.32, 2.32