Message Boards

GROUPS:

Bill Gosper

Formidable Ramanjujan formulas: tuples, partitions, and integers sums

Bill Gosper, Home

Posted 16 days ago

209 Views

1 Reply

10 Total Likes

Follow this post

Formidable Ramanjujan formulas: tuples, partitions, and integers sums
by Bill Gosper

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.

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:

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[

])1+

(QPochhammer[x,

]QPochhammer[

])

Out[]=

(

;

)

∞

(

;

)

∞

(

;

)

∞

(

;

)

∞



(x;

)

∞

(

;

)

∞

(

;

)

∞

(

;

)

∞

In[]:=

Series[%,{x,0,465}]

Out[]=

True

Fear Ramanujan.

Utility

tim[xp_]:=(Print[#[[1]],",",Length[#[[2]]]];#[[2]])&@AbsoluteTiming[xp](*tim is my identity function that interjects elapsed time and length.*)SetAttributes[tim,HoldAll];

POSTED BY: Bill Gosper

Answer

1 Reply

Sort By:

Moderation Team

Moderation Team, WOLFRAM

Posted 16 days ago

-- you have earned *Featured Contributor Badge* Your exceptional post has been selected for our editorial column *Staff Picks* http://wolfr.am/StaffPicks and Your Profile is now distinguished by a *Featured Contributor Badge* and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team

Answer

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback

Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how »