3.6 $K[x]$: Simple Prime-Power Counting Function

Navigation Links: – Next Page – Parent Page


$K[x]$ – Simple Prime-Power Counting Function that takes a step of $1$ at prime-powers of the form $x=p^n$.

The simple prime-power counting function is defined as follows.

$\quad K[x]=\sum_{i=1}^{\lfloor x\rfloor}If[PrimePowerQ[i],\ 1,\ 0]$


The following plot shows $K[x]$ (blue) and the $K_{est}[x]$ function (orange) which serves as an estimate for$K[x]$. The$K_{est}[x]$ function is defined below.

Simple Prime-Power Counting Function (k[x])
Simple Prime-Power Counting Function $K[x]$

The following formula can be used to recover $K[x]$ from $\pi[x]$.

$\quad K[x]=\sum_{n=1}^{\lfloor\log[2, x]\rfloor}\pi[x^{1/n}]$


The following formula can be used to recover $\pi[x]$ from $K[x]$.

$\quad\pi[x]=\sum_{n=1}^{\lfloor\log[2, x]\rfloor}\mu[n]\ K[x^{1/n}]$


Note the relationship between $\pi[x]$ and $K[x]$ is a simplification of the relationship between $\pi[x]$ and $J[x]$ (i.e. the $\frac{1}{n}$ term is removed from the conversion coefficients).


The $gsfd[n]$ function, referenced in some of the functions below, is the greatest square-free divisor of $n$ (which is also known as the radical or square-free kernel of $n$).


The following formula can be used to recover $K[x]$ from $J[x]$.

$\quad K[x]=\sum_{n=1}^{\lfloor\log[2, x]\rfloor}\frac{EulerPhi[gsfd[n]]}{gsfd[n]}\ J[x^{1/n}]$


The following formula can be used to recover $J[x]$ from $K[x]$.

$\quad J[x]=\sum_{n=1}^{\lfloor\log[2, x]\rfloor}\frac{\mu[gsfd[n]]\ EulerPhi[n]\ gsfd[n]}{n^2}\ K[x^{1/n}]$

The coefficient associated with converting $K[x]$ to $J[x]$ above is my favorite coefficient function. I’ve always found it to be fascinating and almost a bit magical.


The $K_{est}[x]$ function illustrated in the plot above is defined below. The$K_{est}[x]$ function derives an estimate for the $K[x]$ function from the $Li[x]$ and $\log[2]$ terms of Riemann’s formula for $J[x]$.

$\quad K_{est}[x]=\sum_{n=1}^{\lfloor\log[2, x]\rfloor}\frac{EulerPhi[gsfd[n]]}{gsfd[n]}\ (Li[x^{1/n}]-\log[2])$