Thread Rating:

Poll

7 votes (41.17%)
No votes (0%)
2 votes (11.76%)
2 votes (11.76%)
2 votes (11.76%)
6 votes (35.29%)
No votes (0%)
4 votes (23.52%)
2 votes (11.76%)
1 vote (5.88%)

17 members have voted

kubikulann
kubikulann
  • Threads: 27
  • Posts: 905
Joined: Jun 28, 2011
August 21st, 2019 at 7:44:08 PM permalink
Seems like the columns tend to the Fibonacci series (1,1,2,3,5,8,13,21,34,55,…)
where one term is the sum of the two previous ones.
Reperiet qui quaesiverit
weezrDASvegas
weezrDASvegas
  • Threads: 2
  • Posts: 69
Joined: Feb 2, 2018
August 22nd, 2019 at 1:21:40 AM permalink
Quote: kubikulann

Quote: gordonm888


I note that one can assign a number of permutations to any partition (e.g.: the partition 3-2-1-1 has 12 permutations, ) and then sum up the number of permutations for every entry in this table. When I do that I get this table:

1
2
3
4
5
6
7
8
9
10
Total
1
1
1
2
1
1
2
3
1
2
1
4
4
1
3
3
1
8
5
1
4
6
4
1
16
6
1
5
10
10
5
1
32
7
1
6
15
20
15
6
1
64
8
1
7
21
35
35
21
7
1
128
9
1
8
28
56
70
56
28
8
1
256
10
1
9
36
84
126
126
84
36
9
1
512


This is Pascal’s table. (aka Binomial coefficients table)



Lottery numerology
A combo of 6 numbers occurs 2 times: diagonally and vertically
3 6 10 15 21 28
They are birthday numbers. Many people swear by birth numbers and some won millions with them in lottos all over the world.
Im gonna play em. Thanks all.
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
Thanked by
Ajaxx
August 22nd, 2019 at 11:01:45 AM permalink
Quote: Wizard

Sorry to interrupt a good discussion, but here is a count of the number of pieces by size. The left column shows the piece size and along the top row is the base number that is getting partitioned.

Piece 1 2 3 4 5 6 7 8 9 10
1 1 2 4 7 12 19 30 45 67 97
2 1 1 3 4 8 11 19 26 41
3 1 1 2 4 6 9 15 21
4 1 1 2 3 6 8 13
5 1 1 2 3 5 8
6 1 1 2 3 5
7 1 1 2 3
8 1 1 2
9 1 1
10 1
Total 1 3 6 12 20 35 54 86 128 192


Offhand, the only interesting pattern I'm seeing is the total number of pieces generally divide lots of ways:

6 = 2*3
12 = 2*2*3
20 =2*2*5
35 = 5*7
54 = 2*3*3*3
86 = 2 * 43
128 = 2*2*2*2*2*2*2
192 = 2*2*2*2*2*2*3

I guess 86 is the exception.



If you keep a running sum/total of the Partitions Numbers and add one to that running sum you get:
N...P(N)....(running Sum of P(N)) +1
1___1______2
2___2______4
3___3______7
4___5______12
5___7______19
6___11_____30
7___15_____45
8___22_____67
9___30_____97

Notice that the (running sum of the partition number +1) = number of pieces that are 1 !

Edit: Another way to say this: think of the "Pieces of 1" row as a sequence of numbers. If you take the nth term and subtract the (n-1) term, you obtain a sequence that is the partition numbers!!

When you look at primes, you can't find any patterns. When you look at partitions, everything is a recursive pattern! Everywhere you look!!! Its maddening!!!! It's TURTLES all the way down!
Last edited by: gordonm888 on Aug 22, 2019
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
August 23rd, 2019 at 6:02:10 AM permalink
The long silence after my last post leaves me wondering whether Wizard (and others) are attempting to write an algorithm, using combination math, to calculate the number of "pieces of 1" in partitions of any number N - as a way to calculate the partition number of any number N. I've been trying to conceptually develop the algorithm in my head, to judge whether its worth actually trying to attempt it. I don't know - its uncertain of success.

Edit: I think that such an attempt is likely to wind up with an algorithm that is a "sum of a sum" of terms, amounting to a sum of N[sup}2 terms. That's essentially the same as developing a table of N[sup}2 entries, as we are doing now. Unless there is a way to represent many terms by a function (like defining an infinite series to be a sin() function) I question whether such an approach will work.
Last edited by: gordonm888 on Aug 23, 2019
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
August 25th, 2019 at 3:46:36 AM permalink
Quote: gordonm888

The long silence after my last post ...



Sorry I was out of town for a few days. I'll get caught up shortly. Just skimming this, I find it intriguing, but need to chew on it some more.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
August 25th, 2019 at 3:01:33 PM permalink
Let me put into a table, what you said, because I love tables. The third column represents the sum of partitions from 1 to n-1, for n. For examples, for n=5, it equals P(1)+ P(2) + P(3) + P(4). As Gordon said, this column equals one less than the number of pieces of size one in the partition of n.

n Partitions Sum from 1 to n-1 Size 1
1 1 0 1
2 2 1 2
3 3 3 4
4 5 6 7
5 7 11 12
6 11 18 19
7 15 29 30
8 22 44 45
9 30 66 67
10 42 96 97
11 56 138 139
12 77 194 195
13 101 271 272
14 135 372 373
15 176 507 508


Offhand, I can't think of why this is true.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
August 25th, 2019 at 3:35:07 PM permalink
I found a very good estimate for the P(n) if you know P(n-1).

Here it is

P(n) = P(n-1) * exp(0.923266 * n-0.448858)

Total Partitions Estimate
2 2 2
3 3 4
4 5 5
5 7 8
6 11 11
7 15 16
8 22 22
9 30 31
10 42 42
11 56 58
12 77 76
13 101 103
14 135 134
15 176 178
16 231 230
17 297 299
18 385 382
19 490 492
20 627 623
21 792 793
22 1,002 997
23 1,255 1,256
24 1,575 1,567
25 1,958 1,958
26 2,436 2,425
27 3,010 3,006
28 3,718 3,702
29 4,565 4,558
30 5,604 5,579
31 6,842 6,829
32 8,349 8,314
33 10,143 10,118
34 12,310 12,261
35 14,883 14,844
36 17,977 17,904
37 21,637 21,578
38 26,015 25,914
39 31,185 31,093
40 37,338 37,197
41 44,583 44,450
42 53,174 52,975
43 63,261 63,069
44 75,175 74,902
45 89,134 88,857
46 105,558 105,184
47 124,754 124,368
48 147,273 146,758
49 173,525 172,989
50 204,226 203,529
51 239,943 239,201
52 281,589 280,650
53 329,931 328,922
54 386,155 384,890
55 451,276 449,910
56 526,823 525,136
57 614,154 612,313
58 715,220 712,982
59 831,820 829,364
60 966,467 963,500
61 1,121,505 1,118,247
62 1,300,156 1,296,257
63 1,505,499 1,501,189
64 1,741,630 1,736,523
65 2,012,558 2,006,902
66 2,323,520 2,316,851
67 2,679,689 2,672,297
68 3,087,735 3,079,074
69 3,554,345 3,544,718
70 4,087,968 4,076,762
71 4,697,205 4,684,738
72 5,392,783 5,378,324
73 6,185,689 6,169,606
74 7,089,500 7,070,934
75 8,118,264 8,097,582
76 9,289,091 9,265,325
77 10,619,863 10,593,389
78 12,132,164 12,101,831
79 13,848,650 13,814,875
80 15,796,476 15,757,907
81 18,004,327 17,961,369
82 20,506,255 20,457,367
83 23,338,469 23,284,033
84 26,543,660 26,481,857
85 30,167,357 30,098,590
86 34,262,962 34,185,095
87 38,887,673 38,801,042
88 44,108,109 44,010,271
89 49,995,925 49,887,144
90 56,634,173 56,511,563
91 64,112,359 63,976,143
92 72,533,807 72,380,601
93 82,010,177 81,840,049
94 92,669,720 92,478,779
95 104,651,419 104,439,541
96 118,114,304 117,876,907
97 133,230,930 132,967,732
98 150,198,136 149,903,764
99 169,229,875 168,903,715
100 190,569,292 190,205,143
101 214,481,126 214,077,983
102 241,265,379 240,815,950
103 271,248,950 270,751,831
104 304,801,365 304,248,019
105 342,325,709 341,714,098
106 384,276,336 383,596,583
107 431,149,389 430,398,690
108 483,502,844 482,669,611
109 541,946,240 541,026,864
110 607,163,746 606,144,673
111 679,903,203 678,779,658
112 761,002,156 759,758,436
113 851,376,628 850,006,583
114 952,050,665 950,535,914
115 1,064,144,451 1,062,477,315
116 1,188,908,248 1,187,067,276
117 1,327,710,076 1,325,685,559
118 1,482,074,143 1,479,841,222
119 1,653,668,665 1,651,215,227
120 1,844,349,560 1,841,646,583
121 2,056,148,051 2,053,180,746
122 2,291,320,912 2,288,055,476
123 2,552,338,241 2,548,756,438
124 2,841,940,500 2,838,003,205
125 3,163,127,352 3,158,812,305
126 3,519,222,692 3,514,484,355
127 3,913,864,295 3,908,675,862
128 4,351,078,600 4,345,387,189
129 4,835,271,870 4,829,045,048
130 5,371,315,400 5,364,492,060
131 5,964,539,504 5,957,080,654
132 6,620,830,889 6,612,665,660
133 7,346,629,512 7,337,711,517
134 8,149,040,695 8,139,287,915
135 9,035,836,076 9,025,193,137
136 10,015,581,680 10,003,954,084
137 11,097,645,016 11,084,967,033
138 12,292,341,831 12,278,504,303
139 13,610,949,895 13,595,875,397
140 15,065,878,135 15,049,440,854
141 16,670,689,208 16,652,797,825
142 18,440,293,320 18,420,803,387
143 20,390,982,757 20,369,787,021
144 22,540,654,445 22,517,586,846
145 24,908,858,009 24,883,793,414
146 27,517,052,599 27,489,800,523
147 30,388,671,978 30,359,086,343
148 33,549,419,497 33,517,282,606
149 37,027,355,200 36,992,497,240
150 40,853,235,313 40,815,407,361
151 45,060,624,582 45,019,630,316
152 49,686,288,421 49,641,843,916
153 54,770,336,324 54,722,214,741
154 60,356,673,280 60,304,551,933
155 66,493,182,097 66,436,799,884
156 73,232,243,759 73,171,234,091
157 80,630,964,769 80,565,028,699
158 88,751,778,802 88,680,500,984
159 97,662,728,555 97,585,767,147
160 107,438,159,466 107,355,045,666
161 118,159,068,427 118,069,412,967
162 129,913,904,637 129,817,179,016
163 142,798,995,930 142,694,759,153
164 156,919,475,295 156,807,133,501
165 172,389,800,255 172,268,855,018
166 189,334,822,579 189,204,609,387
167 207,890,420,102 207,750,378,180
168 228,204,732,751 228,054,120,182
169 250,438,925,115 250,277,114,645
170 274,768,617,130 274,594,783,747
171 301,384,802,048 301,198,246,569
172 330,495,499,613 330,295,309,281
173 362,326,859,895 362,112,259,825
174 397,125,074,750 396,895,058,709
175 435,157,697,830 434,911,413,024
176 476,715,857,290 476,452,200,458
177 522,115,831,195 521,833,869,016
178 571,701,605,655 571,400,136,521
179 625,846,753,120 625,524,763,617
180 684,957,390,936 684,613,579,960
181 749,474,411,781 749,107,689,772
182 819,876,908,323 819,485,877,701
183 896,684,817,527 896,268,317,743
184 980,462,880,430 980,019,425,239
185 1,071,823,774,337 1,071,352,143,426
186 1,171,432,692,373 1,170,931,321,289
187 1,280,011,042,268 1,279,478,668,917
188 1,398,341,745,571 1,397,776,745,817
189 1,527,273,599,625 1,526,674,692,637
190 1,667,727,404,093 1,667,092,933,883
191 1,820,701,100,652 1,820,029,801,774
192 1,987,276,856,363 1,986,567,076,583
193 2,168,627,105,469 2,167,877,641,991
194 2,366,022,741,845 2,365,231,996,716
195 2,580,840,212,973 2,580,007,105,134
196 2,814,570,987,591 2,813,694,041,537
197 3,068,829,878,530 3,067,908,214,547
198 3,345,365,983,698 3,344,398,333,926
199 3,646,072,432,125 3,645,058,221,777
200 3,972,999,029,388 3,971,937,310,627
201 4,328,363,658,647 4,327,254,289,804
202 4,714,566,886,083 4,713,409,383,776
203 5,134,205,287,973 5,133,000,108,179
204 5,590,088,317,495 5,588,835,619,535
205 6,085,253,859,260 6,083,954,904,602
206 6,622,987,708,040 6,621,643,524,989
207 7,206,841,706,490 7,205,454,616,281
208 7,840,656,226,137 7,839,228,409,394
209 8,528,581,302,375 8,527,116,458,389
210 9,275,102,575,355 9,273,604,382,976
211 10,085,065,885,767 10,083,539,816,166
212 10,963,707,205,259 10,962,158,865,096
213 11,916,681,236,278 11,915,118,346,825
214 12,950,095,925,895 12,948,526,550,206
215 14,070,545,699,287 14,068,980,396,734
216 15,285,151,248,481 15,283,601,178,668
217 16,601,598,107,914 16,600,077,386,512
218 18,028,182,516,671 18,026,706,182,776
219 19,573,856,161,145 19,572,442,752,352
220 21,248,279,009,367 21,246,948,396,225
221 23,061,871,173,849 23,060,647,367,795
222 25,025,873,760,111 25,024,782,607,963
223 27,152,408,925,615 27,151,481,184,166
224 29,454,549,941,750 29,453,818,819,391
225 31,946,390,696,157 31,945,895,218,868
226 34,643,126,322,519 34,642,908,729,066
227 37,561,133,582,570 37,561,243,002,581
228 40,718,063,627,362 40,718,553,325,339
229 44,132,934,884,255 44,133,866,294,224
230 47,826,239,745,920 47,827,679,552,474
231 51,820,051,838,712 51,822,076,403,342
232 56,138,148,670,947 56,140,840,962,281
233 60,806,135,438,329 60,809,589,881,049
234 65,851,585,970,275 65,855,905,223,838
235 71,304,185,514,919 71,309,485,804,774
236 77,195,892,663,512 77,202,300,401,270
237 83,561,103,925,871 83,568,761,572,559
238 90,436,839,668,817 90,445,902,217,271
239 97,862,933,703,585 97,873,575,120,469
240 105,882,246,722,733 105,894,656,301,136
241 114,540,884,553,038 114,555,274,014,365
242 123,888,443,077,259 123,905,042,795,369
243 133,978,259,344,888 133,997,326,179,546
244 144,867,692,496,445 144,889,505,925,148
245 156,618,412,527,946 156,643,283,280,695
246 169,296,722,391,554 169,324,988,512,763
247 182,973,889,854,026 183,005,926,250,793
248 197,726,516,681,672 197,762,731,133,712
249 213,636,919,820,625 213,677,763,545,749
250 230,793,554,364,681 230,839,518,036,227
251 249,291,451,168,559 249,343,076,603,055
252 269,232,701,252,579 269,290,577,482,513
253 290,726,957,916,112 290,791,734,156,514
254 313,891,991,306,665 313,964,373,128,410
255 338,854,264,248,680 338,935,027,975,330
256 365,749,566,870,782 365,839,555,950,559
257 394,723,676,655,357 394,823,817,645,196
258 425,933,084,409,356 426,044,383,633,593
259 459,545,750,448,675 459,669,311,792,618
260 495,741,934,760,846 495,878,956,707,614
261 534,715,062,908,609 534,866,858,363,775
262 576,672,674,947,168 576,840,668,810,756
263 621,837,416,509,615 622,023,167,767,158
264 670,448,123,060,170 670,653,323,043,735
265 722,760,953,690,372 722,987,450,753,395
266 779,050,629,562,167 779,300,428,193,871
267 839,611,730,366,814 839,887,018,776,921
268 904,760,108,316,360 905,063,258,652,871
269 974,834,369,944,625 975,167,969,139,993
270 1,050,197,489,931,110 1,050,564,341,278,630
271 1,131,238,503,938,600 1,131,641,661,657,750
272 1,218,374,349,844,330 1,218,817,122,296,590
273 1,312,051,800,816,210 1,312,537,789,269,910
274 1,412,749,565,173,450 1,413,282,669,049,830
275 1,520,980,492,851,170 1,521,564,953,213,890
276 1,637,293,969,337,170 1,637,934,376,582,770
277 1,762,278,433,057,260 1,762,979,775,792,390
278 1,896,564,103,591,580 1,897,331,779,227,310
279 2,040,825,852,575,070 2,041,665,722,301,010
280 2,195,786,311,682,510 2,196,704,714,572,330
281 2,362,219,145,337,710 2,363,222,960,201,970
282 2,540,952,590,045,690 2,542,049,253,703,810
283 2,732,873,183,547,530 2,734,070,760,525,010
284 2,938,929,793,929,550 2,940,236,999,631,600
285 3,160,137,867,148,990 3,161,564,146,448,330
286 3,397,584,011,986,770 3,399,139,568,230,940
287 3,652,430,836,071,050 3,654,126,719,723,870
288 3,925,922,161,489,420 3,927,770,305,994,760
289 4,219,388,528,587,090 4,221,401,850,472,780
290 4,534,253,126,900,880 4,536,445,569,650,230
291 4,872,038,056,472,080 4,874,424,703,634,060
292 5,234,371,069,753,670 5,236,968,198,243,810
293 5,622,992,691,950,600 5,625,817,899,891,690
294 6,039,763,882,095,510 6,042,836,153,121,440
295 6,486,674,127,079,080 6,490,013,974,965,660
296 6,965,850,144,195,830 6,969,479,689,946,320
297 7,479,565,078,510,580 7,483,508,214,051,230
298 8,030,248,384,943,040 8,034,530,865,140,210
299 8,620,496,275,465,020 8,625,145,903,435,480
300 9,253,082,936,723,600 9,258,129,673,182,110
301 9,930,972,392,403,500 9,936,448,565,599,450
302 10,657,331,232,548,800 10,663,271,667,656,800
303 11,435,542,077,822,100 11,441,984,334,851,100
304 12,269,218,019,229,400 12,276,202,545,689,500
305 13,162,217,895,057,700 13,169,788,295,603,300
306 14,118,662,665,280,000 14,126,865,881,272,200
307 15,142,952,738,857,100 15,151,839,354,143,200
308 16,239,786,535,829,600 16,249,410,987,302,400
309 17,414,180,133,147,200 17,424,601,057,574,000
310 18,671,488,299,600,300 18,682,768,780,005,900
311 20,017,426,762,576,900 20,029,634,721,655,400
312 21,458,096,037,352,800 21,471,304,525,099,900
313 23,000,006,655,487,300 23,014,294,295,620,400
314 24,650,106,150,830,400 24,665,557,475,818,700
315 26,415,807,633,566,300 26,432,513,591,256,500
316 28,305,020,340,996,000 28,323,078,684,208,600
317 30,326,181,989,842,900 30,345,697,851,320,000
318 32,488,293,351,466,600 32,509,379,696,109,400
319 34,800,954,869,440,800 34,823,733,146,946,400
320 37,274,405,776,748,000 37,299,006,445,639,900
321 39,919,565,526,999,900 39,946,128,795,469,600
322 42,748,078,035,954,600 42,776,754,468,280,500
323 45,772,358,543,578,000 45,803,309,901,036,700
324 49,005,643,635,237,800 49,039,043,576,859,200
325 52,462,044,228,828,600 52,498,079,266,012,700
326 56,156,602,112,874,200 56,195,472,418,011,800
327 60,105,349,839,666,500 60,147,270,329,785,500
328 64,325,374,609,114,500 64,370,575,877,957,000
329 68,834,885,946,073,800 68,883,615,494,065,300
330 73,653,287,861,850,300 73,705,811,169,211,700
331 78,801,255,302,666,600 78,857,857,225,508,800
332 84,300,815,636,225,100 84,361,801,640,598,500
333 90,175,434,980,549,600 90,241,132,726,932,600
334 96,450,110,192,202,700 96,520,870,953,318,000
335 103,151,466,321,735,000 103,227,666,780,563,000
336 110,307,860,425,292,000 110,389,904,302,398,000
337 117,949,491,546,113,000 118,037,811,639,875,000
338 126,108,517,833,796,000 126,203,577,886,370,000
339 134,819,180,623,301,000 134,921,477,635,335,000
340 144,117,936,527,873,000 144,228,002,896,388,000
341 154,043,597,379,576,000 154,162,003,523,593,000
342 164,637,479,165,761,000 164,764,835,973,643,000
343 175,943,559,810,422,000 176,080,521,617,844,000
344 188,008,647,052,292,000 188,155,914,441,466,000
345 200,882,556,287,683,000 201,040,879,464,350,000
346 214,618,299,743,286,000 214,788,481,736,150,000
347 229,272,286,871,217,000 229,455,187,360,548,000
348 244,904,537,455,382,000 245,101,076,427,177,000
349 261,578,907,351,144,000 261,790,069,437,081,000
350 279,363,328,483,702,000 279,590,167,131,561,000
351 298,330,063,062,758,000 298,573,705,454,962,000
352 318,555,973,788,329,000 318,817,625,598,558,000
353 340,122,810,048,577,000 340,403,761,014,690,000
354 363,117,512,048,110,000 363,419,141,393,747,000
355 387,632,532,919,029,000 387,956,315,666,778,000
356 413,766,180,933,342,000 414,113,694,080,277,000
357 441,622,981,929,358,000 441,995,911,597,065,000
358 471,314,064,268,398,000 471,714,212,733,254,000
359 502,957,566,506,000,000 503,386,860,294,917,000
360 536,679,070,310,691,000 537,139,568,199,682,000
361 572,612,058,898,037,000 573,105,961,076,774,000
362 610,898,403,751,884,000 611,428,060,918,555,000
363 651,688,879,997,206,000 652,256,803,730,406,000
364 695,143,713,458,946,000 695,752,586,553,637,000
365 741,433,159,884,081,000 742,085,848,086,667,000
366 790,738,119,649,411,000 791,437,683,397,883,000
367 843,250,788,562,528,000 844,000,496,260,715,000
368 899,175,348,396,088,000 899,978,689,741,625,000
369 958,728,697,912,338,000 959,589,398,908,019,000
370 1,022,141,228,367,340,000 1,023,063,266,444,290,000
371 1,089,657,644,424,390,000 1,090,645,265,413,150,000
372 1,161,537,834,849,960,000 1,162,595,570,132,140,000
373 1,238,057,794,119,120,000 1,239,190,479,809,280,000
374 1,319,510,599,727,470,000 1,320,723,396,115,790,000
375 1,406,207,446,561,480,000 1,407,505,859,788,460,000
376 1,498,478,743,590,580,000 1,499,868,647,676,860,000
377 1,596,675,274,490,750,000 1,598,162,935,821,660,000
378 1,701,169,427,975,810,000 1,702,761,530,251,060,000
379 1,812,356,499,739,470,000 1,814,060,171,624,690,000
380 1,930,656,072,350,460,000 1,932,478,915,720,990,000
381 2,056,513,475,336,630,000 2,058,463,596,496,840,000
382 2,190,401,332,423,760,000 2,192,487,374,066,330,000
383 2,332,821,198,543,890,000 2,335,052,374,987,350,000
384 2,484,305,294,265,410,000 2,486,691,427,602,110,000
385 2,645,418,340,688,760,000 2,647,969,900,547,130,000
386 2,816,759,503,217,940,000 2,819,487,647,630,880,000
387 2,998,964,447,736,450,000 3,001,881,067,996,670,000
388 3,192,707,518,433,530,000 3,195,825,285,280,280,000
389 3,398,704,041,358,160,000 3,402,036,455,563,610,000
390 3,617,712,763,867,600,000 3,621,274,208,413,110,000
391 3,850,538,434,667,420,000 3,854,344,231,777,640,000
392 4,098,034,535,626,590,000 4,102,101,005,688,210,000
393 4,361,106,170,762,280,000 4,365,450,696,609,950,000
394 4,640,713,124,699,620,000 4,645,354,218,123,350,000
395 4,937,873,096,788,190,000 4,942,830,470,972,180,000
396 5,253,665,124,416,970,000 5,258,959,768,984,820,000
397 5,589,233,202,595,400,000 5,594,887,465,213,220,000
398 5,945,790,114,707,870,000 5,951,827,785,731,630,000
399 6,324,621,482,504,290,000 6,331,067,886,881,070,000
400 6,727,090,051,741,040,000 6,733,972,144,452,060,000
401 7,154,640,222,653,940,000 7,161,986,692,184,490,000
402 7,608,802,843,339,870,000 7,616,644,219,256,550,000
403 8,091,200,276,484,460,000 8,099,569,045,897,860,000


I'm sure the estimate would become more accurate if I threw in more decimal places.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
August 25th, 2019 at 7:11:21 PM permalink
Quote: Wizard

I found a very good estimate for the P(n) if you know P(n-1).

Here it is

P(n) = P(n-1) * exp(0.923266 * n-0.448858)

{snip}

I'm sure the estimate would become more accurate if I threw in more decimal places.



I think you could come up with a more accurate version of this formula if you derived two different formulas: one each for even and odd values of n. If you use one formula, you should always tend to overestimate for odd n and underestimate for even n.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
August 25th, 2019 at 7:20:42 PM permalink
Quote: gordonm888

I think you could come up with a more accurate version of this formula if you derived two different formulas: one each for even and odd values of n. If you use one formula, you should always tend to overestimate for odd n and underestimate for even n.



Doesn't this odd and even effect diminish over time? I did some calculus to get at a direct formula. However, there is already a good formula for this. I'll put it in spoiler tags. I'll just say that it goes back to what I wrote earlier, that series seems to always come down to pi, e, and primes. I'll add to that the Fibonacci series.



P(n) = 1/(4n*sqrt(3)) * exp(pi * sqrt(2n/3))
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
August 25th, 2019 at 7:57:54 PM permalink
Quote: Wizard

Doesn't this odd and even effect diminish over time? I did some calculus to get at a direct formula. However, there is already a good formula for this. I'll put it in spoiler tags. I'll just say that it goes back to what I wrote earlier, that series seems to always come down to pi, e, and primes. I'll add to that the Fibonacci series.



P(n) = 1/(4n*sqrt(3)) * exp(pi * sqrt(2n/3))



I've looked at this only up from n=1 . . . 51. The odd/even effect definitely appears to get larger on an absolute basis but smaller on a % basis. At n=50,51 the P(n) for odd and even ns may be off by +/- 75, but the P(n) is >200,000 so as a % it is a small effect.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
Thanked by
Ajaxx
August 25th, 2019 at 8:14:27 PM permalink
Quote: Wizard

Let me put into a table, what you said, because I love tables. The third column represents the sum of partitions from 1 to n-1, for n. For examples, for n=5, it equals P(1)+ P(2) + P(3) + P(4). As Gordon said, this column equals one less than the number of pieces of size one in the partition of n.

n Partitions Sum from 1 to n-1 Size 1
1 1 0 1
2 2 1 2
3 3 3 4
4 5 6 7
5 7 11 12
6 11 18 19
7 15 29 30
8 22 44 45
9 30 66 67
10 42 96 97
11 56 138 139
12 77 194 195
13 101 271 272
14 135 372 373
15 176 507 508


Offhand, I can't think of why this is true.



Dang, I wrote out a long post on this, but the Internet was down and I lost it.

I'll just try to quickly rephrase the point. Let's let O(n) = Pieces of size 1 in the partitions of n.

As an example, consider O(5). We can tack on a one piece onto every partition of 4. However, the partitions of 4 already had some one pieces.

O(5) = P(4) + O(4).

To get O(4), we can tack on a one piece onto every partition of 3. However, the partitions of 3 already had some one pieces.

O(5) = P(4) + P(3) + O(3)

To get O(3), we can tack on a one piece onto every partition of 2. However, the partitions of 2 already had some one pieces.

O(5) = P(4) + P(3) + P(2) + O(2)

To get O(2), we can tack on a one piece onto every partition of 1. However, the partitions of 1 already had a single one piece.

O(5) = P(4) + P(3) + P(2) + P(1) + O(1) = P(4) + P(3) + P(2) + P(1) + 1 = 5 + 3 + 2 + 1 + 1 = 12
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
August 25th, 2019 at 10:11:34 PM permalink
What I have looked at is counting the number of partitions that don't have the numeral 1 in them. I call this Q(n) - the number of partitions without a "1"

n P(n), Partitions Q(n), Partitions without a "1" Running Sum of Q(n) =1
1 1 0 1
2 2 1 2
3 3 1 3
4 5 2 5
5 7 2 7
6 11 4 11
7 15 4 15
8 22 7 22
9 30 8 30
10 42 12 42
11 56 14 56
12 77 21 77
13 101 24 101
14 135 34 135
15 176 41 176
16 231 55 231


The column Q(n) is very interesting. Q(n) is equal to P(n) - P(n-1). Thus, calculating the sequence of Q(n) is equivalent to calculating the partitions P(n), because Q(n) is a generating function for P(n).

The sequence Q(n) does involve smaller numbers but will likely be as impossible to directly calculate as P(n).
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
August 25th, 2019 at 10:20:20 PM permalink
Quote: Wizard



Dang, I wrote out a long post on this, but the Internet was down and I lost it.

I'll just try to quickly rephrase the point. Let's let O(n) = Pieces of size 1 in the partitions of n.

As an example, consider O(5). We can tack on a one piece onto every partition of 4. However, the partitions of 4 already had some one pieces.

O(5) = P(4) + O(4).

To get O(4), we can tack on a one piece onto every partition of 3. However, the partitions of 3 already had some one pieces.

O(5) = P(4) + P(3) + O(3)

To get O(3), we can tack on a one piece onto every partition of 2. However, the partitions of 2 already had some one pieces.

O(5) = P(4) + P(3) + P(2) + O(2)

To get O(2), we can tack on a one piece onto every partition of 1. However, the partitions of 1 already had a single one piece.

O(5) = P(4) + P(3) + P(2) + P(1) + O(1) = P(4) + P(3) + P(2) + P(1) + 1 = 5 + 3 + 2 + 1 + 1 = 12



Nice proof.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Ajaxx
Ajaxx
  • Threads: 4
  • Posts: 36
Joined: Sep 15, 2019
October 23rd, 2019 at 8:21:20 AM permalink
This was really interesting to read through, and I wish I'd joined WoV early enough to chime in as it happened - apologies for instead disturbing a thread that's been laid to rest. This happens to be a topic I'm studying though, and trying to explain stuff like this always helps me understand it better. So, in case anyone is still interested, a couple of thoughts:

Quote: Wizard

Here are the Ramanujan identities.  Let P(x) = number of partitions of x.

P(5x + 4) is always divisible by 5
P(7x + 5) is always divisible by 7
P(11x + 6) is always divisible by 11

Here are a couple more that were discovered later:

P(17303x + 237) is always divisible by 13
P(206839x + 839) is always divisible by 17
P(1977147619x + 815655) is always divisible by 19

Makes you suspect there is another identity for the next prime, 23, but we haven't found it yet.

Actually, we have:  in 2012 Fredrik Johansson tabulated 22,474,608,014 of these identities (which we usually refer to as congruences) using the primes from 13 to 31. The simplest example for 23 is probably that p(14375n + 3474) is always divisible by 23. The mathematician who paved the way for that result, Ken Ono, was actually an associate producer of and the mathematical consultant for the film Wiz linked to in the OP; inspired by one of Ramanujan's unpublished manuscripts, he proved back in 2000 that there are an infinite number of congruences for every number that isn't a multiple of 2 or 3, including - starting with Ramanujan's original 5, 7, and 11 - the rest of the primes .

That original trio is still special though, because those numbers are each the period of their own cycles; that is, the interval between repeats (i.e. the number multiplied by x in all of Wiz's examples) is 5 for divisibility by 5, 7 for divisibility by 7, and 11 for divisibility by 11. Even more remarkably, Ramanujan himself was aware that you can get more congruences like that for any number that has 5, 7 and/or 11 as its only prime factors. For example, p(25n + 24) is always divisible by 25, p(49n + 47) is always divisible by 49, and p(55n + 39) is always divisible by 55. It turns out that all of these congruences including Ramanujan's original three are explained by a single rule: if the number m in the phrase "is always divisible by m" (which we call the modulus) is a product of only 5's, 7's and 11's, and the number n that you're partitioning is such that n×24 - 1 is divisible by m, then p(n) is always divisible by m. Notice that, since 24 is a multiple of 2 and 3, that can never happen when m is a multiple of either - that is related to the fact that 2 and 3 are the only primes without congruences.

These are the kinds of moments that make me love math: when you see a pattern that looks simple like 5n + 4, 7n + 5, 11n + 6, and just when you think you know what's going on (the next one has to be 13n + 7, right?) the underlying mechanism reveals itself to be deeper than you would ever have guessed. One of my favorite (albeit unrelated) examples of that kind of pattern is explained in an awesome trio of videos from what I think is by far the most artful math channel on YouTube, 3Blue1Brown.

As a side note: I know the post was months ago so no worries if you don't remember where you got this from, but did you mean P(206839x + 2623) is always divisible by 17 instead of P(206839x + 839)? If 839 was actually correct, I would love if you could include a link to your source, as it would be fascinating and weird if two different "phase shifts" worked for the same period of 206839.
"Not only [does] God play dice... he sometimes confuses us by throwing them where they can't be seen." ~ Stephen Hawking
Ajaxx
Ajaxx
  • Threads: 4
  • Posts: 36
Joined: Sep 15, 2019
October 23rd, 2019 at 8:34:24 AM permalink
Quote: Wizard

Damn Excel doesn't handle big numbers very well, so my sample size is rather small...

I think I'll add more code to check the factorization for larger numbers. I can handle numbers up to 2^64 in C++. Projects like this make me jealous of the people who have Mathematica.


I share that jealousy, but since the Mathematica price tag is sky high, I cannot recommend highly enough downloading the latest version of SageMath. Their mission is "Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab" and it doesn't disappoint: the built-in partition function, for example, spit out the first 10,000 partition numbers to exact precision for me in about one second.

Or, to keep it simpler, just code in Python: there is no limit to integer size, and as of Python 3 you don't even have to use a separate long type; the standard int can be arbitrarily big.
"Not only [does] God play dice... he sometimes confuses us by throwing them where they can't be seen." ~ Stephen Hawking
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26436
Joined: Oct 14, 2009
October 23rd, 2019 at 8:39:45 AM permalink
Thanks for joining the thread! I did know about those other congruences. Yes, this indeed is why I love math. There are so many mysteries like this. But funny how so many of them come back to primes.

As to my source, I don't remember. It is entirely possible I made a mistake. Can you quote your own source and I'll correct that post.

I shall check out those videos later, hopefully this evening.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Ajaxx
Ajaxx
  • Threads: 4
  • Posts: 36
Joined: Sep 15, 2019
Thanked by
gordonm888
October 23rd, 2019 at 8:51:01 AM permalink
Quote: Wizard

I took the analysis of how often total partitions are divisible by a prime number up to an initial quantity of 405. Here are the results.

Prime Count in 2 to 405 Ratio Expected
2 181 44.8% 50.0%
3 139 34.4% 33.3%
5 139 34.4% 20.0%
7 101 25.0% 14.3%
11 108 26.7% 9.1%
13 25 6.2% 7.7%
17 17 4.2% 5.9%
23 18 4.5% 4.3%
29 11 2.7% 3.4%


This shows a huge surplus of total partitions divisible by 5, 7, and 11, especially 11. You may recall these are the same primes in the Ramanujan identities. Very interesting...

The expected percentages in the last column of Wiz's table above would be correct if we knew nothing about the partition numbers, but once we take Ramanujan's congruences into account we know that, for example, every fifth number is 100% guaranteed to be divisible by 5. So, assuming the divisibility of the remaining four-fifths of the numbers is indeed random (i.e. has probability 20% or ⅕), we'd expect ⅕ + ⅘×⅕ = 9/25 = 36% to be divisible by 5, which is roughly what you see in the first 405 partition numbers. By similar reasoning, we'd expect (1/7) + (6/7)×(1/7) = 13/49 ≈ 26.53% to be divisible by 7, again consistent with the percentage in Wiz's table (the actual expected percentage is slightly more than 27% for reasons too complicated to get into here, but close enough).

11, though, can't be fully explained by Ramanujan's congruence. We'd expect (1/11) + (10/11)×(1/11) = 21/121 ≈ 17.355%, but the percentage is still 26.7% after 405 partition numbers. Before you get your hopes too high, the percentage of partition numbers that are multiples of 11 does eventually get arbitrarily close to 17.355%. But it takes an absurdly long time; to get within a percentage point you have to go all the way out to p(4594), which, to give you some perspective, is a 72-digit number, roughly as big as the number of individual atoms in the Milky Way galaxy. An effect which persists that long is clearly more than a fluke. So what's going on?

To answer that, a good first step, as always, is to generalize. Rather than the yes-or-no question of whether something is divisible by 11, it's more informative to ask what remainder a number produces when divided by 11 . If we get a remainder of 0, that number is divisible by 11 or, to use the jargon, it is "congruent to 0 (mod 11)". But if we get a remainder of, say, 4, rather than simply saying "this number is not divisible by 11," we can make the more precise statement that it is "congruent to 4 (mod 11)."

Below is a table of the first 660 partition numbers mod 11 — in other words, the cell for n contains the remainder you get when dividing p(n) by 11. It's a "periodic table" in the sense that, rather than listing all of the numbers out in one long row, it jumps to a new line every 11th number, which makes the table more compact and, more importantly, allows you to skip ahead 11 partition numbers at a time by simply moving straight down one of the columns. With things lined up in this way, Ramanujan's famous congruence, p(11n + 6) ≡ 0 (mod 11), shows up as the uninterrupted 0's in the column for k = 6. The partition numbers themselves (without the mod 11 operation applied) get huge very quickly and so aren't listed, but I included the first 11 at the very top as a reference/reminder of how the rest of the table is calculated. Note that p(0) = 1 because the 1 and only partition of 0 is the empty sum.


k 0 1 2 3 4 5 6 7 8 9 10
p(k) 1 1 2 3 5 7 11 15 22 30 42
p(k) mod 11 1 1 2 3 5 7 0 4 0 8 9
p(11 + k) mod 11 1 0 2 3 0 0 0 0 6 0 0
p(22 + k) mod 11 1 1 2 0 5 7 0 0 5 0 0
p(33 + k) mod 11 1 1 0 3 0 0 0 4 0 0 0
p(44 + k) mod 11 1 1 2 3 5 0 0 0 0 8 0
p(55 + k) mod 11 1 0 2 0 0 7 0 0 6 0 9
p(66 + k) mod 11 1 1 2 3 5 7 0 4 0 0 9
p(77 + k) mod 11 1 0 2 3 0 0 0 0 0 8 0
p(88 + k) mod 11 1 1 2 3 5 7 0 4 0 8 0
p(99 + k) mod 11 1 1 2 3 5 0 0 4 0 0 0
p(110 + k) mod 11 2 1 2 3 5 7 0 0 0 0 9
p(121 + k) mod 11 1 1 2 3 0 7 0 0 0 0 0
p(132 + k) mod 11 2 2 4 3 5 7 0 4 0 8 9
p(143 + k) mod 11 2 1 2 3 5 0 0 0 6 0 0
p(154 + k) mod 11 2 1 4 3 5 7 0 4 0 8 0
p(165 + k) mod 11 2 1 2 6 5 7 0 4 0 8 9
p(176 + k) mod 11 2 2 4 6 5 7 0 4 0 8 9
p(187 + k) mod 11 2 1 4 3 5 7 0 4 0 0 9
p(198 + k) mod 11 2 2 4 6 10 3 0 4 0 8 9
p(209 + k) mod 11 2 1 4 6 5 7 0 4 6 8 0
p(220 + k) mod 11 3 2 4 6 10 3 0 4 0 8 9
p(231 + k) mod 11 3 2 6 6 5 7 0 4 6 8 9
p(242 + k) mod 11 3 2 6 6 10 7 0 4 0 8 9
p(253 + k) mod 11 3 2 4 6 5 7 0 4 0 8 9
p(264 + k) mod 11 4 3 6 9 10 3 0 8 0 8 9
p(275 + k) mod 11 4 2 6 9 5 3 0 4 6 8 9
p(286 + k) mod 11 4 3 6 6 4 3 0 4 0 8 9
p(297 + k) mod 11 4 3 6 9 10 3 0 8 0 8 9
p(308 + k) mod 11 4 3 8 9 4 3 0 8 0 5 9
p(319 + k) mod 11 4 3 8 9 10 3 0 4 6 8 9
p(330 + k) mod 11 5 4 8 1 4 10 0 8 0 5 7
p(341 + k) mod 11 5 3 8 1 10 3 0 8 6 8 9
p(352 + k) mod 11 5 4 10 1 4 10 0 8 0 5 7
p(363 + k) mod 11 6 3 8 1 4 3 0 1 6 5 7
p(374 + k) mod 11 6 4 10 1 4 10 0 8 0 5 7
p(385 + k) mod 11 6 4 10 1 4 10 0 8 6 5 7
p(396 + k) mod 11 7 5 1 4 9 6 0 1 6 2 7
p(407 + k) mod 11 7 4 1 4 4 10 0 8 6 5 7
p(418 + k) mod 11 7 5 1 4 9 6 0 1 0 5 7
p(429 + k) mod 11 7 5 1 7 9 10 0 1 6 5 7
p(440 + k) mod 11 8 6 3 7 3 6 0 1 6 2 5
p(451 + k) mod 11 8 5 3 7 9 6 0 1 6 5 7
p(462 + k) mod 11 9 7 5 7 3 2 0 5 0 2 5
p(473 + k) mod 11 9 6 3 10 9 6 0 1 6 2 7
p(484 + k) mod 11 10 7 5 10 8 2 0 5 0 10 5
p(495 + k) mod 11 10 7 5 10 3 2 0 5 6 2 5
p(506 + k) mod 11 0 7 7 2 8 2 0 5 6 2 5
p(517 + k) mod 11 0 7 7 10 3 2 0 5 6 2 5
p(528 + k) mod 11 1 9 9 5 2 9 0 9 6 10 3
p(539 + k) mod 11 1 8 9 5 8 2 0 5 1 10 5
p(550 + k) mod 11 2 9 0 5 2 5 0 9 6 10 3
p(561 + k) mod 11 2 9 0 8 8 9 0 9 6 10 3
p(572 + k) mod 11 3 10 2 8 7 5 0 9 6 7 3
p(583 + k) mod 11 3 9 2 8 2 5 0 9 1 10 3
p(594 + k) mod 11 4 0 4 0 1 1 0 2 6 7 1
p(605 + k) mod 11 5 10 4 0 7 5 0 2 1 7 1
p(616 + k) mod 11 6 1 6 3 1 8 0 6 6 4 1
p(627 + k) mod 11 6 0 6 6 1 1 0 6 1 7 1
p(638 + k) mod 11 7 2 8 6 6 8 0 6 6 4 1
p(649 + k) mod 11 7 1 8 6 1 8 0 6 1 4 1



When I calculated 17.355% as the percentage of partition numbers that should be divisible by 11, I assumed that divisibility by 11 would be random for the numbers not covered under Ramanujan's congruence (i.e. all of the columns except the one starting with k = 6). The table above makes it clear that the other columns are anything but random; in fact, they reveal a deeper level of cycling going on here that is hidden by Ramanujan's special case. For example, when we consider every 11th partition number starting at k = 0, we get p(11n) ≡ 1 (mod 11) for the first ten numbers, but for the next ten it looks like p(11n) ≡ 2 (mod 11), and then the remainder shifts to 3, then 4, and so on. The remainder itself is cycling, with an increment of 1. You can see something similar happening for the other starting numbers; for k = 3, we start out with a remainder of 3 for a while, then 6, then 9, and then, since we're working in the mod 11 number system and can't have a remainder bigger than 10, we "wrap around" to 12 (mod 11) a.k.a. 1, and then 4 and then 7 and so on. We can even think of Ramanujan's special k = 6 column as having an increment of 0, meaning the remainder stays fixed.

It appears that, for every initial value k from 0 to 10, there is an associated increment by which the remainder is "allowed" to drift up and down as you move down that column through every 11th partition number. If as you can see in table, it looks like that the increment is always equal to the very first entry in each column! In other words,  the increments for the 11 columns are the first 11 partition numbers. Crazily enough, the same thing shows up if we do this analysis in the mod 5 number system (the increments for the five columns are 1, 1, 2, 3, and 0) and in mod 7 (the increments are 1, 1, 2, 3, 5, 0, and 4, where 4 is 11 mod 7).

If at this point your head is spinning from all these cycles that is more than understandable, but here is the upshot. It seems we so often get a remainder of zero when dividing these first partition numbers by 11 because, for two of the eleven "tracks" (the ones starting at p(6) = 11 and at p(8) = 22) we start off with a remainder of 0, and the matching increment of 0 means that that remainder tends to stay put and keep producing partition numbers divisible by 11. Meanwhile, for the other tracks, we start off with a nonzero remainder — 4, for example, in the case of p(7) = 15 — but since that number is also the increment by which the remainder is allowed to drift, 0 is always one step away: our only choices initially are to drift up to twice the remainder (4 + 4 = 8 in our example), or drift down to 0 (4 - 4 = 0). So for a while, 0 appears way more in our table than any other number, and only when these drifts become more frequent and more random (which you can start to see happening towards the bottom for all but Ramanujan's column) do we approach 17.355% divisibility. The effect is less pronounced for mod 5 and mod 7, which makes sense since only one of the "tracks" starts off with a remainder of 0 in those cases.

Of course, pointing out this underlying phenomenon and calling it an explanation is probably unfair: if you ask me why we get these drifting remainders, the best I could give you would be "math is mystifying." I hope someone much smarter than I am is working on a better answer.
Last edited by: Ajaxx on Oct 23, 2019
"Not only [does] God play dice... he sometimes confuses us by throwing them where they can't be seen." ~ Stephen Hawking
Ajaxx
Ajaxx
  • Threads: 4
  • Posts: 36
Joined: Sep 15, 2019
October 23rd, 2019 at 9:10:12 AM permalink
Quote: Wizard

Thanks for joining the thread!

Thank you for tolerating a very late post.

Quote: Wizard

As to my source, I don't remember. It is entirely possible I made a mistake. Can you quote your own source and I'll correct that post.

The p(206839n + 2623)≡ 0 (mod 17) congruence (which is more helpfully expressed as p(17×233×n + 2623) ≡ 0 (mod 17)) is mentioned on page 177 of George E. Andrews's The Theory of Partitions. It's a good read if you want to get deeper into this subject.

Quote: Wizard

I shall check out those videos later, hopefully this evening.


Let me know what you think!
"Not only [does] God play dice... he sometimes confuses us by throwing them where they can't be seen." ~ Stephen Hawking
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
October 23rd, 2019 at 1:57:10 PM permalink
Quote: Ajaxx


If at this point your head is spinning from all these cycles that is more than understandable, but here is the upshot. It seems we so often get a remainder of zero when dividing these first partition numbers by 11 because, for two of the eleven "tracks" (the ones starting at p(6) = 11 and at p(8) = 22) we start off with a remainder of 0, and the matching increment of 0 means that that remainder tends to stay put and keep producing partition numbers divisible by 11. Meanwhile, for the other tracks, we start off with a nonzero remainder — 4, for example, in the case of p(7) = 15 — but since that number is also the increment by which the remainder is allowed to drift, 0 is always one step away: our only choices initially are to drift up to twice the remainder (4 + 4 = 8 in our example), or drift down to 0 (4 - 4 = 0). So for a while, 0 appears way more in our table than any other number, and only when these drifts become more frequent and more random (which you can start to see happening towards the bottom for all but Ramanujan's column) do we approach 17.355% divisibility. The effect is less pronounced for mod 5 and mod 7, which makes sense since only one of the "tracks" starts off with a remainder of 0 in those cases.

Of course, pointing out this underlying phenomenon and calling it an explanation is probably unfair: if you ask me why we get these drifting remainders, the best I could give you would be "math is mystifying." I hope someone much smarter than I am is working on a better answer.



Another way to state your "mechanism" is to say that n=11 has higher than expected divisibility into the partition numbers p(k) because, when considering the more limited set of partition numbers p(k), k=0...(n-1) there are two numbers divisible by n (that is, in this case, divisible by 11.) I wonder how often this occurs, and whether other such values of n have greater than expected divisibility. For example, does 15 also divide into partition numbers an anomalously large number of times because p(7)=15 and p(9)=30 and those are both divisible by 15?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Ajaxx
Ajaxx
  • Threads: 4
  • Posts: 36
Joined: Sep 15, 2019
October 25th, 2019 at 9:55:30 AM permalink
Quote: gordonm888

Quote: Ajaxx


If at this point your head is spinning from all these cycles that is more than understandable, but here is the upshot. It seems we so often get a remainder of zero when dividing these first partition numbers by 11 because, for two of the eleven "tracks" (the ones starting at p(6) = 11 and at p(8) = 22) we start off with a remainder of 0, and the matching increment of 0 means that that remainder tends to stay put...


Another way to state your "mechanism" is to say that n=11 has higher than expected divisibility into the partition numbers p(k) because, when considering  the more limited set of partition numbers p(k), k=0...(n-1) there are two numbers divisible by n (that is, in this case, divisible by 11.)   I wonder how often this occurs, and whether other such values of n have greater than expected divisibility.  For example, does 15 also divide into partition numbers an anomalously large number of times because p(7)=15 and p(9)=30  and those are both divisible by 15?


That is a great question, and 15 is definitely the right example to test that theory with because there are actually three multiples of 15 among the first fifteen partition numbers: p(7) = 15, p(9) = 30 and p(14) = 135. As you can see from the additional tables below, though, you really do need both things in order for abnormally high divisibility to persist as long as it does with the modulus 11: luck (there happen to be slightly more multiples of n among the first n partition numbers than you'd expect) and staying power (the modulus has prime factors of only 5, 7 and 11, and so Ramanujan's congruence property applies and "stabilizes" what would otherwise be a somewhat random distribution of remainders).
  • The tables for mod 5 and mod 7 below show what happens when you have congruences but bad luck (i.e. no lucky second multiple in the first row). We have Ramanujan's unwavering column of zeroes, but the other columns start at small nonzero remainders that gradually drift with small nonzero increments. For some of the columns (see columns k=0 and k=1 in both tables) that actually means that it takes an usually long time for even a single 0 to appear, while others (like column k=6 in the mod 7 table) linger around 0 for a while before moving on. The overall effect is slightly less multiples than expected for mod 5 initially and slightly more for mod 7, but by the 180th partition number both of those effects have largely faded and we have 35.56% and 26.11% divisibility, respectively — only trivially different from the 36% and ~27.24% we expect.
  • Your example, a modulus of 15, shows what happens when you have the converse: luck without congruences. 20% of the numbers in the first row happen to be divisible by 15, but that turns out not to mean much because there is little regularity to how the remainder drifts as you move vertically down the columns from there. Of course, 15's prime factors are 3 and 5, the latter being a Ramanujan prime, so the congruences are not entirely absent from this table; because p(5n + 4) is guaranteed to be divisible by 5, in the columns for k=4, 9 and 14 we can only get remainders that are divisible by 5, i.e. 0, 5, or 10. In other words, we expect not 1 out of 15 numbers (6.67%) in this table to be divisible by 15, but (3/15)×(1/3) + (12/15)×(1/15) = 27/225 = 3/25 = 12%, since there is a 1 out of 3 chance of divisibility in those three special columns and the normal 1 out of 15 chance in the remaining twelve (we get the same number by reasoning that a third of numbers divisible by 5 should be divisible by 15, and we calculated that 36% of partition numbers should be divisible by 5). The actual fraction does indeed approach 12% asymptotically from below as you can see in this chart, mirroring the fact that we approach 36% from below in the case of mod 5 but with additional noise thrown in from the random distribution of multiples of 3.



k 0 1 2 3 4
p(k) 1 1 2 3 5
p(k) mod mod 5 1 1 2 3 0
p(5 + k) mod mod 5 2 1 0 2 0
p(10 + k) mod mod 5 2 1 2 1 0
p(15 + k) mod mod 5 1 1 2 0 0
p(20 + k) mod mod 5 2 2 2 0 0
p(25 + k) mod mod 5 3 1 0 3 0
p(30 + k) mod mod 5 4 2 4 3 0
p(35 + k) mod mod 5 3 2 2 0 0
p(40 + k) mod mod 5 3 3 4 1 0
p(45 + k) mod mod 5 4 3 4 3 0
p(50 + k) mod mod 5 1 3 4 1 0
p(55 + k) mod mod 5 1 3 4 0 0
p(60 + k) mod mod 5 2 0 1 4 0
p(65 + k) mod mod 5 3 0 4 0 0
p(70 + k) mod mod 5 3 0 3 4 0
p(75 + k) mod mod 5 4 1 3 4 0
p(80 + k) mod mod 5 1 2 0 4 0
p(85 + k) mod mod 5 2 2 3 4 0
p(90 + k) mod mod 5 3 4 2 2 0
p(95 + k) mod mod 5 4 4 0 1 0
p(100 + k) mod mod 5 2 1 4 0 0
p(105 + k) mod mod 5 4 1 4 4 0
p(110 + k) mod mod 5 1 3 1 3 0
p(115 + k) mod mod 5 1 3 1 3 0
p(120 + k) mod mod 5 0 1 2 1 0
p(125 + k) mod mod 5 2 2 0 0 0
p(130 + k) mod mod 5 0 4 4 2 0
p(135 + k) mod mod 5 1 0 1 1 0
p(140 + k) mod mod 5 0 3 0 2 0
p(145 + k) mod mod 5 4 4 3 2 0
p(150 + k) mod mod 5 3 2 1 4 0
p(155 + k) mod mod 5 2 4 4 2 0
p(160 + k) mod mod 5 1 2 2 0 0
p(165 + k) mod mod 5 0 4 2 1 0
p(170 + k) mod mod 5 0 3 3 0 0
p(175 + k) mod mod 5 0 0 0 0 0
p(180 + k) mod mod 5 1 1 3 2 0
p(185 + k) mod mod 5 2 3 3 1 0
p(190 + k) mod mod 5 3 2 3 4 0
p(195 + k) mod mod 5 3 1 0 3 0
p(200 + k) mod mod 5 3 2 3 3 0
p(205 + k) mod mod 5 0 0 0 2 0
p(210 + k) mod mod 5 0 2 4 3 0
p(215 + k) mod mod 5 2 1 4 1 0
p(220 + k) mod mod 5 2 4 1 0 0
p(225 + k) mod mod 5 2 4 0 2 0
p(230 + k) mod mod 5 0 2 2 4 0
p(235 + k) mod mod 5 4 2 1 2 0
p(240 + k) mod mod 5 3 3 4 3 0
p(245 + k) mod mod 5 1 4 1 2 0
p(250 + k) mod mod 5 1 4 4 2 0
p(255 + k) mod mod 5 0 2 2 1 0
p(260 + k) mod mod 5 1 4 3 0 0
p(265 + k) mod mod 5 2 2 4 0 0
p(270 + k) mod mod 5 2 1 3 0 0
p(275 + k) mod mod 5 0 1 4 4 0
p(280 + k) mod mod 5 1 1 3 0 0
p(285 + k) mod mod 5 2 3 3 2 0
p(290 + k) mod mod 5 1 4 2 0 0
p(295 + k) mod mod 5 3 1 4 0 0




k 0 1 2 3 4 5 6
p(k) 1 1 2 3 5 7 11
p(k) mod mod 7 1 1 2 3 5 0 4
p(7 + k) mod mod 7 1 1 2 0 0 0 3
p(14 + k) mod mod 7 2 1 0 3 0 0 4
p(21 + k) mod mod 7 1 1 2 0 5 0 0
p(28 + k) mod mod 7 1 1 4 3 5 0 4
p(35 + k) mod mod 7 1 1 0 3 0 0 0
p(42 + k) mod mod 7 2 2 2 3 5 0 0
p(49 + k) mod mod 7 2 1 4 0 0 0 0
p(56 + k) mod mod 7 3 2 2 3 5 0 4
p(63 + k) mod mod 7 2 2 2 3 5 0 4
p(70 + k) mod mod 7 3 2 4 6 5 0 0
p(77 + k) mod mod 7 2 2 4 3 5 0 0
p(84 + k) mod mod 7 3 3 6 6 3 0 1
p(91 + k) mod mod 7 3 3 4 3 5 0 0
p(98 + k) mod mod 7 4 3 4 6 5 0 1
p(105 + k) mod mod 7 5 3 6 6 3 0 0
p(112 + k) mod mod 7 5 4 6 6 3 0 4
p(119 + k) mod mod 7 5 4 6 6 5 0 0
p(126 + k) mod mod 7 6 5 1 2 3 0 1
p(133 + k) mod mod 7 5 5 1 6 3 0 4
p(140 + k) mod mod 7 0 5 1 5 1 0 1
p(147 + k) mod mod 7 0 6 3 2 1 0 4
p(154 + k) mod mod 7 1 6 3 5 1 0 1
p(161 + k) mod mod 7 1 6 3 2 1 0 1
p(168 + k) mod mod 7 2 1 0 1 6 0 5
p(175 + k) mod mod 7 2 1 0 5 1 0 4
p(182 + k) mod mod 7 4 2 5 1 6 0 1
p(189 + k) mod mod 7 4 2 0 1 6 0 1
p(196 + k) mod mod 7 6 3 4 4 4 0 5
p(203 + k) mod mod 7 6 3 2 4 6 0 1
p(210 + k) mod mod 7 1 5 4 0 2 0 2
p(217 + k) mod mod 7 1 5 6 4 4 0 1
p(224 + k) mod mod 7 3 0 1 3 2 0 6
p(231 + k) mod mod 7 3 0 1 0 0 0 5
p(238 + k) mod mod 7 5 1 5 6 0 0 2
p(245 + k) mod mod 7 5 2 5 6 0 0 2
p(252 + k) mod mod 7 1 4 2 5 3 0 6
p(259 + k) mod mod 7 2 4 2 2 5 0 2
p(266 + k) mod mod 7 4 6 2 1 3 0 3
p(273 + k) mod mod 7 4 0 6 5 1 0 6
p(280 + k) mod mod 7 0 2 3 0 6 0 0
p(287 + k) mod mod 7 1 3 3 4 1 0 6
p(294 + k) mod mod 7 5 5 0 3 4 0 4
p(301 + k) mod mod 7 5 6 4 0 4 0 6
p(308 + k) mod mod 7 2 1 4 2 0 0 1
p(315 + k) mod mod 7 3 3 1 2 0 0 0
p(322 + k) mod mod 7 6 5 5 1 5 0 1
p(329 + k) mod mod 7 1 6 5 1 5 0 4
p(336 + k) mod mod 7 4 3 4 3 6 0 2
p(343 + k) mod mod 7 6 4 1 0 1 0 1
p(350 + k) mod mod 7 4 0 3 5 4 0 6
p(357 + k) mod mod 7 5 2 2 2 2 0 5
p(364 + k) mod mod 7 2 5 1 4 5 0 3
p(371 + k) mod mod 7 4 0 1 4 5 0 2
p(378 + k) mod mod 7 2 4 2 2 6 0 4
p(385 + k) mod mod 7 5 6 6 6 6 0 3
p(392 + k) mod mod 7 4 3 5 4 2 0 5
p(399 + k) mod mod 7 6 6 2 4 0 0 4
p(406 + k) mod mod 7 5 3 1 2 3 0 2
p(413 + k) mod mod 7 0 5 5 2 1 0 5




k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
p(k) 1 1 2 3 5 7 11 15 22 30 42 56 77 101 135
p(k) mod mod 15 1 1 2 3 5 7 11 0 7 0 12 11 2 11 0
p(15 + k) mod mod 15 11 6 12 10 10 12 12 12 10 0 8 6 10 13 5
p(30 + k) mod mod 15 9 2 9 3 10 3 7 7 5 0 3 3 14 6 10
p(45 + k) mod mod 15 4 3 14 3 5 1 3 9 6 10 1 8 9 5 10
p(60 + k) mod mod 15 2 0 1 9 10 8 5 14 0 5 3 0 13 4 5
p(75 + k) mod mod 15 9 11 13 14 5 6 7 10 14 5 2 7 8 9 10
p(90 + k) mod mod 15 8 4 2 2 5 4 14 0 1 10 7 11 9 5 0
p(105 + k) mod mod 15 14 6 9 14 5 1 3 1 13 5 6 13 1 13 10
p(120 + k) mod mod 15 5 11 7 11 0 12 2 5 10 0 5 14 14 12 10
p(135 + k) mod mod 15 11 5 1 6 10 10 8 0 7 5 14 4 3 7 10
p(150 + k) mod mod 15 13 12 1 14 10 7 14 4 7 5 6 7 12 0 0
p(165 + k) mod mod 15 5 4 2 1 0 10 8 8 0 5 10 10 10 0 10
p(180 + k) mod mod 15 6 6 13 2 10 2 13 8 1 0 8 12 8 9 5
p(195 + k) mod mod 15 3 6 10 3 0 3 2 3 8 10 5 5 0 12 0
p(210 + k) mod mod 15 5 12 14 13 0 7 1 4 11 5 12 9 6 0 5
p(225 + k) mod mod 15 12 9 5 7 5 5 12 12 4 10 4 2 11 12 0
p(240 + k) mod mod 15 3 8 14 13 10 1 14 11 2 0 6 14 14 7 10
p(255 + k) mod mod 15 5 2 12 11 0 11 14 13 10 10 2 12 9 0 5
p(270 + k) mod mod 15 12 11 13 5 10 10 11 9 9 5 11 6 13 10 0
p(285 + k) mod mod 15 2 3 8 12 0 6 14 7 10 5 8 6 9 0 5
p(300 + k) mod mod 15 7 6 4 14 0 14 10 9 8 10 4 10 1 2 0
p(315 + k) mod mod 15 1 3 14 4 0 7 1 6 8 5 11 4 4 5 5
p(330 + k) mod mod 15 9 5 4 13 10 10 12 2 5 0 12 0 9 8 10
p(345 + k) mod mod 15 4 14 0 6 5 12 6 14 3 0 13 2 12 0 10
p(360 + k) mod mod 15 1 9 11 9 10 9 14 2 14 0 2 2 0 0 0
p(375 + k) mod mod 15 14 11 1 5 10 7 0 6 1 10 11 2 4 1 10
p(390 + k) mod mod 15 8 11 6 4 0 10 3 8 12 0 11 11 9 11 5
p(405 + k) mod mod 15 12 14 11 14 10 2 12 9 8 10 9 14 2 4 5
p(420 + k) mod mod 15 14 11 6 4 0 4 14 9 14 0 8 14 6 5 0
p(435 + k) mod mod 15 11 5 10 7 5 13 5 1 2 10 14 6 4 14 0
p(450 + k) mod mod 15 10 9 8 5 10 8 4 4 7 10 6 10 1 12 10
p(465 + k) mod mod 15 9 9 13 12 5 12 4 3 8 5 5 11 3 7 5
p(480 + k) mod mod 15 6 5 5 14 5 7 8 13 1 10 13 4 7 8 0
p(495 + k) mod mod 15 2 6 12 8 0 12 6 11 5 10 2 2 6 6 5
p(510 + k) mod mod 15 5 7 3 7 5 1 8 10 10 5 8 6 3 1 0
p(525 + k) mod mod 15 11 13 6 1 10 10 12 13 2 5 9 3 4 14 10
p(540 + k) mod mod 15 6 13 3 5 10 14 2 1 6 5 0 2 9 12 10
p(555 + k) mod mod 15 1 8 11 2 0 2 1 9 4 10 12 9 11 3 5
p(570 + k) mod mod 15 3 1 12 6 5 6 13 8 10 0 0 8 7 7 5
p(585 + k) mod mod 15 14 11 6 8 10 2 7 13 7 5 2 10 14 12 10
p(600 + k) mod mod 15 2 4 12 7 5 14 7 14 12 10 1 2 5 5 10
p(615 + k) mod mod 15 14 4 9 12 0 4 11 14 11 0 11 9 14 1 10
p(630 + k) mod mod 15 14 14 6 12 10 5 6 9 9 5 14 14 2 14 5
p(645 + k) mod mod 15 3 13 5 9 0 5 5 6 14 0 12 14 9 2 0



There are bigger numbers than 11 which satisfy both conditions, but since Ramanujan's congruences only apply when the factors of the modulus are limited to 5's, 7's and 11's, all of them are composite numbers made up of those constituent parts. There are 6 multiples of 55 among the first 55 partition numbers, for example, with the congruence being that p(55n + 39) is always divisible by 55; likewise, there are 10 multiples of 77 among the first 77 partition numbers, and p(77n + 61) is always divisible by 77. The longer periods and intermingling of multiple prime factors means that for these, much like the mod 15 table above, we don't see clean patterns in any of the columns besides the column of zeroes for the congruence itself, and the periodic tables aren't really worth looking at. But since being divisible by, say, 55 requires being divisible by 5 and 11, the initial percentage of multiples for these is essentially a blending of the individual effects described above, where factors of 11 inflate the divisibility for a while, 7's briefly inflate divisibility, and 5's briefly suppress it. I included 55 and 121 in the chart as examples.

With all that being said, I am probably guilty of missing the point by spending so many words in this post and the last trying to explain when we do and do not see a lot of multiples among the partition numbers for a particular modulus. I did so because I wanted to come full circle by returning to Wiz's table of percentages and the observation of increased divisibility that led us down this path in the first place, but, as so often happens in math it seems like, our inroad was more of a happy coincidence that allowed us to glimpse something subtle and start poking around in interesting places in the search for an explanation. Ultimately, I think the coincidence that 11 happens to have an extra multiple which amplifies its divisibility more than 5 and 7 is less significant than the fact that for all three of those primes, there is a regular pattern in all the columns, not just the ones corresponding to Ramanujan's congruence.
"Not only [does] God play dice... he sometimes confuses us by throwing them where they can't be seen." ~ Stephen Hawking
  • Jump to: