## Sunday, January 21, 2007

### Using prime counting formula

I've talked a lot in various formats across the web about a way to count prime numbers that I found back in 2002, but I don't see a lot of places where I go through a simple example, so I'll go through a basic example.

I am going to next give my prime counting function in its sieve form, where things might look a bit complicated but I'm going to break it all down simply to count the primes up to 100.

Sieve form of my prime counting function:

With natural numbers x and n, where p_i is the i_th prime:

P(x,n) = x - 1 - sum for i=1 to n of {P([x/p_i],i-1) - (i-1)}

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

The word "sieve" is used a lot like it is used in non-math areas to mean a way to block out certain things while getting just what you want. And to count the primes up to 100 the sieve part has to do with getting primes, as you first need to already know the primes up to the positive square root of 100, which is of course 10.

And those primes are 2, 3, 5, and 7, and there are 4 of them, so with

x=100, n = 4, and I can go back and expand out what I had before:

P(100,4) = 100 - 1 - (P([100/2], 0)-0) - (P([100/3], 1) - 1) - (P([100/5, 2) - 2 )- (P([100/7], 3) - 3 )

where I want to explain the part with the brackets, as, for instance,[100/3] = 33.

The brackets are called the floor function and mean to drop off any remainder when you do the division, which is a good thing, as it makes it easier to do the calculation without worry about any decimal places or fractions.

So, now I can go forward to get:

P(100,4) = 99 - P(50, 0) - P(33, 1) + 1 - P(20, 2) + 2 - P(14, 3) + 3

but with P(14,3) I need to do the reset mentioned in the definition as there are only 2 primes up to the positive of sqrt(14) as those are 2 and 3, so that needs to be changed to 2, and I can add all the integers together so I have:

P(100,4) = 105 - P(50, 0) - P(33, 1) - P(20, 2) - P(14, 2)

So now what? Well the function has called itself 4 times so you go through each time, and the first is easy enough as you now have

P(50, 0) = 50 - 1 = 49

as the 0 means no other iterations, because you go from 1, in the definition above. But,

P(33, 1) = 33 - 1 - P([33/2], 0) + 0 = 32 - P[16,0] = 32 - 15 = 17

I know that P[16,0] equals 15 from what I learned with the previous case as the 0 means not to iterate so you just subtract 1, so that's easy. Next is

P(20, 2) = 20 - 1 - (P([20/2], 0) - 0) - (P([20/3], 1) - 1)

so

P(20, 2) = 19 - P(10, 0) - P(6, 1) + 1

and the P(10,0) is easy to get as that is just 9. And there is a short-cut for P(6,1) though you can go the long way if you want, or you can notice that there is only one prime less than the positive square root of 6 as that prime is 2, so P(6,1) must be the count of primes up to 6, and those are 2, 3 and 5, so it is 3. Then

P(20, 2) = 20 - 9 - 3 = 8

and you may notice that is the count of primes up to 20. As 2 is equal to the number of primes less than the positive square root of 20.

So now only P(14, 2) is left and you may think now this is a long process but I am explaining a lot so you can have a clear idea of how it works. Once you get a feel for it though, it's a fast and easy way to count primes.

Now with P(14, 2) I can use the formula or I can just notice that it is the count of primes up to 14, which is 6, as those are 2, 3, 5, 7, 11 and 13. (As an exercise you can go ahead with the formula and verify you get 6.)

So now finally I can get the count of primes up to 100:

P(100,4) = 105 - 49 - 17 - 8 - 6 = 25

To verify your prime counts you can go on to web to various sources.

Ok, so that is a detailed explanation of how to use that formula which is the sieve form of my prime counting function.

Just for fun, I'll do a quick calculation for 120, as that's the last number before you need another prime, so n still equals 4, like before and

P(120,4) = 120 - 1 - (P([120/2], 0)-0) - (P([120/3], 1) - 1) - (P([120/5, 2) - 2 )- (P([120/7], 3) - 3 )

so

P(120,4) = 119 - 59 - P(40, 1) + 1 - P(24, 2) + 2 - P(17, 2) + 3

where P(17,3) goes to P(17,2) using the reset because there are only two primes up to the positive square root of 17. And now for some short-cuts, as P(24, 2) is the count of primes up to 24, and I'll just count those off on my fingers to get P(24, 2) = 9, and doing the same with P(17,2) gives

P(17,2) = 7

and hope you caught that one as I didn't at first as 17 is prime, so it gets counted.

And

P(40,1) = 40 - 1 - P(20,0) = 39 - 19 = 20

so I have

P(120,4) = 119 - 59 - 20 + 1 - 9 + 2 - 7 + 3 = 30.

So just like that you know there are 5 more primes after 100, before 120 and those are:

101, 103, 107, 109, and 113

And yes, if you just like playing with numbers you can easily keep doing prime counts where it's kind of a good idea to keep short-cut information handy.

James Harris (Edited to correct an error--P(14,2) instead of P(14,1)--8/30/09.)

Anonymous said...

You have the comment "Just for fun, I'll do a quick calculation for 120, as that's the last number before you get another prime, so n still equals 4, ..."

The way I read this is that you're implying that the number that comes after 120 is prime. But that number, 121, is not prime. In fact, it is a perfect square.

Did I misunderstand you?

James said...

Hmmm...what I have can be confusing. Maybe I should have said "need" versus "get" another prime. I think I'll change it.

0 said...

Incredible . :)