Generating Primes

For years people have tried to find formulae, or algorithms, which will generate primes, albeit not necessarily every prime in sequence.

The simple quadratic formula

  n2+n+41

was found in the 18th century by Euler, and gives primes for n between zero and 39 inclusive. But polynomials are bound to fail. Set n equal to the constant term (41 here), and each term individually, and hence the whole sum too, is divisible by that constant.

Here is presented a less well-known algorithm based on a Fibonacci-like sequence. Consider the series

  S1=0
  S2=2
  S3=3
  
  Sn=Sn-3+Sn-2

Assert that if S_n is divisible by n, then n is prime.

#!/usr/bin/python3

current=[0,2,3]

for i in range (3,1000):
    if current[2]%i==0: print("%d is prime"%(i))
    current=[current[1],current[2],current[0]+current[1]]

(Remember python indexes lists from zero, not one.)

The proposition sounds ridiculous, and to disprove it one needs to find just one counter-example where S_n is divisible by n but n is not prime.

This is an ideal task for a computer, for any Human will get very tired before the first counter-example is found.