Prime Partitions
October 19, 2012
Today’s exercise is my penance for a wrong answer at /r/math.
A partition of a number is a way to add numbers to equal the target number; for instance, 1+1+2+3+5 is a partition of 11. We studied partitions in two previous exercises. If all the numbers used in the summation are prime, it is known as a prime partition; for instance, 2+2+2+2+3 = 2+3+3 = 2+2+2+5 = 3+3+5 = 2+2+7 = 11 are the 6 prime partitions for 11. The number of prime partitions of a number is a function known by the Greek letter kappa in number theory, so κ(11)=6. You can see the sequence of prime partitions at A000607.
The usual computation of the number of prime partitions is done in two parts. The first part is a function to compute the sum of the prime factors of a number; for instance, 42=2·3·7, so sopf(42)=12. Note that sopf(12)=5 because the sum is over only the distinct factors of a number, so even though 12=2·2·3, only one 2 is included in the calculation of the sum. You can see the sequence of the sums of the distinct primes dividing n at A008472.
Given the function to compute the sum of the prime factors of a number, the number of prime partitions can be calculated using the following formula:
Your task is to write a function that computes the number of prime partitions of a number; use it to calculate κ(1000). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to calculate the number of prime partitions for a given […]
The formula in the exercise is wrong: the second call to sopf should be sopf(j), not sopf(n).
My Haskell solution (see http://bonsaicode.wordpress.com/2012/10/19/programming-praxis-prime-partitions/ for a version with comments):
import Data.List import qualified Data.Map as M import Data.Numbers.Primes sopf :: Integer -> Integer sopf = sum . nub . primeFactors 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 main :: IO () main = print $ k 1000 == 48278613741845757small typo: sopf(42)=12, not 7
@ardnew: Fixed. Thanks.
A version in Python. It uses memoization to speed up the calculations.
from ma.primee import td_factors as factors sopfs = {} def sopf(n): if n not in sopfs: sopfs[n] = sum(set(factors(n))) return sopfs[n] kappas = {1:0} def kappa(n): if n not in kappas: kmax = max(kappas.keys()) for i in range(kmax + 1, n + 1): kappas[i] = (sopf(i) + sum(sopf(j) * kappas[i - j] for j in range(1, i))) // i return kappas[n] print kappa(1000)[…] we’re back into the mathy sort of problems from Programming Praxis, tasked with calculating the number of prime partitions for a given number–essentially, how many different […]
Here’s my solution in Racket (along with a memoization macro that makes the runtime bearable):
– Prime Partitions
– “Memoization in Racket
( Also, there’s still a typo in the equation. That took me a fair bit to notice until I saw Remco Niemeijer’s comment. :) )
As a follow up, I wrote up a way to actually generate the prime partitions which might be interesting:
– Prime Partitions II: The Listing
The interesting points at least from my perspective are that it uses generators and
for*/listto control the recursion, making the code relatively clean and simple.[…] Pages: 1 2 […]
Thanks a lot for this formula. It was a huge problem for me to understand the Euler transformation and I think that without Your formula I’d give up. :D