## 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:

$\kappa(n) = \frac{1}{n}\left(\mathrm{sopf}(n) + \sum_{j=1}^{n-1} \mathrm{sopf}(j) \cdot \kappa(n-j)\right)$

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.

Pages: 1 2

### 10 Responses to “Prime Partitions”

1. […] today’s Programming Praxis exercise, our goal is to calculate the number of prime partitions for a given […]

2. The formula in the exercise is wrong: the second call to sopf should be sopf(j), not sopf(n).

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 == 48278613741845757

3. ardnew said

small typo: sopf(42)=12, not 7

4. programmingpraxis said

@ardnew: Fixed. Thanks.

5. Paul said

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)

6. […] 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 […]

7. JP said

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. :) )

8. JP said

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*/list to control the recursion, making the code relatively clean and simple.

9. […] Pages: 1 2 […]