mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-10-09, 11:43   #1
R2357
 
"Ruben"
Oct 2020
Nederland

3810 Posts
Lightbulb 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 1-1*1/2=1/2, 1/2-1/2*1/3=2/6, 2/6-2/6*1/5=8/30, 8/30-8/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...
R2357 is offline   Reply With Quote
Old 2020-10-09, 13:14   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2020-10-09, 22:20   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217108 Posts
Thumbs up

Quote:
Originally Posted by R2357 View Post
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,

Maybe an interesting idea...
It is an interesting idea indeed ...and a nice reinvention (not in a bad sense; people reinvent things all the time while they learn - which is very much like embryological parallelism. While one grows as a mathematical being, one repeats what the past evolution has already done).

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).
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime counting function records D. B. Staple Computer Science & Computational Number Theory 49 2020-11-06 22:02
New confirmed pi(10^27), pi(10^28) prime counting function records kwalisch Computer Science & Computational Number Theory 34 2020-10-29 10:04
The prime counting function conjecture jrsousa2 Miscellaneous Math 3 2020-09-13 04:04
Prime counting function Steve One Miscellaneous Math 20 2018-03-03 22:44
Legendre's prime counting function pbewig Information & Answers 0 2011-07-14 00:47

All times are UTC. The time now is 05:30.

Sat Nov 28 05:30:19 UTC 2020 up 79 days, 2:41, 3 users, load averages: 1.04, 1.18, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.