# 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

n^{2}+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

S_{1}=0 S_{2}=2 S_{3}=3 S_{n}=S_{n-3}+S_{n-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.

n | S_{n} | prime? | |
---|---|---|---|

1 | 0 | ||

2 | 2 | Y | (2=2) |

3 | 3 | Y | (3=3) |

4 | 2 | ||

5 | 5 | Y | (5=5) |

6 | 5 | ||

7 | 7 | Y | (7=7) |

8 | 10 | ||

9 | 12 | ||

10 | 17 | ||

11 | 22 | Y | (11x2=22) |

12 | 29 | ||

13 | 39 | Y | (13x3=39) |

14 | 51 | ||

15 | 68 | ||

16 | 90 | ||

17 | 119 | Y | (17x7=119) |

18 | 158 | ||

19 | 209 | ||

20 | 277 | ||

21 | 367 | ||

22 | 486 | ||

23 | 644 | Y | (23x28=644) |