Prime numbers has been a most beloved number category from the ancient years until now. The Greek Euclides proves in his 9th book that prime numbers are infinite and later, around 250 B.C. Eratosthenes invents a method (Eratosthene's Sieve) which finds all prime numbers smaller than a given number.

Next big step: Piere Fermat believes that all numbers of the form Fn = 22n +1 are prime. In the 18th century Euler disproves it by showing that F5 is divided by 641. Next step is again by Euler who in 1742, finds a relation between the harmonic series (1 + 1/2 + 1/3 + ... + 1/) and the sum of the inverse prime number series (1/2 + 1/3 + 1/5 + ... + 1/p).

The next contribution is in 1798, when Andrien-Marie Legendre in his "Essai sur la theorie des nombres", he suggests without proving it, that for relatively big "x" values, the number of primes less or equal than "x" is approximated by p(x) = x /(log(x) - 1.08366). Indeed, here's a sample:

x = 10166, p(x) = 1248.412109, actual = 1248, diff = 0.412
x = 10167, p(x) = 1248.519897, actual = 1248, diff = 0.520
x = 10168, p(x) = 1248.627563, actual = 1248, diff = 0.628
x = 10169, p(x) = 1248.735352, actual = 1249, diff = -0.265
x = 10170, p(x) = 1248.843018, actual = 1249, diff = -0.157
x = 10171, p(x) = 1248.950684, actual = 1249, diff = -0.049
x = 10172, p(x) = 1249.058472, actual = 1249, diff = 0.058
x = 10173, p(x) = 1249.166138, actual = 1249, diff = 0.166
x = 10174, p(x) = 1249.273926, actual = 1249, diff = 0.274
x = 10175, p(x) = 1249.381592, actual = 1249, diff = 0.382
Note: You can find the C code producing these samples at the end of the writeup.

That is, there are 1249 prime numbers in the range [2, 10172] for example, and the approximation formula yields 1249.058472. Of course, as "x" gets bigger and bigger, the interval between successing primes gets bigger, so the approximation is not always that good. Example:

x = 11410, p(x) = 1381.592535, actual = 1376, diff = 5.593
x = 11411, p(x) = 1381.698959, actual = 1377, diff = 4.699
x = 11412, p(x) = 1381.805382, actual = 1377, diff = 4.805
x = 11413, p(x) = 1381.911804, actual = 1377, diff = 4.912
x = 11414, p(x) = 1382.018225, actual = 1377, diff = 5.018

In 1792, Gauss observing that in fixed-length intervals of positive integers, primes appear with decreased frequency as the beginning of the interval is increasing, suggested the approximation formula p(x) = ∫x2(dt/log t) which is better in some ranges but worse than that of Legendre. For example, for the same as above range [10166, 10175], Gauss's formula yields far bigger divergions:

x = 10166, diff = -15.099
x = 10167, diff = -15.208
x = 10168, diff = -15.316
x = 10169, diff = -14.424
x = 10170, diff = -14.533
x = 10171, diff = -14.641
x = 10172, diff = -14.749
x = 10173, diff = -14.858
x = 10174, diff = -14.966
x = 10175, diff = -15.075

In other ranges, of course, the approximation is much better than the one that Legendre's formula calculates.

Lattely, research is focused on the properties of the difference pn+1 - pn, where pn is some prime and pn+1 the next prime. A sample of this sequence is:
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, where for example, the first element "1" is the difference of the first prime ("2") and the very next ("3"). The prime number distribution is closely related with one unsolved till now problem: Goldbach's conjecture.


C code for the examples

(is_prime(x) and other useful functions for number theory problems, can be found at Useful Number Theory functions in C)

Gauss approximation formula: p(x) = ∫x2(dt/log t)

#include <stdio.h>
#include <math.h>

int is_prime(int x)
{
    int i, s;
    if (x < 2) return 0;
    for (i = 2, s = sqrt(x); i <= s; i++)
        if (x % i == 0) return 0;
    return 1;
}

int primes_till_x(int x){
  unsigned int i, sum = 0;

  for(i=1; i <= x;i++)
   if (is_prime(i)) sum++;
  return sum;
}


int main(){

  unsigned int x;
  double t, d=0.001, integr;

 for(x=10166; x <= 10175; x++){
  integr = 0.0;
  for(t=2; t <= x; t += d)
    integr += d/(log(t));
  printf("x = %d, diff = %.3f\n", x, primes_till_x(x)- integr);
 }
  return 0;
}

Legendre approximation formula: p(x) = x /(log(x) - 1.08366)

#include <stdio.h> #include <math.h> int is_prime(int x) { int i, s; if (x < 2) return 0; for (i = 2, s = sqrt(x); i <= s; i++) if (x % i == 0) return 0; return 1; } int main(){ unsigned int i; double tt1, tt2=0.0; for(i=1;i <= 10175; i++){ tt1=i/(log(i)-1.08366); if (is_prime(i)) tt2 +=1; // printf("x = %d, p(x) = %.6f, actual = %.0f, diff = %.3f\n", i, tt1, tt2, tt1-tt2); printf("%d %.3f\n", i, tt1-tt2); } return 0; }
Bibliography:
The Papyros Larousse Britannica Encyclopedia.

Log in or register to write something here or to contact authors.