## Proth Primes And Sierpinski Numbers

### April 6, 2018

One of the neat things about mathematics is that, throughout history, many contributions to mathematics have been made by self-taught amateur mathematicians. About 150 years ago, a French farmer named François Proth (1852–1879), who lived near Verdun, proved this theorem:

Let

N=k2^{n}+ 1 withkodd and 2^{n}>k. Choose an integeraso that the Jacobi symbol (a,N) is -1. ThenNis prime if and only ifa^{(N−1)/2}≡ -1 (modN).

Primes of that form are known as Proth primes. Testing for a Proth prime is easy: choose *a* ∈ {3, 5, 7, 17} so that the Jacobi symbol is -1 and perform the modular multiplication. The game that recreational mathematicians play is to fix *k* and iterate *n* and see which *k* are fertile in producing primes; for instance, *k* = 12909 produces 81 primes before *n* = 53118.

Sierpinski numbers have the same form as Proth numbers, but “opposite” in the sense that there are *no* primes for a given *k*. The smallest known Sierpinski *k* is 78557; the only smaller *k* for which the Sierpinski character is not known are 10223, 21181, 22699, 24737, 55459 and 67607.

Your task is to write a program that identifies Proth primes and use it to find fertile *k* and Sierpinski *k*. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[…] Read More […]

@programmingpraxis, the problem states that 2^n > k, but the output of your solution includes n for which the inequality does not hold when k = 12909. For example, the first output is n = 1. In that case 2^n <= k and N = (53118 * 2^1) + 1 = 106237, which is not prime.

Here’s a solution in Python.

Examples: