Xrfgtjtk

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$ .

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.

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^dle 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.