1. Home
  2. Electronics Design
  3. prime counting function I made

prime counting function I made

Hi,

I made a prime counting function that is quite accurate, take a look if you want! :D

Here is the prime counting function:

count of primes = (EulerPhi(Pn(n))/Pn(n)*(prime(n)^2))+n

Here are some results for various n, and compared to Mathematica PrimePi function:

n=1 a=4 b=3.00001 c=2 d=1.50001

n=2 a=9 b=5.00001 c=4 d=1.25

n=3 a=25 b=9.66668 c=9 d=1.07408

n=4 a=49 b=15.2 c=15 d=1.01333

n=5 a=121 b=30.1429 c=30 d=1.00476

n=6 a=169 b=38.4156 c=39 d=0.985015

n=7 a=289 b=59.1718 c=61 d=0.97003

n=8 a=361 b=69.7397 c=72 d=0.968607

n=9 a=529 b=95.5382 c=99 d=0.965032

n=10 a=841 b=142.834 c=146 d=0.978312

n=15 a=2209 b=321.397 c=329 d=0.976892

n=20 a=5041 b=664.228 c=675 d=0.984042

n=25 a=9409 b=1157.07 c=1163 d=0.994897

n=30 a=12769 b=1495.5 c=1523 d=0.981943

n=31 a=16129 b=1867.55 c=1877 d=0.994965

n=32 a=17161 b=1971.14 c=1976 d=0.997542

n=33 a=18769 b=2138.36 c=2141 d=0.998768

n=34 a=19321 b=2185.69 c=2190 d=0.998032

n=35 a=22201 b=2490.83 c=2489 d=1.00073

n=36 a=22801 b=2541.5 c=2547 d=0.997839

n=37 a=24649 b=2728.31 c=2729 d=0.999748

n=38 a=26569 b=2921.15 c=2915 d=1.00211

n=39 a=27889 b=3047.27 c=3043 d=1.0014

n=40 a=29929 b=3249.65 c=3241 d=1.00267

n=45 a=38809 b=4097.41 c=4089 d=1.00206

cheers, Jamie

Reply to
Jamie M
Loading thread data ...

Hi,

I forgot to mention:

n = nth prime a = value to count primes up to (nth prime)^2 b = my prime counting function c = mathematica primepi d = error between b and c

For example for nth prime = 10 (prime(10)=29)

count of primes = (EulerPhi(Pn(n))/Pn(n)*(prime(n)^2))+n

count of primes = (EulerPhi(Pn(n))/Pn(n)*(prime(n)^2))+n

count of primes = 142.834

This gives the estimate of how many primes there are up to 29^2 (841)

Mathematica PrimePi gives 146

So the error is 0.978312 (142.834/146)

see below for n=10:

cheers, Jamie

Reply to
Jamie M

Try it for 37^2=24649, my formula is more accurate over certain wide ranges of numbers.

2704.968... = 24649 / (ln(24649) - 1)

2728.31 = (EulerPhi(Pn(37))/Pn(37)*(prime(37)^2))+n

Mathematica PrimePi = 2729

cheers, Jamie

Reply to
Jamie M

Can the 'where' of the 'certain ranges' be predicted I wonder?

I'm slightly reminded of the twelve hour analog clock that is absolutely accurate twice a day. If I knew exactly 'when' it was going to be absolutely accurate I could use it as a master timer.

Reply to
FromTheRafters

What's the function "Pn" in this context?

Reply to
bitrex

Right. A list of primes is even more accurate, though over smaller ranges.

Exactly.

Reply to
krw

Hi,

Pn(1) = 2 Pn(2) = 6 Pn(3) = 30

see

formatting link

cheers, Jamie

Reply to
Jamie M

Hi,

I think so, the formula is less than 24 hours old, and I'm still testing to see what the error looks like, right now it seems to be a converging error, but it may oscillate.

I made a new formula in the meantime that is more accurate I think, but also a bit less nice looking:

Here it is:

An example prime counting formula:

to estimate the primes up to prime(n)^2 where prime(n) is prime and n > 1

count of primes = prime(n)^2 - (sum(((((prime(n)^2)-1) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1), x=1 to n-1) + 1)

example for n=4, prime(n)=7, prime(n)^2=49

count of primes = prime(n)^2 - (sum(((((prime(n)^2)-1) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1), x=1 to n-1) + 1)

count of primes = 49 - (sum((((48) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1), x=1 to 3) + 1)

count of primes = 49 - ((((48) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1) + (((48) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1) + (((48) / (Pn(x)/EulerPhi(Pn(x-1)))) - 1) + 1)

count of primes = 49 - ((((48) / (Pn(3)/EulerPhi(Pn(3-1)))) - 1) + (((48) / (Pn(2)/EulerPhi(Pn(2-1)))) - 1) + (((48) / (Pn(1)/EulerPhi(Pn(1-1)))) - 1) + 1)

count of primes = 49 - ((((48) / (30/2))) - 1) + (((48) / (6/1))) - 1) + (((48) / (2/1))) - 1) + 1)

count of primes = 49 - (((3.2 - 1) + (8 - 1) + (24 - 1)) + 1) count of primes = 49 - ((2.2 + 7 + 23) + 1) count of primes = 49 - (32.2 + 1) count of primes = 49 - 33.2 count of primes = 49 - 33.2 count of primes = 15.8 actual count of primes up to prime(n)^2 = 15

So the formula got 15.8 and there are actually 15 primes. I have to test it more, but it should remain fairly accurate.

cheers, Jamie

Reply to
Jamie M

formatting link

seems to do the job, and it dates from 1896. Apparently there is a mathematical proof that it is right.

You can't use it to prove the Legendre Conjecture

formatting link

which is a pity.

Jamie seems to have re-invented the wheel ....

--
Bill Sloman, Sydney
Reply to
bill.sloman

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.