How many different tuples of positive integers sum to 42? Well there’s the singleton {42}, and then (41, 1) and then (40,2) and (40,1,1}. . . and finally (1,1, . . .,1} (forty two 1s}. The answer is
In[]:=
PartitionsP@42
Out[]=
53174
We could actually enumerate them via
In[]:=
IntegerPartitions[42][[{1,2,3,0,0,0,-3,-2,-1}]]
{{42},{41,1},{40,2},List,List,List,{2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}
How can we tell if Mathematica actually generated all 53174 when we just asked how many? Ask for too many!
In[]:=
PartitionsP@1234//Timing
Out[]=
{0.027075,156978797223733228787865722354959930}
IntegerName[%[[2]]]//Timing
Out[]=
{0.000911,156 decillion 978 nonillion 797 octillion 223 septillion 733 sextillion 228 quintillion 787 quadrillion 865 trillion 722 billion 354 million 959 thousand 930}
So it “counted” 156 decillion partitions in 27 millisecond.. When, by Moore’s law, could this actually happen?
So Mathematica has a formula. An amazingly hairy formula. “https://en.wikipedia.org/wiki/Partition_function_(number_theory)”, found by Ramanujan, Hardy, and Rademacher. R and H were only hoping for an asymptotic approximation, like Stirling’s approximation for large factorial. But one of them, probably Ramanujan, had the unearthly idea to replace n by n-1/24 in a couple of places, even though n is an integer! This so improved the accuracy of the formula that it could be made exact simply by taking the nearest integer to where it oscillated least! If n-1/24 was Ramanujan’s brainstorm, it would help explain why Hardy held him in such awe. Then, to ice the cake, Rademacher changed an e^x into 2 sinh x, and the bleeping series converges! To the exact right integer! This has to be one of the high water marks of Mathematical Analysis.
So Mathematica has a formula. An amazingly hairy formula. “https://en.wikipedia.org/wiki/Partition_function_(number_theory)”, found by Ramanujan, Hardy, and Rademacher. R and H were only hoping for an asymptotic approximation, like Stirling’s approximation for large factorial. But one of them, probably Ramanujan, had the unearthly idea to replace n by n-1/24 in a couple of places, even though n is an integer! This so improved the accuracy of the formula that it could be made exact simply by taking the nearest integer to where it oscillated least! If n-1/24 was Ramanujan’s brainstorm, it would help explain why Hardy held him in such awe. Then, to ice the cake, Rademacher changed an e^x into 2 sinh x, and the bleeping series converges! To the exact right integer! This has to be one of the high water marks of Mathematical Analysis.
To avert boredom, let’s avoid . . ., 1,1,1, . . . by counting distinct (no repeats) partitions.
In[]:=
PartitionsQ@42
Out[]=
1426
But to actually see these, we have to write our own
In[]:=
Clear@distinctPartitions;distinctPartitions@n_Integer:=Select[IntegerPartitions@n,UnsameQ@@#&]
In[]:=
distinctPartitions[42][[{1,2,3,0,0,0,-3,-2,-1}]]
Out[]=
{{42},{41,1},{40,2},List,List,List,{10,8,7,6,5,3,2,1},{9,8,7,6,5,4,3},{9,8,7,6,5,4,2,1}}
Now suppose instead of distinctpartitions, we consider partitions into exclusively odd integers. Unattractively, this reopens the door to . . ., 1,1,1, . . . , but with a nice surprise.
In[]:=
allOdd[L_List]:={}Select[L,EvenQ,1]
In[]:=
oddPartitions@n_Integer:=Select[IntegerPartitions@n,allOdd]
In[]:=
oddPartitions@7
Out[]=
{{7},{5,1,1},{3,3,1},{3,1,1,1,1},{1,1,1,1,1,1,1}}
Compare the oddPartitions@7 with the distinctPartitions@7:
In[]:=
Transpose[{distinctPartitions@7,oddPartitions@7}]//MatrixForm
Out[]//MatrixForm=
{7} | {7} |
{6,1} | {5,1,1} |
{5,2} | {3,3,1} |
{4,3} | {3,1,1,1,1} |
{4,2,1} | {1,1,1,1,1,1,1} |
Five of each. Probably a coincidence. Try partitioning 8:
In[]:=
Transpose[{distinctPartitions@8,oddPartitions@8}]//MatrixForm
Out[]//MatrixForm=
{8} | {7,1} |
{7,1} | {5,3} |
{6,2} | {5,1,1,1} |
{5,3} | {3,3,1,1} |
{5,2,1} | {3,1,1,1,1,1} |
{4,3,1} | {1,1,1,1,1,1,1,1} |
Do you suppose . . .?
In[]:=
Transpose[{distinctPartitions@9,oddPartitions@9}]//MatrixForm
Out[]//MatrixForm=
{9} | {9} |
{8,1} | {7,1,1} |
{7,2} | {5,3,1} |
{6,3} | {5,1,1,1,1} |
{6,2,1} | {3,3,3} |
{5,4} | {3,3,1,1,1} |
{5,3,1} | {3,1,1,1,1,1,1} |
{4,3,2} | {1,1,1,1,1,1,1,1,1} |
I dare it to last through 42.
oddPartitions@42//tim
0.101981,1426
Sound familiar? There are probably a dozen proofs that odd and distinct partitions are equinumerous. Some very easy, some very cool. Give it a whack. And say goodbye to easy. And say Hello again to Ramanujan, who,
for some reason, counted the partitions where all the parts differ by at least 2:
for some reason, counted the partitions where all the parts differ by at least 2:
In[]:=
twoapart[L_List]:=Min[Abs@Differences@L]>1
In[]:=
twoapartitions@n_Integer:=Select[IntegerPartitions@n,twoapart]
In[]:=
twoapartitions@22
Out[]=
{{22},{21,1},{20,2},{19,3},{18,4},{18,3,1},{17,5},{17,4,1},{16,6},{16,5,1},{16,4,2},{15,7},{15,6,1},{15,5,2},{14,8},{14,7,1},{14,6,2},{14,5,3},{13,9},{13,8,1},{13,7,2},{13,6,3},{13,5,3,1},{12,10},{12,9,1},{12,8,2},{12,7,3},{12,6,4},{12,6,3,1},{11,9,2},{11,8,3},{11,7,4},{11,7,3,1},{11,6,4,1},{10,8,4},{10,8,3,1},{10,7,5},{10,7,4,1},{10,6,4,2},{9,7,5,1},{9,7,4,2}}
In[]:=
(twoapartitions[42]//tim)[[{1,2,3,0,0,0,-3,-2,-1}]]
0.23749,465
Out[]=
{{42},{41,1},{40,2},List,List,List,{13,11,8,6,3,1},{13,10,8,6,4,1},{12,10,8,6,4,2}}
There were 465 ways to so partition 42. Then he decided to count partitions into parts whose squares are 1 mod 5.
In[]:=
ppeq1mod5@L_List:={1}==Union[Mod[L^2,5]]
In[]:=
ppeq1mod5@{1,4,6,9,11,14,16}
Out[]=
True
In[]:=
ppeq1mod5@{1,4,6,9,11,14,16,17}
Out[]=
False
In[]:=
pp1partitions@n_Integer:=Select[IntegerPartitions@n,ppeq1mod5]
In[]:=
(pp1partitions[42]//tim)[[{1,2,3,0,0,0,-3,-2,-1}]]
0.463081,465
Out[]=
{{41,1},{39,1,1,1},{36,6},List,List,List,{4,4,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{4,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}
Did somebody mention 465? Probably just a coincidence. Maybe Ramanujan could get a different answer from distinct partitions where every even part exceeds twice the number of odd parts.
In[]:=
eeven[L_List]:=Min[Select[L,EvenQ]]>2Count[L,n_/;OddQ@n]
In[]:=
eevenpartitions[n_Integer]:=Select[distinctPartitions@n,eeven]
In[]:=
(eevenpartitions[42]//tim)[[{1,2,3,0,0,0,-3,-2,-1}]]
0.081661,465
Out[]=
{{42},{41,1},{40,2},List,List,List,{12,9,8,7,6},{11,10,9,7,5},{11,10,8,7,6}}
And not even this is the worst! Wait until you see the partition-theoretic consequences of the identity
In[]:=
1(QPochhammer[,]QPochhammer[,]QPochhammer[,]QPochhammer[,])1+(QPochhammer[x,]QPochhammer[,]QPochhammer[,]QPochhammer[,])
2
x
5
x
3
x
5
x
11
x
55
x
44
x
55
x
2
x
5
x
4
x
5
x
22
x
55
x
33
x
55
x
Out[]=
1
(;)
2
x
5
x
∞
(;)
3
x
5
x
∞
(;)
11
x
55
x
∞
(;)
44
x
55
x
∞
2
x
(x;)
5
x
∞
(;)
4
x
5
x
∞
(;)
22
x
55
x
∞
(;)
33
x
55
x
∞
In[]:=
Series[%,{x,0,465}]
Out[]=
True
Fear Ramanujan.
Utility
Utility
tim[xp_]:=(Print[#[[1]],",",Length[#[[2]]]];#[[2]])&@AbsoluteTiming[xp](*tim is my identity function that interjects elapsed time and length.*)SetAttributes[tim,HoldAll];