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.

About these ads

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

    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 == 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. Adam said

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: