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

Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1332
  • Posts: 21923
Thanks for this post from:
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
It's not whether you win or lose; it's whether or not you had a good bet.
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 38
  • Posts: 2563
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, were dead. And a thousand thousand slimy things lived on, and so did I.
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 38
  • Posts: 2563
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, were dead. And a thousand thousand slimy things lived on, and so did I.
Ajaxx
Ajaxx
Joined: Sep 15, 2019
  • Threads: 4
  • Posts: 36
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
Joined: Sep 15, 2019
  • Threads: 4
  • Posts: 36
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
Joined: Oct 14, 2009
  • Threads: 1332
  • Posts: 21923
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.
It's not whether you win or lose; it's whether or not you had a good bet.
Ajaxx
Ajaxx
Joined: Sep 15, 2019
  • Threads: 4
  • Posts: 36
Thanks for this post from:
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
Joined: Sep 15, 2019
  • Threads: 4
  • Posts: 36
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
gordonm888
Joined: Feb 18, 2015
  • Threads: 38
  • Posts: 2563
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, were dead. And a thousand thousand slimy things lived on, and so did I.
Ajaxx
Ajaxx
Joined: Sep 15, 2019
  • Threads: 4
  • Posts: 36
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: