## Rowland’s Prime-Generating Function

### November 12, 2010

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 a1 = 7, an = an-1 + gcd(n, an-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 a1 = lpd(6-1) = 5, a2 = lpd(6-2+5) = 3, a3 = lpd(6-3+5+3) = 11, a4 = lpd(6-4+5+3+11) = 3, a5 = lpd(6-5+5+3+11+3) = 23, …, and an = lpd(6 – n + sum(a1an-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

### 8 Responses to “Rowland’s Prime-Generating Function”

1. […] today’s Programming Praxis exercise our goal is to implement a few functions that create integer sequences […]

```a106108 :: [Integer]
a106108 = 7 : zipWith (\n r -> r + gcd n r) [2..] a106108

a132199 :: [Integer]
a132199 = zipWith (-) (tail a106108) a106108

a137613 :: [Integer]
a137613 = filter (/= 1) a132199

shortcut :: [Integer]
shortcut = f 0 1 where
f s n = r : f (s + r) (n + 1) where r = lpd (6 - n + s)
lpd n = head \$ filter (\d -> mod n d == 0) [3,5..]
```
3. Khanh Nguyen said

My try in F#

```open System

let rec gcd a b = if b = 0 then a else gcd b (a % b)

let A n =
let rec helper iter (result:int list) =
if iter = n then result
else
helper (iter+1) (new_value::result)
helper 1  |> List.rev

let rec diff (l:int list) =
if List.length l < 2 then []
else
let d = abs ((List.nth l 1) - (List.nth l 0))
d::(List.tail l |> diff)
let diff_sequence n = A n |> diff
let third_sequence n = A n |> diff |> List.filter (fun x -> x > 1)

let isPrime (n:int) =
let rec divisors (iter:int) (counts:int) =
if float iter > ceil (sqrt (float(n))) then counts
else
if n % iter = 0 then (divisors (iter+1) (counts+1))
else divisors (iter+1) counts
(divisors 2 0) = 0

let lpd (n:int) =
if n % 2 = 0 then 2
else
let rec helper i =
if (n % i = 0) && (isPrime i) then i
else helper (i + 1)
helper 3

let shortcut n  =
let rec helper iter (result:int list) sum =
if iter = n then result
else
let new_value = lpd (6 - (iter+1) + sum)
helper (iter+1) (new_value::result) (sum+new_value)
helper 1  5 |> List.rev

shortcut 100
```
4. Graham said

Posted on pastebin.com, since my line count stretches the limits of polite posting here.
I memoized nearly everything, trading time for space. Python has syntactic sugar called “decorators” that works nicely for this; after defining
a decorator memoize(func), one merely need write @memoize on the line above the function definition to cache the result of calling func()
for later recursion or reuse.

Rather quick, though not as elegant or speedy as the Scheme or Haskell answers. I bet the F# answer probably wins over mine as well, but I
haven’t the ability to run F# on my laptop just yet.

5. Name Required said

You have “The primes are excluded from that sequence in Sloane’s A137613”, but I believe you mean “The ones are excluded from that sequence in Sloane’s A137613”.

6. programmingpraxis said

Fixed.

7. Hey all- I used this problem to teach myself Clojure. My solution (with some testing code) can be found here: https://github.com/topher200/rowland-primes/blob/master/src/rowland_primes/core.clj.

8. David said

Clojure version using O’Neil sieve for lpd function.

```(load "lazy-sieve")

(defn gcd [a b]
(loop [a a, b b]
(if (= b 0)
a
(recur b (mod a b)))))

(def rowland_seq0
(map first (iterate (fn [[x n]] [(+ x (gcd n x)) (inc n)]) [7 2])))

(def rowland_seq
(filter (fn [n] (not= n 1))
(map - (rest rowland_seq0) rowland_seq0)))

(defn lpd [n]
(first (filter (fn [p] (= (mod n p) 0)) lazy-primes)))

(def shortcut
(map first
(iterate
(fn [[x n sum]]
(let [val (lpd (+ 6 (- n) sum))]
[val (inc n) (+ sum val)]))  [5 2 5])))
```