4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $10000$ is a small number in this context. You should explain what your routine is doing, not just post the code. It will be easier to find what is wrong with a description of the algorithm $\endgroup$ – Ross Millikan May 31 '18 at 15:33
  • $\begingroup$ Seems to be a very ineffective method. If I compute with 32-bit integers, it overflows for $n \ge 10$ (using $\mathrm{lcm}(a,b)=ab/\gcd(a,b)$). What is the purpose of the algorithm? $\endgroup$ – gammatester May 31 '18 at 15:41
  • 3
    $\begingroup$ Not easy to determine what the algorithm does. It might be trial division. $\endgroup$ – Peter May 31 '18 at 15:46
5
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The cycle can be simplified: $a= k/\gcd(k, b1); b4 = b1(1+a)\cdots$ $\endgroup$ – Yuri Negometyanov Jun 7 '18 at 22:32
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.