# 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 Sn 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 Sn 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.

nSnprime?
1 0
2 2Y(2=2)
3 3Y(3=3)
4 2
5 5Y(5=5)
6 5
7 7Y(7=7)
8 10
9 12
10 17
11 22Y(11x2=22)
12 29
13 39Y(13x3=39)
14 51
15 68
16 90
17119Y(17x7=119)
18158
19209
20277
21367
22486
23644Y(23x28=644)