Prime Counting 10 Year Anniversary

So I should acknowledge an intriguing milestone as it has been 10 years since I found a way to count prime numbers using, for the first time known, a difference equation:

With natural numbers

P(x,y) = x - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

Because it is a difference equation you do not need to tell the equation any prime numbers.

To count primes up to 100, for example, you'd calculate P(100,10), which gives 25.

For me it was always fascinating as I found the original form working at the computer.

It was such a fascinating feeling August of 2002, ten years ago, when that computer screen filled up with prime numbers, found as the full count took place. It finds the primes up to the square root, so if you're counting to 100, it finds 2, 3, 5 and 7. If you're counting primes up to 10000, it finds primes up to 100 as it counts. So cool.

It does have a sieve form, where you give it those primes instead of letting the math find them, which is what can be made faster as in iterating through to count with the fully mathematicized form, it's doing some calculations over and over again. The sieve form helps stop that repetition so it's faster:

Still with natural numbers where p_j is the j_th prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/p_j,j-1) - (j-1)}

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

Because you're using natural numbers, no fractions or decimals, so those are just dropped. So 10/3 is 3 with just natural numbers, the sqrt() is the integer square root, for instance sqrt(10) = 3, as that's floor(sqrt(10)), and it's automatically positive because natural numbers are only the positive integers greater than 0.

But if you're not looking for something faster to count primes, it's more interesting to probe the difference equation further, and follow it through to a differential equation!

Continuous function:

In the complex plane

P'_y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

is the partial differential equation that follows from the difference equation.


James Harris