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

Pages: 1 2

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

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

@ardnew: Fixed. Thanks.

A version in Python. It uses memoization to speed up the calculations.

[...] 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*/list`

to 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