Re: Implementation of functions for "Integer partitions detect the primes" paper

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Jul 07, 2025 at 12:39:53AM +0200, hermann@stamm-wilbrandt.de wrote:
> In forum posting
> https://www.mersenneforum.org/node/1081249
> 
> somebody asked for a PARI/GP implementation of partition functions from
> 
> "Integer partitions detect the primes"
> William Craig, Jan-Willem van Ittersum, and Ken Ono
> 
> Nice to see how forpart() can be used for non-simple stuff.
> I implemented functions M1(n), M2(n) and T1(n) for Theorem 1:
> https://www.pnas.org/doi/epub/10.1073/pnas.2409417121
> T1(n) is >=0 and =0 for n prime.
> 
> pi@raspberrypi5:~ $ freq
> min=cur=3000000=max
> pi@raspberrypi5:~ $ gp -q
> ? M1(n)=s=0;fordiv(n,d,s+=d);s;

You should do
M1(n)=my(s=0);fordiv(n,d,s+=d);s;

But this function is just sigma(n)

> ? M2(n)=s=0;for(m=1,n,forpart(v=m,if(v[1]<v[2],for(d=1,n\v[1],r=n-d*v[1];if(r%v[2]==0,s+=d*(r\v[2])))),[1,m],[2,2]));s;

As I understand this function is
(sigma(n,3)-(2*n-1)*sigma(n))/8
which is much faster to compute.

Of course this is kind of cheating, since the purpose of the paper is to prove this formula:
written this way, it is obvious that (n^2 - 3^n + 2)M1(n) - 8M2(n) is 0 iff n is prime.


Cheers,
Bill