In the recent paper arXiv:2405.06451 the authors provide infinitely many characterizations of the primes using MacMahon partition functions: for $a>0$ the functions $M_a(n):=\sum\limits_{0<s_1<s_2<\dots<s_a\atop n=m_1s_1+m_2s_2+\dots +m_as_a}m_1m_2\dots m_a$

The simplest is : $n$ is prime iff $(n^2-3n+2)M_1(n)-8M_2(n)=0$

I'm not really able to compute those functions. Could someone please write out the above characterization in full for the first few $n=2,3,4,5,6$ ?


For $n=3$, which is prime, what would make sense is $M_1(3)=1+3=4$ since $3=3×1=1×3$ and $M_2(3)=1×1=1$ since $3=1×1+1×2$, and indeed we have the equality $(3^2-3×3+2)×4-8×1=0$.

For $n=4$, which is composite, since $4=4×1=2×2=1×4$ we should have $M_1(4)=1+2+4=7$ and since $4=1×1+1×3=2×1+1×2$ we should have $M_2(4)=3+2=5$ and indeed $(4^2-3×4+2)×7-8×5=6×7-8×5=2$ is non zero positive.

Could someone please confirm?

  • 2
    $\begingroup$ I think this is even far less efficient than applying Wilson's theorem , but maybe interesting for theoretical purposes. $\endgroup$
    – Peter
    May 15 at 12:30
  • $\begingroup$ @Peter : of course I am not claiming this could be a fast detection method, the number of product and sums obviously grows fast with $n$. What I would like to understand is the partition aspect, to see what those sums are. $\endgroup$
    – Archie
    May 15 at 13:51

1 Answer 1


MacMahon worked out some cases using the function $$ \sigma_\nu(n) = \sum_{d \mid n} d^\nu$$ based on the divisors of $n$. Here are the first few. \begin{gather*} M_1(n) = \sigma_1(n) \\ M_2(n) = \frac{1}{8} [(1-2n)\sigma_1(n) + \sigma_3(n)] \\ M_3(n) = \frac{1}{1920} [(37 - 100n + 40n^2)\sigma_1(n) + (50-20n)\sigma_3(n) + 3 \sigma_5(n)] \end{gather*} The OEIS entries AA002127, A002128, and AA365664 through AA365667 include equivalent formulas using binomial coefficients rather than $\sigma_k(n)$.

See also this MathOverflow question and its links.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .