Task — Prime partition

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.

Examples

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

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

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

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

Analysis

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 that in this instance:

• $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 to 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.

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, 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 then, for example, $m = 501, $n = 5 takes about 2 minutes.

Interestingly, the unproved Goldbach's Conjecture states that any positive integer greater than 1 has a prime partition - ie is the sum - of two primes, though that includes duplicates and 1. It has been verified up to 10¹⁸.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-07-07
# PWC 172 task 1

use v5.28;
use strict;
use warnings;
use utf8;
binmode(STDOUT, ':utf8');

my (@tests, @is_prime, $test, $m, $n, @is_used, @parts, $or, $output, $start);

@tests = ([18, 2], [19, 3], [97, 4], [101, 7], [998, 2]);
@is_prime = make_sieve(1000);   # $sieve[$j] == 1 if $j is prime
$is_prime[1] = 0;               # examples suggest that 1 is not allowed as a prime

# loop over tests
for $test (@tests) {
    ($m, $n) = @$test;
    say qq[\nInput:  \$m = $m, \$n = $n];
    
    # initialise
    @is_used = ();   # we are looking for distinct primes, so set $is_used[$j] if $j is already used
    @parts = ();     # these are the components of the set of primes
    $or = '';
    $output = 'Output: ';
    $start = $m;     # the largest possible number that fits in the initial gap
    
    # find the answer
    fill_gap($m, $n);
    say $output;
}
        
sub fill_gap {  # 

    # fill_gap($gap, $count) finds all the sets of $count distinct primes which add up to $gap

    my ($gap, $count, $j, $result, $new_gap);
    $gap = shift;
    $count = shift;
    
    # loop downwards over primes from the last one tried
    for ($j = $start; $j >= 1; $j --) {
        next if (not $is_prime[$j] or $is_used[$j]);
        
        # let's assume this is the right one
        $parts[$n - $count] = $j;
        
        # ... and it would reduce the gap to $new_gap
        $new_gap = $gap - $j;
        
        # if $new gap is zero and $count == 1 then we have a result
        if ($new_gap == 0 and $count == 1) {
            $output .= $or . join(', ', reverse @parts);  # Mohammad wants them in increasing order
            $or = ' or ';
            
        # or if $count is > 1 we call fill_gap recursively to fill $new_gap with $count - 1 primes  
        } elsif ($count != 1) {
            $is_used[$j] = 1;
            $start = $j;
            fill_gap($new_gap, $count - 1);
            $is_used[$j] = 0;
            
        # or if $count == 0 but this prime won't fill the gap then we keep on trying
        } else {
            $is_used[$j] = 0;
        }
    }
    $parts[$n - $count] = 0;
}

sub make_sieve {
    
    # make sieve of Eratosthenes - $j is prime if $sieve[$j];
    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = $_[0];
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }
    
    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime     
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
    return @sieve;
}

Output

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

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

Input:  $m = 97, $n = 4
Output: 2, 5, 7, 83 or 2, 3, 13, 79 or 2, 5, 11, 79 or 
2, 3, 19, 73 or 2, 5, 17, 73 or 2, 5, 19, 71 or 
2, 7, 17, 71 or 2, 11, 13, 71 or 2, 5, 23, 67 or
2, 11, 17, 67 or 2, 3, 31, 61 or 2, 5, 29, 61 or
2, 11, 23, 61 or 2, 5, 31, 59 or 2, 7, 29, 59 or
2, 13, 23, 59 or 2, 17, 19, 59 or 2, 5, 37, 53 or
2, 11, 31, 53 or 2, 13, 29, 53 or 2, 19, 23, 53 or
2, 5, 43, 47 or 2, 7, 41, 47 or 2, 11, 37, 47 or
2, 17, 31, 47 or 2, 19, 29, 47 or 2, 11, 41, 43 or
2, 23, 29, 43 or 2, 17, 37, 41 or 2, 23, 31, 41

Input:  $m = 101, $n = 7
Output: 3, 5, 7, 11, 13, 19, 43 or
3, 5, 7, 13, 17, 19, 37 or 3, 5, 7, 13, 19, 23, 31 or
3, 7, 11, 13, 17, 19, 31 or 3, 5, 11, 13, 17, 23, 29 or
5, 7, 11, 13, 17, 19, 29

Input:  $m = 998, $n = 2
Output: 7, 991 or 31, 967 or 61, 937 or 79, 919 or
139, 859 or 211, 787 or 229, 769 or 241, 757 or
271, 727 or 307, 691 or 337, 661 or 367, 631 or
379, 619 or 397, 601 or 421, 577 or 457, 541