Tricky partitions and easy stats

Prime partitions

Task 1 this week asks:

You are given two positive integers, $m and $n. Write a script to find out the Prime Partition of the given number. No duplicates allowed. For example,

Input: $m = 18, $n = 2
Output: 5, 13 or 7, 11

Input: $m = 19, $n = 3
Output: 3, 5, 11

The internet tells us that a prime partition is a set of prime numbers that add up to a given number.  From the examples, I think we can deduce:

• $m is the given number for which we are to find certain prime partitions
• These partition sets must contain $n members
• These members must be distinct
• 1 is not regarded as a usable prime number
• We are to report all possible sets for a given $m
• We are report the members of the set in increasing order (ie 5,13 not 13, 5)

The simple-minded way to do this is to check all the sums of $n prime numbers which are less than $m and somewhere in there we will find the result.  There are a few efficiencies we can apply: for example, if $n == 3, having selected two primes whose sum already exceeds $m there is no point in looking at a third.

This problem is one of nested loops, and the number of loops is variable. Such problems are often best solved by recursion, and that's what I did.  I wrote a function fill_gap($gap, $count) which finds all the possible sets of $count primes that sum to $gap.  

I use 'gap' to mean difference between $m and the incomplete set of primes I am currently testing.  So for the second of Mohammad's examples, the gap is initially 19, but when I am testing 3 as the first prime, the gap is now 16.

So what does fill_gap do? We start by calling fill_gap($m, $n) - we are looking for all the sets of $n qualifying primes that sum to $m.  And here's what fill_gap does:

• If $count == 1, it checks to see if $gap is prime, and if so we have a result!
• If $count == 1 and $gap is not prime then we know that there is no answer involving the previous set of $n - 1 primes we are testing.
• If $count > 1 then we loop downwards over all the primes ($j) less than $gap, calling fill_gap($gap - $j, $count - 1) to fill the remaining gap.

So does it work?  Well, yes, of course.  It works pretty well for smallish numbers. For example $m = 101, $n = 4 finds 21 answers in milliseconds.  For large $m it is still quite efficient: $m = 501, $n = 4 takes about 5 seconds (on my Raspberry Pi). However, if you start increasing $n, $m = 501, $n = 5 takes about 2 minutes.

Five number summary

Task 2 says: You are given an array of integers. Write a script to compute the five-number summary of the given set of integers.

The 5-number summary comprises minimum, first (or lower) quartile, median, third (or upper) quartile and maximum.  To do this, we first sort the array.  The minimum and maximum values are now the first and last elements.  If there is an odd number of elements in the array, the middle one is the median; if there is an even number then the average of the two elements that straddle the middle is  the median.

A similar process is used to find the first and third quartiles. For example, if there are 10 numbers in the set, s[0] to s[9], the median is the average of s[4] and s[5], the first quartile is 0.75 of item s[2] plus 0.25 of item s[3] and the third quartile is 0.25 of item s[6] plus 0.75 of item s[7].

Of course there are modules to do all this, but it's only a dozen lines of simple coding to do it from first principles.