mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-05-18, 19:39   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default 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
File Type: txt party.cpp.txt (2.3 KB, 194 views)
fivemack is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 02:29.


Thu Sep 29 02:29:41 UTC 2022 up 41 days, 23:58, 0 users, load averages: 0.82, 1.04, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔