Prime counting function formulas

Question

Are there any elementary (including floor, ceiling, mod) representations of the prime counting function. Or one without an integral.

All of thos rely on some other non elementary function, like the Riemann zeta function in some cases — Nimish, Oct 29 '17 at 18:16
It depends on how you define elementary. The answer I posted to a related question at https://math.stackexchange.com/q/3325680 provides several formulas for $\pi(x)$. The second Chebyshev function $\psi(x)=\sum\limits_{n\le x}\Lambda(n)$ has a simpler formula $\psi(x)=-\sum\limits_{n\le x}\mu(n)\log(n),\lfloor\frac{x}{n}\rfloor$. — Steven Clark, Mar 19 '20 at 20:50
This link Aug 10 2022 stackexchange shows one (still with a summation). — billymac00, Aug 21 '22 at 22:20

user140242 · Answer 1 · 2021-07-31T08:07:11.390

I made this elementary formula, although it really has no practical importance:

for $n > 3$

$\pi (n) = 2 + \sum \limits_{m=4}^{n} \left\lfloor \frac{\displaystyle 1}{\displaystyle 1+ \displaystyle\sum_{p=2}^{\left\lfloor \sqrt{m} \right\rfloor}{\left( \left\lfloor\frac{m}{p}\right\rfloor- \left\lfloor\frac{m-1}{p}\right\rfloor \right)}} \right\rfloor$

if we neglect the multiples of 2 and 3, it can be transformed into the following formula:

$\pi (n) = 2 + \sum \limits_{k=1}^{\left\lfloor{\frac{n+1}{6}}\right\rfloor} {\left\lfloor \frac{\displaystyle 1}{ \displaystyle 1 + \displaystyle\sum_{a=1}^{\left\lfloor\frac{1+\sqrt{-1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{-1+6\cdot k}{-1+6\cdot a}\right\rfloor - \left\lfloor\frac{-2+6\cdot k}{-1+6\cdot a}\right\rfloor \right)} + \displaystyle\sum_{a=1}^{\left\lfloor\frac{-1+\sqrt{-1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{-1+6\cdot k}{1+6\cdot a}\right\rfloor - \left\lfloor\frac{-2+6\cdot k}{1+6\cdot a}\right\rfloor \right)} }\right\rfloor}+\sum \limits_{k=1}^{\left\lfloor{\frac{n-1}{6}}\right\rfloor} {\left\lfloor \frac{\displaystyle 1}{\displaystyle 1 + \displaystyle\sum_{a=1}^{\left\lfloor\frac{1+\sqrt{1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{1+6\cdot k}{-1+6\cdot a}\right\rfloor - \left\lfloor\frac{6\cdot k}{-1+6\cdot a}\right\rfloor \right)} + \displaystyle\sum_{a=1}^{\left\lfloor\frac{-1+\sqrt{1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{1+6\cdot k}{1+6\cdot a}\right\rfloor - \left\lfloor\frac{6\cdot k}{1+6\cdot a}\right\rfloor \right)} }\right\rfloor}$

This is the Matlab code to verify the formula:

n=10000;
Pin=2;
for k=1:floor((n+1)/6)
    Sk=1;
    for a=1:floor((1+sqrt(-1+6*k))/6)
        Sk = Sk + floor((-1+6*k)/(-1+6*a)) - floor((-2+6*k)/(-1+6*a));
    end  
    for a=1:floor((-1+sqrt(-1+6*k))/6)
        Sk = Sk + floor((-1+6*k)/(1+6*a)) -  floor((-2+6*k)/(1+6*a));
    end  
    Pin=Pin+floor(1/Sk);
end
for k=1:floor((n-1)/6)
    Sk =1;
    for a=1:floor((1+sqrt((1+6*k)))/6)
        Sk = Sk + floor((1+6*k)/(-1+6*a)) - floor((6*k)/(-1+6*a));
    end 
    for a=1:floor((-1+sqrt((1+6*k)))/6)
        Sk = Sk + floor((1+6*k)/(1+6*a)) -  floor((6*k)/(1+6*a)) ;
    end 
    Pin=Pin+floor(1/Sk);
end
Pin

score 1 · Answer 2 · answered Oct 05 '20 at 20:37

I know three beautiful formulas for the prime-counting function. You can proof them with Wilson's theorem, which states that $$(n-1)!\,\equiv -1\mod n \Longleftrightarrow n\in\mathbb{P},\qquad \forall n\geq2.$$

Define a function $X_\mathbb{P}(n)$, which gives $1$ for $n\in\mathbb{P}$ and $0$ for $n\notin\mathbb{P}$. An expression for the prime counting function would be then: $$\pi(x) = \sum_{n=2}^{x}X_\mathbb{P}(n).$$

I know three closed expressions for $X_\mathbb{P}(n)$ but I think you can find one more. Here they are: $$F(n) = \left\lfloor\cos^2\left(\pi\cfrac{(n-1)!+1}{n}\right)\right\rfloor$$ $$H(n) = \cfrac{\sin^2{\left(\pi\cfrac{(n-1)!^2}{n}\right)}}{\sin^2\frac{\pi}{n}}$$ $$M(n) = \left\lfloor\left(\cfrac{(n-1)!+1}{n}\right)-\left\lfloor\left(\cfrac{(n-1)!}{n}\right)\right\rfloor\right\rfloor$$

Prime counting function formulas

2 Answers2