20201009, 11:43  #1 
"Ruben"
Oct 2020
Nederland
46_{8} Posts 
The prime counting function
Hello,
I've thought about the prime counting function pi(n), and I thought that when n is a primorial : 17#, 19#, 23# and so on, there may exist a way to find the exact value pi(n) that could be simpler than computing all the primes (whitch would, of course need to be tested) Example : We know that pi(210)=46, let's suppose we didn't know it, we could start by calculating the number of possible positions doing 11*1/2=1/2, 1/21/2*1/3=2/6, 2/62/6*1/5=8/30, 8/308/30*1/7=48/210, Then, we would add 4, the number of primes up to x#, (in that case 7#), giving us 52, then we take away 1, because the first number in any cycle x# is always a possible prime position but 1 isn't prime, so we get to 51, And, (probably the most time consuming part for this method) : we take away, for each of the primes above x (for x#), whose square is below x#, the number of primes that they can multiply by to give less than x#, in the case 7#, 11 can be multiplied up to 19, giving us 4 taken away (11*11, 13, 17, 19), and 13² takes away another number, We have thus 51(4+1)=46. Maybe an interesting idea... 
20201009, 13:14  #2 
Aug 2006
3^{2}·5·7·19 Posts 
There's nothing in this method that limits it to primorials.
If you push a little further you'll get the Legendre sieve and hence the beginnings of sieve theory. 
20201009, 22:20  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
41×229 Posts 
Quote:
I think this idea is ~188 years old. you see  for squareful numbers, whose moebius function is zero, you subtract them back because you've already added them in the first pass. But if you used moebius function, you would have "added them with weight 0" (i.e. skipped). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime counting function records  D. B. Staple  Computer Science & Computational Number Theory  50  20201216 07:24 
New confirmed pi(10^27), pi(10^28) prime counting function records  kwalisch  Computer Science & Computational Number Theory  34  20201029 10:04 
The prime counting function conjecture  jrsousa2  Miscellaneous Math  3  20200913 04:04 
Prime counting function  Steve One  Miscellaneous Math  20  20180303 22:44 
Legendre's prime counting function  pbewig  Information & Answers  0  20110714 00:47 