The nth prime calculator

Question

How to prove the correctness of the following algorithm :

Input: $n$ : the ordinal number

Output: $x$ : the nth prime number

$b_1=6$ , $b_2=6$ , $b_3=6$

If $n==1$ , then $x=2$ , else $x=3$

$k=4$ , $m=3$

While $m \leq n$ do:

$\phantom{5}$ $b_4=b_1+ \operatorname{lcm}(k-2,b_1)$

$\phantom{5}$ $a=b_4/b_1-1$

$\phantom{5}$ $k=k+1$

$\phantom{5}$ $b_1=b_2$ , $b_2=b_3$ , $b_3=b_4$

$\phantom{5}$ If $x<a$ then $x=a$ , $m=m+1$

Return $x$

You can run this code here .

GUI application that implements this algorithm can be found here .

Fast command line program that implements this algorithm can be found here .

I can confirm that algorithm produces correct results for all $n$ up to $10000$ .

Answer 1

Consider the variable $k$. Apart from the initialisation and increment, it is only used once, as $k-2$. It is therefore clearer if we simply lower its value by $2$ throughout:

b1 = 6 , b2 = 6 , b3 = 6
If n == 1, then x = 2 , else x = 3
k = 2, m = 3
While m ≤ n
do:
  b4 = b1 + lcm(k, b1)
  a = b4/b1 − 1
  k = k + 1
  b1 = b2 , b2 = b3 , b3 = b4
  If x < a then x = a , m = m + 1
Return x

Next, let's substitute the expression for $b_4$ into the expression for $a$.

$$a=\frac{b_4}{b_1}−1 = \frac{b_1+\textrm{lcm}(k,b_1)}{b_1}-1 = \frac{\textrm{lcm}(k,b_1)}{b_1} = \frac{k}{\gcd(k,b_1)}$$

b1 = 6 , b2 = 6 , b3 = 6
If n == 1, then x = 2 , else x = 3
k = 2, m = 3
While m ≤ n
do:
  b4 = b1 + lcm(k, b1)
  a = k/gcd(k, b_1)
  k = k + 1
  b1 = b2 , b2 = b3 , b3 = b4
  If x < a then x = a , m = m + 1
Return x

Basically what is happening is that $k$ is continually incremented. If it is a prime, then $\gcd(k,b_1)$ will be $1$, and $a$ will have the same value. The if statement will increment its prime counter, and store the prime in $x$. If the counter is at the requested value, the prime is returned.

If $k$ is not prime, then the $\gcd$ is highly likely not $1$ and $a$ is a smaller value than the previous prime found. The if statement will then do nothing, and the loop continues.

The only thing that remains to be shown is that $\gcd(k,b_1)$ is always larger than $1$ if $k$ is not prime. To be more precise:

Let $b_i$ be a sequence defined by $$ b_1=b_2=b_3=6\\ b_{i+3}=b_i+\textrm{lcm}(i+1,b_i)$$

It remains to be shown that $\gcd(k,b_{k-1})>1$ for all composite $k$.

The $b_i$ are highly composite ($b_{i-3}|b_i$) and the sequence grows large very quickly. Furthermore it starts with sixes so that it has factors $2$ and $3$ to begin with. That could well be enough to make it work for the relatively small $n$ that it has been tested with. I wouldn't expect it to fail until you get to large semiprimes, i.e. large composite numbers without small factors.

Answer 2

Updated 11.06.18

The proposed calculator enumerates the prime numbers on the pass.

Let us construct the similar algorithm based on the ideas of Eratosthenes sieve.

m = 1;
x = 2;
b = 2;
while (m < n)
{
  for(k = 3; ; k = k+2)
  {
    if(gcd(b,k)==1)
    {
       x = k;
       m = m + 1;
       b = b * x; 
    } 
  } 
}
return x;

In the both of the algorithms, a sequence of positive integers is tested for the presence of a common factor with a high composite number $b.$ If it equals to 1, then the integer is prime.

The algorithm above shows that it's sufficiently to use $b$ which equals the primorial $x\#$.

The OP calculator algorithm forms the greater value of $b,$ which contains any prime $p$ in the degree $d,$ wherein $$p^d\le x < p^{d+1},$$ but uses its delayed value.

This means that the OP calculator can be improved.

At this time, analysis of delaying influence shows that OP calculator is correct.