Programming Praxis

Regular readers of Programming Praxis know of my affinity for prime numbers. Today’s exercise is based on a prime-generating sequence described by Eric Rowland. Consider the sequence a₁ = 7, a_n = a_n-1 + gcd(n, a_n-1): 7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73. Taking the differences between successive elements of the sequence gives a second sequence 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1. All the elements of that sequence are either 1 or prime. Eliminating the 1s gives a third sequence of primes that begins 5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3. Rowland has proved that all elements of the sequence are either 1 or prime; it is conjectured but not proven that all the odd primes appear in the sequence.

It is possible to shortcut the sequence by omitting the 1s, since the number of 1s at any point can be pre-computed. If we have a least-prime-divisor function lpd, then Vladimir Shevelev describes the sequence as a₁ = lpd(6-1) = 5, a₂ = lpd(6-2+5) = 3, a₃ = lpd(6-3+5+3) = 11, a₄ = lpd(6-4+5+3+11) = 3, a₅ = lpd(6-5+5+3+11+3) = 23, …, and a_n = lpd(6 – n + sum(a₁ … a_n-1).

Your task is to write functions that generate the three sequences, including the shortcut. 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