Partition function (number theory): Difference between revisions

Revision as of 21:36, 15 February 2023

Revision as of 10:36, 12 March 2023

Line 24:

{{As of|2022|June}}, the largest known [[prime number]] among the values of {{math|''p''(''n'')}} is {{math|''p''(1289844341)}}, with 40,000 decimal digits.{{r|caldwell}}<ref>{{citation |title=PrimePage Primes: p(1289844341) |url=https://primes.utm.edu/primes/page.php?id=130336 |website=primes.utm.edu |access-date=30 June 2022}}</ref> Until March 2022, this was also the largest prime that has been proved using [[elliptic curve primality proving]].<ref>{{citation |title=The Top Twenty: Elliptic Curve Primality Proof |url=https://primes.utm.edu/top20/page.php?id=27 |website=primes.utm.edu |access-date=30 June 2022}}</ref>

== Generating function==

[[File:Euler_partition_function.svg|thumb|upright|link={{filepath:Euler_partition_function.svg}}|Using Euler's method to find {{math|''p''(40)}}: A ruler with plus and minus signs (grey box) is slid downwards, the relevant terms added or subtracted. The positions of the signs are given by differences of alternating natural (blue) and odd (orange) numbers. In [{{filepath:Euler_partition_function.svg}} the SVG file,] hover over the image to move the ruler.]]

{{main|Pentagonal number theorem}}

Line 68:

For instance the number of partitions is divisible by five whenever the decimal representation of <math>n</math> ends in the digit 4 or 9, as expressed by the congruence{{r|hw}}

<math display="block">p(5k+4) \equiv 0 \pmod 5</math>

For instance, the number of partitions for the integer 4 is 5.

For the integer 9, the number of partitions is 30; for 14 there are 135 partitions. This congruence is implied by the more general identity

<math display="block"> \sum_{k=0}^\infty p(5k+4)x^k = 5~ \frac{ (x^5)^5_\infty } {(x)^6_\infty},</math>

Line 224:

=== Gaussian binomial coefficient ===

If we denote <math>p(N, M, n)</math> the number of partitions of ''n'' in at most ''M'' parts, with each part smaller or equal to ''N'', then the generating function of <math>p(N, M, n)</math> is the following [[Gaussian binomial coefficient|Gaussian binomial coefficient]]:

:<math>\sum_{n=0}^\infty p(N, M, n)q^n = {N+M \choose M}_q

=

\frac{(1-q^{N+M})(1-q^{N+M-1})\cdots(1-q^{N+1})} {(1-q)(1-q^2)\cdots(1-q^M)}</math>