Programming Praxis – Rowland’s Prime-Generating Function

In today’s Programming Praxis exercise our goal is to implement a few functions that create integer sequences related to prime generation. Let’s get started, shall we?

As in the Scheme solution, the function names refer to their number in the On-Line Encyclopedia of Integers.

The first sequence can be written in a manner similar to the typical Fibonacci sequence solution.

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

The next two just build on the previous one and are fairly trivial.

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

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

The shortcut function is slightly longer. We store the sum of all the previous numbers so that the function runs in O(n2) rather than O(n3).

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..]

Some tests to see if we’re getting the correct output:

main :: IO ()
main = do print $ take 65 a106108
          print $ take 104 a132199
          print $ take 72 a137613
          print $ take 72 shortcut

Yup. Piece of cake.

About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: