Skip to content

PartitionsQ

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

PartitionsQ[n]

gives the number q(n) of partitions of the integer n into distinct parts -- equal, by Euler's theorem, to the number of partitions into odd parts.

Notes n must be an integer; q(n) = 0 for n \< 0. Threads over lists. For the partitions themselves use IntegerPartitions.

Examples (6)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (3)

In[1]:= Table[PartitionsQ[k], {k, 0, 20}]
Out[1]= {1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64}

In[2]:= PartitionsQ[100]
Out[2]= 444793

In[3]:= PartitionsQ[{2, 4, 6}]
Out[3]= {1, 2, 4}

Worked examples (1)

In[4]:= PartitionsQ[{2, 4, 6}]
Out[4]= {1, 2, 4}

Applications (2)

In[5]:= PartitionsQ[10]
Out[5]= 10

In[6]:= PartitionsQ[6]
Out[6]= 4

Algorithm

partitions.c — IntegerPartitions

A faithful, efficient recreation of the Wolfram-Language IntegerPartitions. The whole surface collapses onto a single count-vector enumerator over an ordered set of allowed parts, run with exact GMP rational arithmetic so that integers, big integers, rationals and negative values are all handled by the same code path.

Forms:

  IntegerPartitions[n]                     all partitions of n
  IntegerPartitions[n, k]                  into at most k parts
  IntegerPartitions[n, {k}]                into exactly k parts
  IntegerPartitions[n, {kmin, kmax}]       between kmin and kmax parts
  IntegerPartitions[n, {kmin, kmax, dk}]   kmin, kmin+dk, ... parts
  IntegerPartitions[n, kspec, sspec]       parts drawn only from sspec
  IntegerPartitions[n, kspec, sspec, m]    first m (m>0) or last |m| (m<0)

n and the s_i may be rational and/or negative. Results are in reverse lexicographic order; within a partition the parts appear in the order of the reversed sspec (descending for the default Range[n]).

Ownership: this builtin only reads res. On every NULL return (bad arguments, ::undef, symbolic input) the evaluator keeps res unevaluated.

Implementation notes

Algorithm. builtin_partitionsq returns q(n), the number of partitions of n into distinct parts (equivalently, into odd parts; OEIS A000009), with the same size dispatch as PartitionsP at a threshold of n = 1000. Below it, partitionsq_recurrence applies an exact GMP recurrence derived from prod(1 - x^k) Q(x) = prod(1 - x^(2k)): the same generalized-pentagonal homogeneous sum as p(n), plus an inhomogeneous term r(m) = (-1)^k whenever m is even and m/2 is a generalized pentagonal number of index k. At or above it, partitionsq_hrr evaluates the Hardy–Ramanujan–Rademacher / Hagis convergent series in MPFR, q(n) = (pi/sqrt(24n+1)) sum_(k odd) (1/k) A_k(n) I_1(pi sqrt(48n+2)/(12k)), where A_k(n) is a Dedekind-sum character sum and I_1 is the modified Bessel function summed from its everywhere-positive power series.

Data structures. The recurrence uses a table of n+1 mpz_t; the HRR path works in mpfr_t at ~pi sqrt(n/3)/ln2 + 96 bits, and the Dedekind sums s(h, k) are computed exactly in mpq_t by O(log k) reciprocity. The result is an Integer/BigInt. There is no ND/packed/Compile path, and PartitionsQ is Listable, threaded by the evaluator.

Complexity / limits. The recurrence is O(n^1.5) time and O(n sqrt n) bits. The Hagis series has no clean closed-form remainder bound, so termination is convergence-driven: the rounding is accepted only when the sum lies within 1/4 of an integer and the last term is below 1/8 (so the unsummed tail cannot flip the rounding), growing the odd-k term count and precision otherwise, with correctness pinned by an exhaustive HRR-equals-recurrence cross-check in the unit tests. Big-integer arguments are rejected (unevaluated), q(n) = 0 for n < 0, and a wrong argument count emits PartitionsQ::argx.

  • Protected, Listable — PartitionsQ[{2, 4, 6}] → {1, 2, 4}.
  • Two engines, dispatched by the size of n (threshold n = 1000):
  • Small n — an exact GMP recurrence derived from the Euler identity ∏(1−x^k)·∏(1+x^k) = ∏(1−x^{2k}): q(m) = r(m) + Σ_k (−1)^(k−1) [q(m − g_k) + q(m − g_k')] over the same generalized pentagonal numbers g_k = k(3k∓1)/2 as PartitionsP, with an inhomogeneous term r(m) = (−1)^k when m/2 is the generalized pentagonal number g_k (else 0). O(n^1.5) integer additions; O(n·√n)-bit table.
  • Large n — the Hardy–Ramanujan–Rademacher / Hagis exact convergent series evaluated in MPFR (Hagis, Amer. J. Math. 85 (1963) 213–222): q(n) = (π/√(24n+1)) · Σ_{k odd} (1/k)·A_k(n)·I₁(π√(48n+2)/(12k)), summing over odd k only, with the modified Bessel function I₁ (computed by its everywhere-positive power series, as MPFR has no I₁) and the character sum A_k(n) = Σ_{gcd(h,k)=1} cos(π(s(h,k) − s(2h,k)) − 2πnh/k) built from exact Dedekind sums s(h,k). Working precision ≈ π√(n/3)/ln 2 bits plus guard bits; memory stays tiny where the recurrence's table would be prohibitive.
  • Unlike PartitionsP, the q-series has no clean closed-form Rademacher remainder bound, so the HRR engine's term count is convergence-driven (sum ≈√n odd terms; accept only when the sum lies within 1/4 of an integer and the last term is below 1/8, growing terms/precision otherwise). Correctness is pinned by an exhaustive HRR-equals-recurrence cross-check (every n up to 1500 plus a strided sample and large spot values to n = 100000; see tests/test_partitionsq.c).
  • q(0) = 1; q(n) = 0 for n < 0. The result auto-promotes to a big integer (q(1000) has 22 digits; q(100000) has 245).
  • Non-integer, symbolic, or astronomically large (big-integer) arguments are left unevaluated; PartitionsQ called with other than one argument emits PartitionsQ::argx and is left unevaluated.

Attributes: Listable, Protected.

References

See also: IntegerPartitions, PartitionsP

Notes & additional examples

Distinct parts equal odd parts

PartitionsQ[n] counts the partitions of n into distinct parts. Euler's celebrated identity says this equals the number of partitions of n into odd parts — the generating-function identity ∏ (1 + x^k) = ∏ 1/(1 - x^(2k-1)). Contrast PartitionsP, which counts all partitions.