I watched The hardest "What comes next?" (Euler's pentagonal formula) The explanatory video by Mathologer, and I learn't a lot. Somewhere in chapter three, the presenter just throws in that a small modification to his sequence of sequences can be used to generate primes.
I created the Rosetta Code task, and Python entry that follows the video, going so far as to add the prime number generator too. But I was used to sieves for generating primes and I could not work out how this new method worked.
I still have a mental todo item to get back to this.
Another mental todo item was that I remembered from this, or probably another mathologer video where he pointed out that two sequences can lull you into thinking they are the same for several values before they then diverge. I needed to check the partition based prime generator against a sieve.
Well, this morning I added the following extra code to use Pythons sympy.primerange sieve and checked the first 100_000 primes:
if 1:
from sympy import primerange
n = 100_000
print('Check that the first', n, 'partition and sieved primes are equal:')
part_primes = list(islice(par_primes(), n))
sieve_primes = list(primerange(2, part_primes[-1]+1))
if part_primes == sieve_primes:
print(f" First {n} primes, up to {part_primes[-1]} are equal.")
else:
print(f" First {n} primes are NOT equal!")
Outputs:
Check that the first 100000 partition and sieved primes are equal:
First 100000 primes, up to 1299709 are equal.
So my question is: Can someone please explain what links this method and the sieve method that I am familiar with?
Thanks in advance.
(PS my level of mathematics is at around the the level shown in the video in this area).
The integer partition function $p(n)$ satisfies the recurrence relation illustrated in formula (1) below where $g_n=\frac{n\,(3\, n-1)}{2}$ is the generalized pentagonal number.
$$p(n)=\sum\limits_{k\ne 0}(-1)^{k-1}\,p\left(n-g_k\right)=\sum\limits_{k>0}(-1)^{k-1}\,\left(p\left(n-g_k\right)+p\left(n-g_{-k}\right)\right)\tag{1}$$
The relationships between the integer partition function $p(n)$ and the divisor function $\sigma_1(n)$ are given in formulas (2) and (3) below.
$$\quad p(n)=\frac{1}{n}\sum\limits_{k=0}^{n-1}\,\sigma _1(n-k)\,p(k)=\frac{1}{n}\sum\limits_{k=1}^n\sigma_1(k)\,p(n-k)\,,\quad n>0\tag{2}$$
$$\quad \sigma_1(n)=\sum\limits_{k\ne 0}(-1)^{k-1}\,g_k\, p\left(n-g_k\right)=\sum\limits_{k>0}(-1)^{k-1}\,\left(g_k\, p\left(n-g_k\right)+g_{-k}\, p\left(n-g_{-k}\right)\right)\tag{3}$$
Note formula (2) above is explicitly defined as a finite sum, but formulas (1) and (3) above can also be evaluated as a finite sums since $p(n)=0\,\forall\,n<0$.
The function $\sigma_1(n)$ is related to the primes as follows:
$$\sigma_1(n)=n+1\iff n\in \mathbb{P}\tag{4}$$
If $n$ is composite then $\sigma_1(n)>n+1$ since composite values of $n$ have more divisors than just $1$ and $n$.
For more information on the partition function $p(n)$ see Weisstein, Eric W. "Partition Function P." From MathWorld--A Wolfram Web Resource, PartitionsP function, and Partition Function Identities.
Form more information on the divisor function $\sigma_1(n)$ see Weisstein, Eric W. "Divisor Function." From MathWorld--A Wolfram Web Resource and DivisorSigma Function.