Prime Count and Addition Chains

Zhi-Wei Sun (maths.nju.edu.cn/~zwsun) in 2015 conjectured that a certain sequence of prime counts would be an addition chain A262439. If we define this function:

\(f(n)=\pi\left(\frac{n(n+1)}{2}+1\right)\)

where \(\pi(x)\) is the number of primes \(\le x\), then:

\(f(x)=\begin{cases}1 \text{  if }x=1\\f(y)+f(z) \text{  }1\le y,z<x\end{cases}\).

Zhi-Wei Sun then strengthened the conjecture A262446 to say that all but the first few steps are non-doubling steps:

\(f(x)    =\begin{cases}
1  \text{  if }x=1\\f(y)+f(z)  \text{  if }x\le3,1\le y,z<x\\f(y)+f(z) \text{  } 1\le y<z<x\end{cases}\)

Sun validated this conjecture for all \(n\le 10^5\) in 2015. Chang Zhang then further validated \(n\le 5\times 10^5\) in 2020.

In 2024 I checked the conjecture for \(n\le 2^{24} \). I used primecount write out the \(f(n)\) values for each \(n\). Then I processed the file to make sure it was an addition chain.

The raw file with 64 bit entries is here for (\(n\le 2^{21}\)): 

primePiValues.bin.gz

In order to get the processing to work fast you had to realize that this addition chain grows quite slowly in comparison to near optimum chains. This chain is full of extreme non-star steps.

Since \(\lim_{n\rightarrow\infty}\frac{f(n+1)}{f(n)}=1\) we must get blocks of larger and larger sequences of small steps. \(\lim_{n\rightarrow\infty}f(n+1)-f(n)=\infty\) so the addition chain elements keep growing by larger gaps.

I show the non-star steps in the following table getting bigger as we find new larger cases. We have \(f(x)=f(y)+f(z)\):