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?
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