Programming Praxis – Goldbach’s Conjecture

In today’s Programming Praxis problem we have to test Golbach’s conjecture that every even number greater than 2 can be written as the sum of two primes. Let’s get started.

A quick import (note that both the Numbers and primes packages define this module, but only Numbers contains the isPrime function we’re using):

import Data.Numbers.Primes

The function for testing Goldbach’s conjecture is pretty simple: just look at all the primes p less than n and check if n – p is prime.

goldbach :: Integer -> (Integer, Integer)
goldbach n = head [(p, n - p) | p <- takeWhile (< n) primes, isPrime (n - p)]

A quick test reveals everything’s working correctly.

main :: IO ()
main = do print $ goldbach 28
          print $ goldbach 986332

The Scheme solution implements two versions, citing speed as a reason. I also implemented his second version, but the speed was nearly identical to the algorithm above (about 11 seconds to determine that 532 is indeed the highest first prime in the first one million numbers), and given the choice I’d much rather have one line than thirteen.

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: