Prime number distribution (idea)

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 F_n = 2²ⁿ +1 are prime. In the 18th century Euler disproves it by showing that F₅ 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

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) = ∫^x₂(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 p_n+1 - p_n, where p_n is some prime and p_n+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

#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;
}

#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;
}