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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, factors, Haskell, kata, partitions, praxis, prime, primes, programming

This entry was posted on October 19, 2012 at 1:39 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply