1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did you read this? $\endgroup$ – José Carlos Santos Oct 29 '17 at 17:44
  • $\begingroup$ All of thos rely on some other non elementary function, like the Riemann zeta function in some cases $\endgroup$ – Nimish Oct 29 '17 at 18:16
0
$\begingroup$

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

for $n \geq 3$

$\pi (n) = 1 + \sum \limits_{m=3}^{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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.