/dev/collective

I love Haskell. I love many things about it, but one of its main attractions for me is that it is lazy. I guess I like that because I’m lazy myself.

Lazyness in Haskell means that we get infinite lists (or streams) for free - i.e. they don’t need any special handling over finite lists. Granted, other languages have infinite lists, but in Haskell any regular list has the natural potential of being infinite so we don’t need any specific syntax or constructors for them.

So, when I read about a Rutgers graduate student named Eric Rowland that recently discovered a simple prime-number generating formula, I decided to try it out in Haskell. Turns out it is extremely simple.

The generating formula is based on the sequence a(n) that you get by setting a(1) = 7 and then for n ≥ 2:

a(n) = a(n-1) + gcd(n,a(n-1))

In Haskell, running in interactive mode (GHCi), we define this by

Prelude> let a' = (1,7) : (map ( \(n,x) -> (n+1, x + (gcd (n+1) x))) a')
Prelude> take 10 a'
[(1,7),(2,8),(3,9),(4,10),(5,15),(6,18),(7,19),(8,20),(9,21),(10,22)]
Prelude> let a = map snd a'
Prelude> take 23 a
[7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44,45,46,69]

Note that each element of a’ is a tuple of the index n and the value a(n). By taking differences between successive values of this sequence, you always get either the number 1 or a prime number (proving this is Rowland’s contribution).

Prelude> let d = zipWith (-) (tail a) a
Prelude> take 23 d
[1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3]

So far, so good. Now in one step we remove the 1-s by using filter and get rid of duplicates by using nub (which is defined in the List module).

Prelude> :m +List
Prelude List> let primes = nub $ filter (/= 1) d
Prelude List> take 23 primes
[5,3,11,23,47,101,7,13,233,467,941,1889,3779,7559,15131,53,30323,60647,121403,242807,19,37,17]

Neat! The list primes is of course infinite and we could pluck the values off it as long as we like, and Haskell’s laziness will make sure values are only computed on demand. Rowland’s paper contains the details of the math.