Programming Praxis

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 = k 2ⁿ + 1 with k odd and 2ⁿ > k. Choose an integer a so that the Jacobi symbol (a, N) is -1. Then N is prime if and only if a^(N−1)/2 ≡ -1 (mod N).

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.

Pages: 1 2