Tricky partitions
and easy stats
Weekly challenge 172 — 4 July 2022
Week 172: 4 Jul 2022
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.
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
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,
$n
members,
$m
,
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:
$count == 1
, it checks to see if $gap
is prime, and if so we have a result!
$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.
$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 1018.
#!/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; }
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
Any content of this website which has been created by Peter Campbell Smith is in the public domain