Programming Praxis – Prime Partitions

In today’s Programming Praxis exercise, our goal is to calculate the number of prime partitions for a given number. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.Map as M
import Data.Numbers.Primes

First we need to calculate the sum of the unique prime factors of a given number. The trivial way is to to take the list of prime factors, filter out the unique numbers and sum those. In the provided solution this is marked as the wrong way since there is a more efficient solution. On the other hand, we only need to this once each for the numbers 1 through 1000, so it’s not like it’s a massive performance bottleneck. Since performance doesn’t matter much, I personally prefer the straightforward, easy to understand implementation.

sopf :: Integer -> Integer
sopf = sum . nub . primeFactors

At first glance, the algorithm for the amount of prime partitions bears some resemblance to the Fibonacci function. The difference here is that each term refers to all of its predecessors instead of a fixed number, which means the typical zipWith solution won’t work. Instead, we build op a dictionary where for each number we store sopf(n) and k(n) so we don’t have to recalculate them.

k :: Integer -> Integer
k n = snd $ foldl' calc M.empty [1..n] M.! n where
    calc dict i = M.insert i (s, div (s + sum (map (\j -> (fst $ dict M.! j) *
        (snd $ dict M.! (i - j))) [1..i-1])) i) dict where s = sopf i

A test to see if everything is working properly:

:: IO ()
main = print $ k 1000 == 48278613741845757

Tags: , , , , , , , , ,

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: