2007-05-18, 19:39 | #1 |
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 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. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Fun with partition function | Batalov | And now for something completely different | 49 | 2022-08-04 12:08 |
Number of distinct prime factors of a Double Mersenne number | aketilander | Operazione Doppi Mersennes | 1 | 2012-11-09 21:16 |
residues and non residues of general quadratic congruences | smslca | Math | 0 | 2012-10-12 06:42 |
Have a look at the partition numbers | fivemack | Factoring | 57 | 2007-12-28 10:37 |
Linux/SUSE noob trouble - Resize partition | OmbooHankvald | Linux | 19 | 2005-11-18 10:39 |