Partition an integer x into n primes
Partition a positive integer X into N distinct primes.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Or, to put it in another way:
Find N unique primes such that they add up to X.
Show in the output section the sum X and the N primes in ascending order separated by plus (+) signs:
• partition 99809 with 1 prime.
• partition 18 with 2 primes.
• partition 19 with 3 primes.
• partition 20 with 4 primes.
• partition 2017 with 24 primes.
• partition 22699 with 1, 2, 3, and 4 primes.
• partition 40355 with 3 primes.
The output could/should be shown in a format such as:
Partitioned 19 with 3 primes: 3+5+11
- Use any spacing that may be appropriate for the display.
- You need not validate the input(s).
- Use the lowest primes possible; use 18 = 5+13, not 18 = 7+11.
- You only need to show one solution.
This task is similar to factoring an integer.
- Related tasks
11l
F is_prime(a)
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0)))
F generate_primes(n)
V r = [2]
V i = 3
L
I is_prime(i)
r.append(i)
I r.len == n
L.break
i += 2
R r
V primes = generate_primes(50'000)
F find_combo(k, x, m, n, &combo)
I k >= m
I sum(combo.map(idx -> :primes[idx])) == x
print(‘Partitioned #5 with #2 #.: ’.format(x, m, I m > 1 {‘primes’} E ‘prime ’), end' ‘’)
L(i) 0 .< m
print(:primes[combo[i]], end' I i < m - 1 {‘+’} E "\n")
R 1B
E
L(j) 0 .< n
I k == 0 | j > combo[k - 1]
combo[k] = j
I find_combo(k + 1, x, m, n, &combo)
R 1B
R 0B
F partition(x, m)
V n = :primes.filter(a -> a <= @x).len
V combo = [0] * m
I !find_combo(0, x, m, n, &combo)
print(‘Partitioned #5 with #2 #.: (not possible)’.format(x, m, I m > 1 {‘primes’} E ‘prime ’))
V data = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
(22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]
L(n, cnt) data
partition(n, cnt)- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
ALGOL 68
BEGIN # find the lowest n distinct primes that sum to an integer x #
INT max number = 100 000; # largest number we will consider #
# sieve the primes to max number #
[ 1 : max number ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := ODD i OD;
prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
IF prime[ s ] THEN
FOR p FROM s * s BY s TO UPB prime DO prime[ p ] := FALSE OD
FI
OD;
[ 1 : 0 ]INT no partition; # empty array - used if can't partition #
# returns n partitioned into p primes or an empty array if n can't be #
# partitioned into p primes, the first prime to try is in pstart #
PROC partition from = ( INT n, p, pstart )[]INT:
IF p < 1 OR n < 2 OR pstart < 2 THEN # invalid parameters #
no partition
ELIF p = 1 THEN # partition into 1 prime - n must be prime #
IF NOT prime[ n ] THEN no partition ELSE n FI
ELIF p = 2 THEN # partition into a pair of primes #
INT half n = n OVER 2;
INT p1 := 0, p2 := 0;
BOOL found := FALSE;
FOR p pos FROM pstart TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
p2 := n - p pos;
found := prime[ p2 ]
FI
OD;
IF NOT found THEN no partition ELSE ( p1, p2 ) FI
ELSE # partition into 3 or more primes #
[ 1 : p ]INT p2;
INT half n = n OVER 2;
INT p1 := 0;
BOOL found := FALSE;
FOR p pos FROM pstart TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
[]INT sub partition = partition from( n - p1, p - 1, p pos + 1 );
IF found := UPB sub partition = p - 1 THEN
# have p - 1 primes summing to n - p1 #
p2[ 1 ] := p1;
p2[ 2 : p ] := sub partition
FI
FI
OD;
IF NOT found THEN no partition ELSE p2 FI
FI # partition from # ;
# returns the partition of n into p primes or an empty array if that is #
# not possible #
PROC partition = ( INT n, p )[]INT: partition from( n, p, 2 );
# show the first partition of n into p primes, if that is possible #
PROC show partition = ( INT n, p )VOID:
BEGIN
[]INT primes = partition( n, p );
STRING partition info = whole( n, -6 ) + " with " + whole( p, -2 )
+ " prime" + IF p = 1 THEN " " ELSE "s" FI + ": ";
IF UPB primes < LWB primes THEN
print( ( "Partitioning ", partition info, "is not possible" ) )
ELSE
print( ( "Partitioned ", partition info ) );
print( ( whole( primes[ LWB primes ], 0 ) ) );
FOR p pos FROM LWB primes + 1 TO UPB primes DO
print( ( "+", whole( primes[ p pos ], 0 ) ) )
OD
FI;
print( ( newline ) )
END # show partition # ;
# test cases #
show partition( 99809, 1 );
show partition( 18, 2 );
show partition( 19, 3 );
show partition( 20, 4 );
show partition( 2017, 24 );
show partition( 22699, 1 );
show partition( 22699, 2 );
show partition( 22699, 3 );
show partition( 22699, 4 );
show partition( 40355, 3 )
END- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioning 20 with 4 primes: is not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
APL
primepart←{
sieve←{
(⊃{0@(1↓⍺×⍳⌊(⍴⍵)÷⍺)⊢⍵}/(1↓⍳⍵),⊂(0,1↓⍵/1))/⍳⍵
}
part←{
0=⍴⍺⍺:⍬
⍵=1:(⍺⍺=⍺)/⍺⍺
0≠⍴r←(⍺-⊃⍺⍺)((1↓⍺⍺)∇∇)⍵-1:(⊃⍺⍺),r
⍺((1↓⍺⍺)∇∇)⍵
}
⍺((sieve ⍺)part)⍵
}
primepart_test←{
tests←(99809 1)(18 2)(19 3)(20 4)(2017 24)
tests,←(22699 1)(22699 2)(22699 3)(22699 4)(40355 3)
{
x n←⍵
p←x primepart n
⍞←'Partition ',(⍕x),' with ',(⍕n),' primes: '
0=⍴p:⍞←'not possible.',⎕TC[2]
⍞←(1↓∊'+',¨⍕¨p),⎕TC[2]
}¨tests
}
- Output:
primepart_test⍬ Partition 99809 with 1 primes: 99809 Partition 18 with 2 primes: 5+13 Partition 19 with 3 primes: 3+5+11 Partition 20 with 4 primes: not possible. Partition 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 with 1 primes: 22699 Partition 22699 with 2 primes: 2+22697 Partition 22699 with 3 primes: 3+5+22691 Partition 22699 with 4 primes: 2+3+43+22651 Partition 40355 with 3 primes: 3+139+40213
BASIC
10 DIM P%(13000),PR(30),I%(50),N(50),NP%(50),CP(50): MP=99809!
20 FOR P=2 TO SQR(MP)
30 PRINT CHR$(13);"Sieving... ";P;
40 FOR C=P*P TO MP STEP P
50 B=FIX(C/8): V=C-B*8
60 P%(B) = P%(B) OR 2^V
70 NEXT C,P
80 PRINT CHR$(13);"Sieving done "
90 READ N,NP%
100 IF N=0 THEN END
110 PRINT:PRINT "Partitioning";N;"with";NP%;"primes:"
120 S=1: N(0)=N: NP%(0)=NP%: I%(0)=1: CP(0)=1
130 IF S=0 THEN PRINT CHR$(13);"Impossible":GOTO 90
140 S=S-1: N=N(S): NP%=NP%(S): I%=I%(S): CP=CP(S)
150 CP=CP+1
160 B=FIX(CP/8):V=CP-B*8
170 IF P%(B) AND 2^V GOTO 150
175 PRINT CHR$(13);"@";CP;
180 IF N<CP GOTO 130
190 IF NP%=1 THEN 240
200 PR(I%)=CP
210 CP(S)=CP
220 N(S+1)=N-CP: NP%(S+1)=NP%-1: CP(S+1)=CP: I%(S+1)=I%+1: S=S+2
230 GOTO 130
240 B=FIX(N/8):V=N-B*8
250 IF P%(B) AND 2^V GOTO 130
260 PR(I%)=N
270 PRINT CHR$(13);PR(1);
280 FOR J%=2 TO I%: PRINT "+";PR(J%);: NEXT J%
290 PRINT
300 GOTO 90
310 DATA 99809,1, 18,2, 19,3, 20,4, 2017,24
320 DATA 22699,1, 22699,2, 22688,3, 22699,4, 40355,3, 0,0
- Output:
Sieving done Partitioning 99809 with 1 primes: 99809 Partitioning 18 with 2 primes: 5 + 13 Partitioning 19 with 3 primes: 3 + 5 + 11 Partitioning 20 with 4 primes: Impossible Partitioning 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partitioning 22699 with 1 primes: 22699 Partitioning 22699 with 2 primes: 2 + 22697 Partitioning 22688 with 3 primes: 2 + 7 + 22679 Partitioning 22699 with 4 primes: 2 + 3 + 43 + 22651 Partitioning 40355 with 3 primes: 3 + 139 + 40213
BCPL
get "libhdr"
let sieve(n, prime) be
$( let i = 2
0!prime := false
1!prime := false
for i = 2 to n do i!prime := true
while i*i <= n
$( let j = i*i
while j <= n
$( j!prime := false
j := j+i
$)
i := i+1
$)
$)
let partition(x, n, prime, p, part) =
p > x -> false,
n = 1 -> valof $( !part := x; resultis x!prime $),
valof
$( p := p+1 repeatuntil p!prime
!part := p
if partition(x-p, n-1, prime, p, part+1) resultis true
resultis partition(x, n, prime, p, part)
$)
let showpart(n, part) be
$( writef("%N", !part)
unless n=1 do
$( wrch('+')
showpart(n-1, part+1)
$)
$)
let show(x, n, prime) be
$( let part = vec 32
writef("Partitioned %N with %N prime%S: ", x, n, n=1->"", "s")
test partition(x, n, prime, 1, part)
do showpart(n, part)
or writes("not possible")
newline()
$)
let start() be
$( let prime = getvec(100000)
let tests = table 99809,1, 18,2, 19,3, 20,4, 2017,24,
22699,1, 22699,2, 22699,3, 22699,4, 40355,3
sieve(100000, prime)
for t = 0 to 9 do show(tests!(t*2), tests!(t*2+1), prime)
freevec(prime)
$)- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
C
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct bit_array_tag {
uint32_t size;
uint32_t* array;
} bit_array;
bool bit_array_create(bit_array* b, uint32_t size) {
uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t));
if (array == NULL)
return false;
b->size = size;
b->array = array;
return true;
}
void bit_array_destroy(bit_array* b) {
free(b->array);
b->array = NULL;
}
void bit_array_set(bit_array* b, uint32_t index, bool value) {
assert(index < b->size);
uint32_t* p = &b->array[index >> 5];
uint32_t bit = 1 << (index & 31);
if (value)
*p |= bit;
else
*p &= ~bit;
}
bool bit_array_get(const bit_array* b, uint32_t index) {
assert(index < b->size);
uint32_t bit = 1 << (index & 31);
return (b->array[index >> 5] & bit) != 0;
}
typedef struct sieve_tag {
uint32_t limit;
bit_array not_prime;
} sieve;
bool sieve_create(sieve* s, uint32_t limit) {
if (!bit_array_create(&s->not_prime, limit + 1))
return false;
bit_array_set(&s->not_prime, 0, true);
bit_array_set(&s->not_prime, 1, true);
for (uint32_t p = 2; p * p <= limit; ++p) {
if (bit_array_get(&s->not_prime, p) == false) {
for (uint32_t q = p * p; q <= limit; q += p)
bit_array_set(&s->not_prime, q, true);
}
}
s->limit = limit;
return true;
}
void sieve_destroy(sieve* s) {
bit_array_destroy(&s->not_prime);
}
bool is_prime(const sieve* s, uint32_t n) {
assert(n <= s->limit);
return bit_array_get(&s->not_prime, n) == false;
}
bool find_prime_partition(const sieve* s, uint32_t number, uint32_t count,
uint32_t min_prime, uint32_t* p) {
if (count == 1) {
if (number >= min_prime && is_prime(s, number)) {
*p = number;
return true;
}
return false;
}
for (uint32_t prime = min_prime; prime < number; ++prime) {
if (!is_prime(s, prime))
continue;
if (find_prime_partition(s, number - prime, count - 1,
prime + 1, p + 1)) {
*p = prime;
return true;
}
}
return false;
}
void print_prime_partition(const sieve* s, uint32_t number, uint32_t count) {
assert(count > 0);
uint32_t* primes = malloc(count * sizeof(uint32_t));
if (primes == NULL) {
fprintf(stderr, "Out of memory\n");
return;
}
if (!find_prime_partition(s, number, count, 2, primes)) {
printf("%u cannot be partitioned into %u primes.\n", number, count);
} else {
printf("%u = %u", number, primes[0]);
for (uint32_t i = 1; i < count; ++i)
printf(" + %u", primes[i]);
printf("\n");
}
free(primes);
}
int main() {
const uint32_t limit = 100000;
sieve s = { 0 };
if (!sieve_create(&s, limit)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
print_prime_partition(&s, 99809, 1);
print_prime_partition(&s, 18, 2);
print_prime_partition(&s, 19, 3);
print_prime_partition(&s, 20, 4);
print_prime_partition(&s, 2017, 24);
print_prime_partition(&s, 22699, 1);
print_prime_partition(&s, 22699, 2);
print_prime_partition(&s, 22699, 3);
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
sieve_destroy(&s);
return 0;
}
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
C#
using System;
using System.Collections;
using System.Collections.Generic;
using static System.Linq.Enumerable;
public static class Rosetta
{
static void Main()
{
foreach ((int x, int n) in new [] {
(99809, 1),
(18, 2),
(19, 3),
(20, 4),
(2017, 24),
(22699, 1),
(22699, 2),
(22699, 3),
(22699, 4),
(40355, 3)
}) {
Console.WriteLine(Partition(x, n));
}
}
public static string Partition(int x, int n) {
if (x < 1 || n < 1) throw new ArgumentOutOfRangeException("Parameters must be positive.");
string header = $"{x} with {n} {(n == 1 ? "prime" : "primes")}: ";
int[] primes = SievePrimes(x).ToArray();
if (primes.Length < n) return header + "not enough primes";
int[] solution = CombinationsOf(n, primes).FirstOrDefault(c => c.Sum() == x);
return header + (solution == null ? "not possible" : string.Join("+", solution);
}
static IEnumerable<int> SievePrimes(int bound) {
if (bound < 2) yield break;
yield return 2;
BitArray composite = new BitArray((bound - 1) / 2);
int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
for (int i = 0; i < limit; i++) {
if (composite[i]) continue;
int prime = 2 * i + 3;
yield return prime;
for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
}
for (int i = limit; i < composite.Count; i++) {
if (!composite[i]) yield return 2 * i + 3;
}
}
static IEnumerable<int[]> CombinationsOf(int count, int[] input) {
T[] result = new T[count];
foreach (int[] indices in Combinations(input.Length, count)) {
for (int i = 0; i < count; i++) result[i] = input[indices[i]];
yield return result;
}
}
static IEnumerable<int[]> Combinations(int n, int k) {
var result = new int[k];
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0) {
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n) {
result[index++] = value++;
stack.Push(value);
if (index == k) {
yield return result;
break;
}
}
}
}
}
- Output:
99809 with 1 prime: 99809 18 with 2 primes: 5+13 19 with 3 primes: 3+5+11 20 with 4 primes: not possible 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 22699 with 1 prime: 22699 22699 with 2 primes: 2+22697 22699 with 3 primes: 3+5+22691 22699 with 4 primes: 2+3+43+22651 40355 with 3 primes: 3+139+40213
C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
std::vector<int> primes;
struct Seq {
public:
bool empty() {
return p < 0;
}
int front() {
return p;
}
void popFront() {
if (p == 2) {
p++;
} else {
p += 2;
while (!empty() && !isPrime(p)) {
p += 2;
}
}
}
private:
int p = 2;
bool isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
};
// generate the first 50,000 primes and call it good
void init() {
Seq seq;
while (!seq.empty() && primes.size() < 50000) {
primes.push_back(seq.front());
seq.popFront();
}
}
bool findCombo(int k, int x, int m, int n, std::vector<int>& combo) {
if (k >= m) {
int sum = 0;
for (int idx : combo) {
sum += primes[idx];
}
if (sum == x) {
auto word = (m > 1) ? "primes" : "prime";
printf("Partitioned %5d with %2d %s ", x, m, word);
for (int idx = 0; idx < m; ++idx) {
std::cout << primes[combo[idx]];
if (idx < m - 1) {
std::cout << '+';
} else {
std::cout << '\n';
}
}
return true;
}
} else {
for (int j = 0; j < n; j++) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j;
bool foundCombo = findCombo(k + 1, x, m, n, combo);
if (foundCombo) {
return true;
}
}
}
}
return false;
}
void partition(int x, int m) {
if (x < 2 || m < 1 || m >= x) {
throw std::runtime_error("Invalid parameters");
}
std::vector<int> filteredPrimes;
std::copy_if(
primes.cbegin(), primes.cend(),
std::back_inserter(filteredPrimes),
[x](int a) { return a <= x; }
);
int n = filteredPrimes.size();
if (n < m) {
throw std::runtime_error("Not enough primes");
}
std::vector<int> combo;
combo.resize(m);
if (!findCombo(0, x, m, n, combo)) {
auto word = (m > 1) ? "primes" : "prime";
printf("Partitioned %5d with %2d %s: (not possible)\n", x, m, word);
}
}
int main() {
init();
std::vector<std::pair<int, int>> a{
{99809, 1},
{ 18, 2},
{ 19, 3},
{ 20, 4},
{ 2017, 24},
{22699, 1},
{22699, 2},
{22699, 3},
{22699, 4},
{40355, 3}
};
for (auto& p : a) {
partition(p.first, p.second);
}
return 0;
}
- Output:
Partitioned 99809 with 1 prime 99809 Partitioned 18 with 2 primes 5+13 Partitioned 19 with 3 primes 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime 22699 Partitioned 22699 with 2 primes 2+22697 Partitioned 22699 with 3 primes 3+5+22691 Partitioned 22699 with 4 primes 2+3+43+22651 Partitioned 40355 with 3 primes 3+139+40213
CLU
isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0 = 0 then return(s) end
x1: int := (x0 + s/x0) / 2
while x1 < x0 do
x0, x1 := x1, (x0 + s/x0) / 2
end
return(x0)
end isqrt
primes = proc (n: int) returns (sequence[int])
prime: array[bool] := array[bool]$fill(1, n, true)
prime[1] := false
for p: int in int$from_to(2, isqrt(n)) do
for c: int in int$from_to_by(p*p, n, p) do
prime[c] := false
end
end
pr: array[int] := array[int]$predict(1, n)
for p: int in array[bool]$indexes(prime) do
if prime[p] then array[int]$addh(pr, p) end
end
return(sequence[int]$a2s(pr))
end primes
partition_sum = proc (x, n: int, nums: sequence[int])
returns (sequence[int])
signals (impossible)
if n<=0 cor sequence[int]$empty(nums) then signal impossible end
if n=1 then
for k: int in sequence[int]$elements(nums) do
if x=k then return(sequence[int]$[x]) end
end
signal impossible
end
k: int := sequence[int]$bottom(nums)
rest: sequence[int] := sequence[int]$reml(nums)
return(sequence[int]$addl(partition_sum(x-k, n-1, rest), k))
except when impossible:
return(partition_sum(x, n, rest))
resignal impossible
end
end partition_sum
prime_partition = proc (x, n: int)
returns (sequence[int])
signals (impossible)
return(partition_sum(x, n, primes(x))) resignal impossible
end prime_partition
format_sum = proc (nums: sequence[int]) returns (string)
result: string := ""
for n: int in sequence[int]$elements(nums) do
result := result || "+" || int$unparse(n)
end
return(string$rest(result, 2))
end format_sum
start_up = proc ()
test = struct[x: int, n: int]
tests: sequence[test] := sequence[test]$[
test${x:99809,n:1}, test${x:18,n:2}, test${x:19,n:3}, test${x:20,n:4},
test${x:2017,n:24}, test${x:22699,n:1}, test${x:22699,n:2},
test${x:22699,n:3}, test${x:22699,n:4}, test${x:40355,n:3}
]
po: stream := stream$primary_output()
for t: test in sequence[test]$elements(tests) do
stream$puts(po, "Partitioned " || int$unparse(t.x) || " with "
|| int$unparse(t.n) || " primes: ")
stream$putl(po, format_sum(prime_partition(t.x, t.n)))
except when impossible:
stream$putl(po, "not possible.")
end
end
end start_up- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible. Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Cowgol
include "cowgol.coh";
const MAXPRIM := 100000;
const MAXPRIM_B := (MAXPRIM >> 3) + 1;
var primebits: uint8[MAXPRIM_B];
typedef ENTRY_T is @indexof primebits;
sub pentry(n: uint32): (ent: ENTRY_T, bit: uint8) is
ent := (n >> 3) as ENTRY_T;
bit := (n & 7) as uint8;
end sub;
sub setprime(n: uint32, prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
var one: uint8 := 1;
primebits[ent] := primebits[ent] & ~(one << bit);
primebits[ent] := primebits[ent] | (prime << bit);
end sub;
sub prime(n: uint32): (prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
prime := (primebits[ent] >> bit) & 1;
end sub;
sub sieve() is
MemSet(&primebits[0], 0xFF, @bytesof primebits);
setprime(0, 0);
setprime(1, 0);
var p: uint32 := 2;
while p*p <= MAXPRIM loop
var c := p*p;
while c <= MAXPRIM loop
setprime(c, 0);
c := c + p;
end loop;
p := p + 1;
end loop;
end sub;
sub nextprime(p: uint32): (r: uint32) is
r := p;
loop
r := r + 1;
if prime(r) != 0 then break; end if;
end loop;
end sub;
sub partition(x: uint32, n: uint8, part: [uint32]): (r: uint8) is
record State is
x: uint32;
n: uint8;
p: uint32;
part: [uint32];
end record;
var stack: State[128];
var sp: @indexof stack := 0;
sub Push(x: uint32, n: uint8, p: uint32, part: [uint32]) is
stack[sp].x := x;
stack[sp].n := n;
stack[sp].p := p;
stack[sp].part := part;
sp := sp + 1;
end sub;
sub Pull(): (x: uint32, n: uint8, p: uint32, part: [uint32]) is
sp := sp - 1;
x := stack[sp].x;
n := stack[sp].n;
p := stack[sp].p;
part := stack[sp].part;
end sub;
r := 0;
Push(x, n, 1, part);
while sp > 0 loop
var p: uint32;
(x, n, p, part) := Pull();
p := nextprime(p);
if x < p then
continue;
end if;
if n == 1 then
if prime(x) != 0 then
r := 1;
[part] := x;
return;
end if;
else
[part] := p;
Push(x, n, p, part);
Push(x-p, n-1, p, @next part);
end if;
end loop;
r := 0;
end sub;
sub showpartition(x: uint32, n: uint8) is
print("Partitioning ");
print_i32(x);
print(" with ");
print_i8(n);
print(" primes: ");
var part: uint32[64];
if partition(x, n, &part[0]) != 0 then
print_i32(part[0]);
var i: @indexof part := 1;
while i < n as @indexof part loop
print_char('+');
print_i32(part[i]);
i := i + 1;
end loop;
else
print("Not possible");
end if;
print_nl();
end sub;
sieve();
record Test is
x: uint32;
n: uint8;
end record;
var tests: Test[] := {
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}
};
var test: @indexof tests := 0;
while test < @sizeof tests loop
showpartition(tests[test].x, tests[test].n);
test := test + 1;
end loop;- Output:
Partitioning 99809 with 1 primes: 99809 Partitioning 18 with 2 primes: 5+13 Partitioning 19 with 3 primes: 3+5+11 Partitioning 20 with 4 primes: Not possible Partitioning 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioning 22699 with 1 primes: 22699 Partitioning 22699 with 2 primes: 2+22697 Partitioning 22699 with 3 primes: 3+5+22691 Partitioning 22699 with 4 primes: 2+3+43+22651 Partitioning 40355 with 3 primes: 3+139+40213
D
import std.array : array;
import std.range : take;
import std.stdio;
bool isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
auto generatePrimes() {
struct Seq {
int p = 2;
bool empty() {
return p < 0;
}
int front() {
return p;
}
void popFront() {
if (p==2) {
p++;
} else {
p += 2;
while (!empty && !p.isPrime) {
p += 2;
}
}
}
}
return Seq();
}
bool findCombo(int k, int x, int m, int n, int[] combo) {
import std.algorithm : map, sum;
auto getPrime = function int(int idx) => primes[idx];
if (k >= m) {
if (combo.map!getPrime.sum == x) {
auto word = (m > 1) ? "primes" : "prime";
writef("Partitioned %5d with %2d %s ", x, m, word);
foreach (i; 0..m) {
write(primes[combo[i]]);
if (i < m-1) {
write('+');
} else {
writeln();
}
}
return true;
}
} else {
foreach (j; 0..n) {
if (k==0 || j>combo[k-1]) {
combo[k] = j;
bool foundCombo = findCombo(k+1, x, m, n, combo);
if (foundCombo) {
return true;
}
}
}
}
return false;
}
void partition(int x, int m) {
import std.exception : enforce;
import std.algorithm : filter;
enforce(x>=2 && m>=1 && m<x);
auto lessThan = delegate int(int a) => a<=x;
auto filteredPrimes = primes.filter!lessThan.array;
auto n = filteredPrimes.length;
enforce(n>=m, "Not enough primes");
int[] combo = new int[m];
if (!findCombo(0, x, m, n, combo)) {
auto word = (m > 1) ? "primes" : "prime";
writefln("Partitioned %5d with %2d %s: (not possible)", x, m, word);
}
}
int[] primes;
void main() {
// generate first 50,000 and call it good
primes = generatePrimes().take(50_000).array;
auto a = [
[99809, 1],
[ 18, 2],
[ 19, 3],
[ 20, 4],
[ 2017, 24],
[22699, 1],
[22699, 2],
[22699, 3],
[22699, 4],
[40355, 3]
];
foreach(p; a) {
partition(p[0], p[1]);
}
}
- Output:
Partitioned 99809 with 1 prime 99809 Partitioned 18 with 2 primes 5+13 Partitioned 19 with 3 primes 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime 22699 Partitioned 22699 with 2 primes 2+22697 Partitioned 22699 with 3 primes 3+5+22691 Partitioned 22699 with 4 primes 2+3+43+22651 Partitioned 40355 with 3 primes 3+139+40213
EasyLang
maxn = 100000
len sieve[] maxn
global prim[] .
proc mksieve . .
max = sqrt len sieve[]
for d = 2 to max
if sieve[d] = 0
for i = d * d step d to len sieve[]
sieve[i] = 1
.
.
.
for n = 2 to len sieve[]
if sieve[n] = 0
prim[] &= n
.
.
.
mksieve
proc find n k start . found res[] .
found = 0
if k = 0
if n = 0
res[] = [ ]
found = 1
.
return
.
for i = start to len prim[]
p = prim[i]
if p > n
return
.
find (n - p) (k - 1) (i + 1) found r[]
if found = 1
swap res[] r[]
res[] &= p
return
.
.
print "error: need more primes"
.
test[][] = [ [ 99809 1 ] [ 18 2 ] [ 19 3 ] [ 20 4 ] [ 2017 24 ] [ 22699 1 ] [ 22699 2 ] [ 22699 3 ] [ 22699 4 ] [ 40355 3 ] ]
for i to len test[][]
find test[i][1] test[i][2] 1 f res[]
write test[i][1] & "(" & test[i][2] & ") = "
if f = 1
for j = len res[] downto 2
write res[j] & " + "
.
print res[1]
else
print "not possible"
.
.
- Output:
99809(1) = 99809 18(2) = 5 + 13 19(3) = 3 + 5 + 11 20(4) = not possible 2017(24) = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699(1) = 22699 22699(2) = 2 + 22697 22699(3) = 3 + 5 + 22691 22699(4) = 2 + 3 + 43 + 22651 40355(3) = 3 + 139 + 40213
F#
This task uses Extensible Prime Generator (F#)
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017
let rcTask n ng =
let rec fN i g e l = seq{
match i with
|1 -> if isPrime g then yield Some (g::e) else yield None
|_ -> yield! Seq.mapi (fun n a->fN (i-1) (g-a) (a::e) (Seq.skip (n+1) l)) (l|>Seq.takeWhile(fun n->(g-n)>n))|>Seq.concat}
match fN n ng [] primes |> Seq.tryPick id with
|Some n->printfn "%d is the sum of %A" ng n
|_ ->printfn "No Solution"
- Output:
rcTask 1 99089 -> 99089 is the sum of [99089] rcTask 2 18 -> 18 is the sum of [13; 5] rcTask 3 19 -> 19 is the sum of [11; 5; 3] rcTask 4 20 -> No Solution rcTask 24 2017 -> 2017 is the sum of [1129; 97; 79; 73; 71; 67; 61; 59; 53; 47; 43; 41; 37; 31; 29; 23; 19; 17; 13; 11; 7; 5; 3; 2] rcTask 1 2269 -> 2269 is the sum of [2269] rcTask 2 2269 -> 2269 is the sum of [2267; 2] rcTask 3 2269 -> 2269 is the sum of [2243; 23; 3] rcTask 4 2269 -> 2269 is the sum of [2251; 13; 3; 2] rcTask 3 40355 -> 40355 is the sum of [40213; 139; 3]
Factor
USING: formatting fry grouping kernel math.combinatorics
math.parser math.primes sequences ;
: partition ( x n -- str )
over [ primes-upto ] 2dip '[ sum _ = ] find-combination
[ number>string ] map "+" join ;
: print-partition ( x n seq -- )
[ "no solution" ] when-empty
"Partitioned %5d with %2d primes: %s\n" printf ;
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699
4 40355 3 } 2 group
[ first2 2dup partition print-partition ] each
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: no solution Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Fortran
module primes_module
implicit none
integer,allocatable :: p(:)
integer :: a(0:32), b(0:32)
integer,private :: sum_primes, number
contains
!
subroutine setnum(val)
implicit none
integer :: val
number = val
return
end subroutine setnum
!
subroutine init(thesize)
implicit none
integer :: thesize
!
allocate(p(thesize))
p=0
a=0
b=0
return
end subroutine init
!
subroutine genp(high) ! Store all primes up to high in the array p
integer, intent(in) :: high
integer :: i, numprimes, j,k
logical*1 :: bk(0:high)
!
bk = .false.
p = 0
a = 0
b = 0
call eratosthenes(bk , high)
j = 0
numprimes = count(bk)
k = 0
do i = 1,high
if(bk(i))then
j = j+1
p(j) = i
if(j==numprimes)exit !No need to loop more, all primes stored
endif
end do
print*,'numprimes',numprimes, i,p(j)
return
end subroutine genp
subroutine getp(z) ! used to update the zth prime number in the sequence of primes that are being used to partition the integer number.
integer :: z
integer :: w
!
if (a(z) == 0)a(z) = a(z-1)
a(z) = a(z) + 1
b(z) = p(a(z))
return
end subroutine getp
subroutine part(num_found)
integer, intent(in) :: num_found
integer :: i, s, k, r
logical :: bu
a = 0
do i = 1, num_found
call getp(i)
end do
infinite: do
sum_primes = 0
bu = .false.
nextin:do s = 1, num_found
sum_primes = sum_primes + b(s) !Adds the sth prime to sum_primes.
if (sum_primes > number) then !If the sum of primes exceeds number:
if (s == 1)then
exit infinite !If only one prime has been added, exit the infinite loop.
endif
a(s:num_found) = 0 ! Resets the indices of the primes from s to num_found
do r = s - 1, num_found ! Gets the next set of primes from s-1 to num_found
call getp(r)
end do
bu = .true. ! Sets bu to true and exits the loop over the primes
exit nextin
end if
end do nextin
if (.not. bu) then ! If bu is false (meaning the sum of primes does not exceed number)
if (sum_primes == number) exit infinite !We got it so go
if (sum_primes < number) then
call getp(num_found) ! If the sum of primes is less than number, gets the next prime
else
error stop " Something wrong here!"
endif
endif
end do infinite
write( *,'(/,a,1x,i0,1x,a,1x,i0,1x,a)',advance='yes') "Partition", number, "into", num_found,trim(adjustl(list(num_found)))
end subroutine part
!
function list(num_found)
integer, intent(in) :: num_found
integer :: i
character(len=128) :: list
character(len = 10):: pooka
!
write(list,'(i0)') b(1)
if (sum_primes == number) then
do i = 2, num_found
pooka = ''
write(pooka,'(i0)') b(i)
list = trim(list) // " + " // adjustl(pooka)
end do
else
list = "(not possible)"
end if
list = "primes: " // list
end function list
!
subroutine eratosthenes(p , n)
implicit none
!
! dummy arguments
!
integer :: n
logical*1 , dimension(0:*) :: p
intent (in) n
intent (inout) p
!
! local variables
!
integer :: i
integer :: ii
logical :: oddeven
integer :: pr
!
p(0:n) = .false.
p(1) = .false.
p(2) = .true.
oddeven = .true.
do i = 3 , n,2
p(i) = .true.
end do
do i = 2 , int(sqrt(float(n)))
ii = i + i
if( p(i) )then
do pr = i*i , n , ii
p(pr) = .false.
end do
end if
end do
return
end subroutine eratosthenes
end module primes_module
program prime_partition
use primes_module
implicit none
integer :: x, n,i
integer :: xx,yy
integer :: values(10,2)
! The given dataset from Rosetta Code
! partition 99809 with 1 prime.
! partition 18 with 2 primes.
! partition 19 with 3 primes.
! partition 20 with 4 primes.
! partition 2017 with 24 primes.
! partition 22699 with 1, 2, 3, and 4 primes.
! partition 40355 with 3 primes.
values(1,:) = (/99809,1/)
values(2,:) = (/18,2/)
values(3,:) = (/19,3/)
values(4,:) = (/20,4/)
values(5,:) = (/2017,24/)
values(6,:) = (/22699, 1/)
values(7,:) = (/22699, 2/)
values(8,:) = (/22699, 3/)
values(9,:) = (/22699, 4/)
values(10,:) = (/40355, 3/)
i = maxval(values(1:10,1))*2
call init(i) ! Set up a few basics
call genp(i) ! Generate primes up to i
do i = 1,10
call setnum( values(i,1))
call part(values(i,2))
end do
Stop 'Successfully completed'
end program prime_partition
- Output:
Partition 99809 into 1 primes: 99809 Partition 18 into 2 primes : 5 + 13 Partition 19 into 3 primes : 3 + 5 + 11 Partition 20 into 4 primes : (not possible) Partition 2017 into 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition 22699 into 1 primes: 22699 Partition 22699 into 2 primes: 2 + 22697 Partition 22699 into 3 primes: 3 + 5 + 22691 Partition 22699 into 4 primes: 2 + 3 + 43 + 22651 Partition 40355 into 3 primes: 3 + 139 + 40213
FreeBASIC
'#include "isprime.bas"
Function getPrime(idx As Integer) As Integer
Dim As Integer count = 0
Dim As Integer num = 1
Do
num += 1
If isPrime(num) Then count += 1
Loop Until count = idx
Return num
End Function
Function partition(v As Integer, n As Integer, idx As Integer = 0) As String
If n = 1 Then Return Iif(isPrime(v), Str(v), "0")
Do
idx += 1
Dim As Integer np = getPrime(idx)
If np >= Int(v / 2) Then Exit Do
Dim As String res = partition(v - np, n - 1, idx)
If res <> "0" Then Return Str(np) & " + " & res
Loop
Return "0"
End Function
Dim tests(10, 2) As Integer
tests(1, 1) = 99809: tests(1, 2) = 1
tests(2, 1) = 18: tests(2, 2) = 2
tests(3, 1) = 19: tests(3, 2) = 3
tests(4, 1) = 20: tests(4, 2) = 4
tests(5, 1) = 2017: tests(5, 2) = 24
tests(6, 1) = 22699: tests(6, 2) = 1
tests(7, 1) = 22699: tests(7, 2) = 2
tests(8, 1) = 22699: tests(8, 2) = 3
tests(9, 1) = 22699: tests(9, 2) = 4
tests(10, 1) = 40355: tests(10, 2) = 3
For i As Integer = 1 To 10
Dim As Integer v = tests(i, 1)
Dim As Integer n = tests(i, 2)
Dim As String res = partition(v, n)
Print "Partition "; v; " into "; n; " primes: "; Iif(res = "0", "not possible", res)
Next
Sleep
- Output:
Same as Phix entry.
Go
... though uses a sieve to generate the relevant primes.
package main
import (
"fmt"
"log"
)
var (
primes = sieve(100000)
foundCombo = false
)
func sieve(limit uint) []uint {
primes := []uint{2}
c := make([]bool, limit+1) // composite = true
// no need to process even numbers > 2
p := uint(3)
for {
p2 := p * p
if p2 > limit {
break
}
for i := p2; i <= limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
for i := uint(3); i <= limit; i += 2 {
if !c[i] {
primes = append(primes, i)
}
}
return primes
}
func findCombo(k, x, m, n uint, combo []uint) {
if k >= m {
sum := uint(0)
for _, c := range combo {
sum += primes[c]
}
if sum == x {
s := "s"
if m == 1 {
s = " "
}
fmt.Printf("Partitioned %5d with %2d prime%s: ", x, m, s)
for i := uint(0); i < m; i++ {
fmt.Print(primes[combo[i]])
if i < m-1 {
fmt.Print("+")
} else {
fmt.Println()
}
}
foundCombo = true
}
} else {
for j := uint(0); j < n; j++ {
if k == 0 || j > combo[k-1] {
combo[k] = j
if !foundCombo {
findCombo(k+1, x, m, n, combo)
}
}
}
}
}
func partition(x, m uint) error {
if !(x >= 2 && m >= 1 && m < x) {
return fmt.Errorf("x must be at least 2 and m in [1, x)")
}
n := uint(0)
for _, prime := range primes {
if prime <= x {
n++
}
}
if n < m {
return fmt.Errorf("not enough primes")
}
combo := make([]uint, m)
foundCombo = false
findCombo(0, x, m, n, combo)
if !foundCombo {
s := "s"
if m == 1 {
s = " "
}
fmt.Printf("Partitioned %5d with %2d prime%s: (impossible)\n", x, m, s)
}
return nil
}
func main() {
a := [...][2]uint{
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3},
}
for _, p := range a {
err := partition(p[0], p[1])
if err != nil {
log.Println(err)
}
}
}
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (impossible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Haskell
import Data.List (delete, intercalate)
import Data.Numbers.Primes (primes)
import Data.Bool (bool)
-------------------- PRIME PARTITIONS ---------------------
partitions :: Int -> Int -> [Int]
partitions x n
| n <= 1 =
[ x
| x == last ps ]
| otherwise = go ps x n
where
ps = takeWhile (<= x) primes
go ps_ x 1 =
[ x
| x `elem` ps_ ]
go ps_ x n = ((flip bool [] . head) <*> null) (ps_ >>= found)
where
found p =
((flip bool [] . return . (p :)) <*> null)
((go =<< delete p . flip takeWhile ps_ . (>=)) (x - p) (pred n))
-------------------------- TEST ---------------------------
main :: IO ()
main =
mapM_ putStrLn $
(\(x, n) ->
intercalate
" -> "
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partitions x n
in bool
(tail $ concatMap (('+' :) . show) xs)
"(no solution)"
(null xs)
]) <$>
concat
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
, (,) 22699 <$> [1 .. 4]
, [(40355, 3)]
]
------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)
- Output:
(99809,1) -> 99809 (18,2) -> 5+13 (19,3) -> 3+5+11 (20,4) -> (no solution) (2017,24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 (22699,1) -> 22699 (22699,2) -> 2+22697 (22699,3) -> 3+5+22691 (22699,4) -> 2+3+43+22651 (40355,3) -> 3+139+40213
J
load 'format/printf'
NB. I don't know of any way to easily make an idiomatic lazy exploration,
NB. except falling back on explicit imperative control strutures.
NB. However this is clearly not where J shines neither with speed nor elegance.
primes_up_to =: monad def 'p: i. _1 p: 1 + y'
terms_as_text =: monad def '; }: , (": each y),.<'' + '''
search_next_terms =: dyad define
acc=. x NB. -> an accumulator that contains given beginning of the partition.
p=. >0{y NB. -> number of elements wanted in the partition
ns=. >1{y NB. -> candidate values to be included in the partition
sum=. >2{y NB. -> the integer to partition
if. p=0 do.
if. sum=+/acc do. acc return. end.
else.
for_m. i. (#ns)-(p-1) do.
r =. (acc,m{ns) search_next_terms (p-1);((m+1)}.ns);sum
if. #r do. r return. end.
end.
end.
0$0 NB. Empty result if nothing found at the end of this path.
)
NB. Prints a partition of y primes whose sum equals x.
partitioned_in =: dyad define
terms =. (0$0) search_next_terms y;(primes_up_to x);x
if. #terms do.
'As the sum of %d primes, %d = %s' printf y;x; terms_as_text terms
else.
'Didn''t find a way to express %d as a sum of %d different primes.' printf x;y
end.
)
tests=: (99809 1) ; (18 2) ; (19 3) ; (20 4) ; (2017 24) ; (22699 1) ; (22699 2) ; (22699 3) ; (22699 4)
(0&{ partitioned_in 1&{) each tests
- Output:
As the sum of 1 primes, 99809 = 99809 As the sum of 2 primes, 18 = 5 + 13 As the sum of 3 primes, 19 = 3 + 5 + 11 Didn't find a way to express 20 as a sum of 4 different primes. As the sum of 24 primes, 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 As the sum of 1 primes, 22699 = 22699 As the sum of 2 primes, 22699 = 2 + 22697 As the sum of 3 primes, 22699 = 3 + 5 + 22691 As the sum of 4 primes, 22699 = 2 + 3 + 43 + 22651 As the sum of 3 primes, 40355 = 3 + 139 + 40213
Java
import java.util.Arrays;
import java.util.stream.IntStream;
public class PartitionInteger {
private static final int[] primes = IntStream.concat(IntStream.of(2), IntStream.iterate(3, n -> n + 2))
.filter(PartitionInteger::isPrime)
.limit(50_000)
.toArray();
private static boolean isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
private static boolean findCombo(int k, int x, int m, int n, int[] combo) {
boolean foundCombo = false;
if (k >= m) {
if (Arrays.stream(combo).map(i -> primes[i]).sum() == x) {
String s = m > 1 ? "s" : "";
System.out.printf("Partitioned %5d with %2d prime%s: ", x, m, s);
for (int i = 0; i < m; ++i) {
System.out.print(primes[combo[i]]);
if (i < m - 1) System.out.print('+');
else System.out.println();
}
foundCombo = true;
}
} else {
for (int j = 0; j < n; ++j) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j;
if (!foundCombo) {
foundCombo = findCombo(k + 1, x, m, n, combo);
}
}
}
}
return foundCombo;
}
private static void partition(int x, int m) {
if (x < 2 || m < 1 || m >= x) {
throw new IllegalArgumentException();
}
int[] filteredPrimes = Arrays.stream(primes).filter(it -> it <= x).toArray();
int n = filteredPrimes.length;
if (n < m) throw new IllegalArgumentException("Not enough primes");
int[] combo = new int[m];
boolean foundCombo = findCombo(0, x, m, n, combo);
if (!foundCombo) {
String s = m > 1 ? "s" : " ";
System.out.printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, s);
}
}
public static void main(String[] args) {
partition(99809, 1);
partition(18, 2);
partition(19, 3);
partition(20, 4);
partition(2017, 24);
partition(22699, 1);
partition(22699, 2);
partition(22699, 3);
partition(22699, 4);
partition(40355, 3);
}
}
- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
jq
Works with jq and with gojq, the Go implementation of jq
Prime-number functions
# Is the input integer a prime?
def is_prime:
if . == 2 then true
else 2 < . and . % 2 == 1 and
. as $in
| (($in + 1) | sqrt) as $m
| (((($m - 1) / 2) | floor) + 1) as $max
| all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )
end;
# Is the input integer a prime?
# `previous` should be a sorted array of consecutive primes
# greater than 1 and at least including the greatest prime less than (.|sqrt)
def is_prime(previous):
. as $in
| (($in + 1) | sqrt) as $sqrt
| first(previous[]
| if . > $sqrt then 1
elif 0 == ($in % .) then 0
else empty
end) // 1
| . == 1;
# This assumes . is an array of consecutive primes beginning with [2,3]
def next_prime:
. as $previous
| (2 + .[-1] )
| until(is_prime($previous); . + 2) ;
# Emit primes from 2 up
def primes:
# The helper function has arity 0 for TCO
# It expects its input to be an array of previously found primes, in order:
def next:
. as $previous
| ($previous|next_prime) as $next
| $next, (($previous + [$next]) | next) ;
2, 3, ([2,3] | next);
# The primes less than or equal to $x
def primes($x):
label $out
| primes | if . > $x then break $out else . end;Helper function
# Emit a stream consisting of arrays, a, of $n items from the input array,
# preserving order, subject to (a|add) == $sum
def take($n; $sum):
def take:
. as [$m, $in, $s]
| if $m==0 and $s == 0 then []
elif $m==0 or $s <= 0 then empty
else range(0;$in|length) as $i
| $in[$i] as $x
| if $x > $s then empty
else [$x] + ([$m-1, $in[$i+1:], $s - $x] | take)
end
end;
[$n, ., $sum] | take;Partitioning an integer into $n primes
# This function emits a possibly empty stream of arrays.
# Assuming $primes is primes(.), each array corresponds to a
# partition of the input into $n distinct primes.
# The algorithm is unoptimized.
# The output is a stream of arrays, which would be empty
def primepartition($n; $primes):
. as $x
| if $n == 1
then if $primes[-1] == $x then [$x] else null end
else (if $primes[-1] == $x then $primes[:-1] else $primes end) as $primes
| ($primes | take($n; $x))
end ;
# See primepartition/2
def primepartition($n):
. as $x
| if $n == 1
then if is_prime then [.] else null end
else primepartition($n; [primes($x)])
end;
# Compute first(primepartition($n)) for each $n in the array $ary
def primepartitions($ary):
. as $x
| [primes($x)] as $px
| $ary[] as $n
| $x
| first(primepartition($n; $px));
def task($x; $n):
def pp:
if . then join("+") else "(not possible)" end;
if $n|type == "array" then task($x; $n[])
else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"
end;The tasks
task(18; 2),
task(19; 3),
task(20; 4),
task(2017; 24),
task(22699; [1,2,3,4]),
task(40355; 3)- Output:
A partition of 18 into 2 parts: 5+13 A partition of 19 into 3 parts: 3+5+11 A partition of 2017 into 24 parts: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 A partition of 22699 into 1 parts: 22699 A partition of 22699 into 2 parts: 2+22697 A partition of 22699 into 3 parts: 3+5+22691 A partition of 22699 into 4 parts: 2+3+43+22651 A partition of 40355 into 3 parts: 3+139+40213
Julia
using Primes, Combinatorics
function primepartition(x::Int64, n::Int64)
if n == oftype(n, 1)
return isprime(x) ? [x] : Int64[]
else
for combo in combinations(primes(x), n)
if sum(combo) == x
return combo
end
end
end
return Int64[]
end
for (x, n) in [[ 18, 2], [ 19, 3], [ 20, 4], [99807, 1], [99809, 1],
[ 2017, 24],[22699, 1], [22699, 2], [22699, 3], [22699, 4] ,[40355, 3]]
ans = primepartition(x, n)
println("Partition of ", x, " into ", n, " primes: ",
isempty(ans) ? "impossible" : join(ans, " + "))
end
- Output:
Partition of 18 into 2 prime pieces: 5 + 13 Partition of 19 into 3 prime pieces: 3 + 5 + 11 Partition of 20 into 4 prime pieces: impossible Partition of 99807 into 1 prime piece: impossible Partition of 99809 into 1 prime piece: 99809 Partition of 2017 into 24 prime pieces: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition of 22699 into 1 prime piece: 22699 Partition of 22699 into 2 prime pieces: 2 + 22697 Partition of 22699 into 3 prime pieces: 3 + 5 + 22691 Partition of 22699 into 4 prime pieces: 2 + 3 + 43 + 22651 Partition of 40355 into 3 prime pieces: 3 + 139 + 40213
Kotlin
// version 1.1.2
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
import kotlin.coroutines.experimental.*
val primes = generatePrimes().take(50_000).toList() // generate first 50,000 say
var foundCombo = false
fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun generatePrimes() =
buildSequence {
yield(2)
var p = 3
while (p <= Int.MAX_VALUE) {
if (isPrime(p)) yield(p)
p += 2
}
}
fun findCombo(k: Int, x: Int, m: Int, n: Int, combo: IntArray) {
if (k >= m) {
if (combo.sumBy { primes[it] } == x) {
val s = if (m > 1) "s" else " "
print("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: ")
for (i in 0 until m) {
print(primes[combo[i]])
if (i < m - 1) print("+") else println()
}
foundCombo = true
}
}
else {
for (j in 0 until n) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j
if (!foundCombo) findCombo(k + 1, x, m, n, combo)
}
}
}
}
fun partition(x: Int, m: Int) {
require(x >= 2 && m >= 1 && m < x)
val filteredPrimes = primes.filter { it <= x }
val n = filteredPrimes.size
if (n < m) throw IllegalArgumentException("Not enough primes")
val combo = IntArray(m)
foundCombo = false
findCombo(0, x, m, n, combo)
if (!foundCombo) {
val s = if (m > 1) "s" else " "
println("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: (not possible)")
}
}
fun main(args: Array<String>) {
val a = arrayOf(
99809 to 1,
18 to 2,
19 to 3,
20 to 4,
2017 to 24,
22699 to 1,
22699 to 2,
22699 to 3,
22699 to 4,
40355 to 3
)
for (p in a) partition(p.first, p.second)
}
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Lingo
Using the prime generator class "sieve" from task Extensible prime generator#Lingo.
----------------------------------------
-- returns a sorted list of the <cnt> smallest unique primes that add up to <n>,
-- or FALSE if there is no such partition of primes for <n>
----------------------------------------
on getPrimePartition (n, cnt, primes, ptr, res)
if voidP(primes) then
primes = _global.sieve.getPrimesInRange(2, n)
ptr = 1
res = []
end if
if cnt=1 then
if primes.getPos(n)>=ptr then
res.addAt(1, n)
if res.count=cnt+ptr-1 then
return res
end if
return TRUE
end if
else
repeat with i = ptr to primes.count
p = primes[i]
ok = getPrimePartition(n-p, cnt-1, primes, i+1, res)
if ok then
res.addAt(1, p)
if res.count=cnt+ptr-1 then
return res
end if
return TRUE
end if
end repeat
end if
return FALSE
end
----------------------------------------
-- gets partition, prints formatted result
----------------------------------------
on showPrimePartition (n, cnt)
res = getPrimePartition(n, cnt)
if res=FALSE then res = "not prossible"
else res = implode("+", res)
put "Partitioned "&n&" with "&cnt&" primes: " & res
end
----------------------------------------
-- implodes list into string
----------------------------------------
on implode (delim, tList)
str = ""
repeat with i=1 to tList.count
put tList[i]&delim after str
end repeat
delete char (str.length+1-delim.length) to str.length of str
return str
end-- main
_global.sieve = script("sieve").new()
showPrimePartition(99809, 1)
showPrimePartition(18, 2)
showPrimePartition(19, 3)
showPrimePartition(20, 4)
showPrimePartition(2017, 24)
showPrimePartition(22699, 1)
showPrimePartition(22699, 2)
showPrimePartition(22699, 3)
showPrimePartition(22699, 4)
showPrimePartition(40355, 3)- Output:
-- "Partitioned 99809 with 1 primes: 99809" -- "Partitioned 18 with 2 primes: 5+13" -- "Partitioned 19 with 3 primes: 3+5+11" -- "Partitioned 20 with 4 primes: not prossible" -- "Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129" -- "Partitioned 22699 with 1 primes: 22699" -- "Partitioned 22699 with 2 primes: 2+22697" -- "Partitioned 22699 with 3 primes: 3+5+22691" -- "Partitioned 22699 with 4 primes: 2+3+43+22651" -- "Partitioned 40355 with 3 primes: 3+139+40213"
Mathematica /Wolfram Language
NextPrimeMemo[n_] := (NextPrimeMemo[n] = NextPrime[n]);(*This improves performance by 30% or so*)
PrimeList[count_] := Prime/@Range[count];(*Just a helper to create an initial list of primes of the desired length*)
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*)
NextCandidate[{list_, target_}] :=
With[
{len = Length@list, nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]},
Which[
{} == nextHead, {{}, target},
Total[nextHead] == target && Length@nextHead == len, {nextHead, target},
True, {NestWhile[AppendPrime, MapAt[NextPrimeMemo, nextHead, -1], Length[#] < Length[list] &], target}
]
];(*This is the meat of the matter. If it determines that the job is impossible, it returns a structure with an empty list of summands. If the input satisfies the success criteria, it just returns it (this will be our fixed point). Otherwise, it generates a subsequent candidate.*)
FormatResult[{list_, number_}, targetCount_] :=
StringForm[
"Partitioned `1` with `2` prime`4`: `3`",
number,
targetCount,
If[0 == Length@list, "no solutions found", StringRiffle[list, "+"]],
If[1 == Length@list, "", "s"]]; (*Just a helper for pretty-printing the output*)
PrimePartition[number_, count_] := FixedPoint[NextCandidate, {PrimeList[count], number}];(*This is where things kick off. NextCandidate will eventually return the failure format or a success, and either of those are fixed points of the function.*)
TestCases =
{
{99809, 1},
{18, 2},
{19, 3},
{20, 4},
{2017, 24},
{22699, 1},
{22699, 2},
{22699, 3},
{22699, 4},
{40355, 3}
};
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*)
TimedResults // TableForm
- Output:
0.111699 Partitioned 99809 with 1 prime: 99809 0.000407 Partitioned 18 with 2 primes: 5+13 0.000346 Partitioned 19 with 3 primes: 3+5+11 0.000765 Partitioned 20 with 4 primes: no solutions found 0.008381 Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 0.028422 Partitioned 22699 with 1 prime: 22699 0.02713 Partitioned 22699 with 2 primes: 2+22697 20.207 Partitioned 22699 with 3 primes: 3+5+22691 0.357536 Partitioned 22699 with 4 primes: 2+3+43+22651 57.9928 Partitioned 40355 with 3 primes: 3+139+40213
Miranda
main :: [sys_message]
main = [Stdout (lay (map do_test tests))]
tests :: [(num,num)]
tests = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
(22699, 1), (22699, 2), (22699, 3), (22699, 4),
(40355, 3)]
do_test :: (num,num)->[char]
do_test (x,n)
= description ++ format_result (partition x n)
where description = "Partition " ++ show x ++ " with " ++ show n ++ " primes: "
format_result :: maybe [num]->[char]
format_result Nothing = "impossible"
format_result (Just nums) = tl (concat ['+' : show num | num<-nums])
maybe * ::= Nothing | Just *
primes :: [num]
primes = sieve [2..] where sieve (p:x) = p:sieve [n | n<-x; n mod p ~= 0]
partition :: num->num->maybe [num]
partition x n
= search x n (takewhile (<=x) primes)
where search x n [] = Nothing
search x 1 ps = Just [x], if x $in ps
= Nothing, otherwise
search x n (p:ps) = Just (p : result), if step ~= Nothing
= search x n ps, otherwise
where step = search (x-p) (n-1) ps
Just result = step
in :: *->[*]->bool
in x [] = False
in x (x:xs) = True
in x (y:xs) = x $in xs- Output:
Partition 99809 with 1 primes: 99809 Partition 18 with 2 primes: 5+13 Partition 19 with 3 primes: 3+5+11 Partition 20 with 4 primes: impossible Partition 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 with 1 primes: 22699 Partition 22699 with 2 primes: 2+22697 Partition 22699 with 3 primes: 3+5+22691 Partition 22699 with 4 primes: 2+3+43+22651 Partition 40355 with 3 primes: 3+139+40213
Nim
import math, sugar
const N = 100_000
# Fill a sieve of Erathostenes.
var isPrime {.noInit.}: array[2..N, bool]
for item in isPrime.mitems: item = true
for n in 2..int(sqrt(N.toFloat)):
if isPrime[n]:
for k in countup(n * n, N, n):
isPrime[k] = false
# Build list of primes.
let primes = collect(newSeq):
for n in 2..N:
if isPrime[n]: n
proc partition(n, k: int; start = 0): seq[int] =
## Partition "n" in "k" primes starting at position "start" in "primes".
## Return the list of primes or an empty list if partitionning is impossible.
if k == 1:
return if isPrime[n] and n >= primes[start]: @[n] else: @[]
for i in start..primes.high:
let a = primes[i]
if n - a <= 1: break
result = partition(n - a, k - 1, i + 1)
if result.len != 0:
return a & result
when isMainModule:
import strutils
func plural(k: int): string =
if k <= 1: "" else: "s"
for (n, k) in [(99809, 1), (18, 2), (19, 3), (20, 4),
(2017, 24), (22699, 1), (22699, 2),
(22699, 3), (22699, 4), (40355, 3)]:
let part = partition(n, k)
if part.len == 0:
echo n, " cannot be partitionned into ", k, " prime", plural(k)
else:
echo n, " = ", part.join(" + ")
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitionned into 4 primes 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
PARI/GP
partDistinctPrimes(x,n,mn=2)=
{
if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));
if((x-n)%2,
if(mn>2, return(0));
my(t=partDistinctPrimes(x-2,n-1,3));
return(if(t, concat(2,t), 0))
);
if(n==2,
forprime(p=mn,(x-1)\2,
if(isprime(x-p), return([p,x-p]))
);
return(0)
);
if(n<1, return(if(n, 0, [])));
\\ x is the sum of 3 or more odd primes
my(t);
forprime(p=mn,(x-1)\n,
t=partDistinctPrimes(x-p,n-1,p+2);
if(t, return(concat(p,t)))
);
0;
}
displayNicely(x,n)=
{
printf("Partitioned%6d with%3d prime", x, n);
if(n!=1, print1("s"));
my(t=partDistinctPrimes(x,n));
if(t===0, print(": (not possible)"); return);
if(#t, print1(": "t[1]));
for(i=2,#t, print1("+"t[i]));
print();
}
V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
for(i=1,#V, call(displayNicely, V[i]))- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
PascalABC.NET
uses School;
function primepartition(x, n: Integer): List<integer>;
begin
result := new List<integer>;
foreach var combo in Primes(x).Combinations(n) do
if combo.Sum = x then
begin
result := combo.ToList;
exit
end;
end;
begin
foreach var (x, n) in |(18, 2), (19, 3), (20, 4), (99807, 1), (99809, 1),
(2017, 24), (22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)| do
begin
var ans := primepartition(x, n);
writeln('Partitioned', x:6, ' with', n:3, ' primes: ',
if ans.Count = 0 then 'impossible' else ans.JoinToString('+'));
end
end.
- Output:
Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: impossible Partitioned 99807 with 1 primes: impossible Partitioned 99809 with 1 primes: 99809 Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Perl
It is tempting to use the partition iterator which takes a "isprime" flag, but this task calls for unique values. Hence the combination iterator over an array of primes makes more sense.
use ntheory ":all";
sub prime_partition {
my($num, $parts) = @_;
return is_prime($num) ? [$num] : undef if $parts == 1;
my @p = @{primes($num)};
my $r;
forcomb { lastfor, $r = [@p[@_]] if vecsum(@p[@_]) == $num; } @p, $parts;
$r;
}
foreach my $test ([18,2], [19,3], [20,4], [99807,1], [99809,1], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]) {
my $partar = prime_partition(@$test);
printf "Partition %5d into %2d prime piece%s %s\n", $test->[0], $test->[1], ($test->[1] == 1) ? ": " : "s:", defined($partar) ? join("+",@$partar) : "not possible";
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Phix
with javascript_semantics requires("1.0.2") -- (join(fmt)) function partition(integer v, n, idx=0) if n=1 then return iff(is_prime(v)?{v}:0) end if while true do idx += 1 integer np = get_prime(idx) if np>=floor(v/2) then exit end if object res = partition(v-np, n-1, idx) if sequence(res) then res = prepend(res,np) return res end if end while return 0 end function constant tests = {{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24}, {22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}} for i=1 to length(tests) do integer {v,n} = tests[i] object res = partition(v,n) res = iff(res=0?"not possible":join(res," + ",fmt:="%d")) printf(1,"Partition %d into %d primes: %s\n",{v,n,res}) end for
- Output:
Partition 99809 into 1 primes: 99809 Partition 18 into 2 primes: 5 + 13 Partition 19 into 3 primes: 3 + 5 + 11 Partition 20 into 4 primes: not possible Partition 2017 into 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition 22699 into 1 primes: 22699 Partition 22699 into 2 primes: 2 + 22697 Partition 22699 into 3 primes: 3 + 5 + 22691 Partition 22699 into 4 primes: 2 + 3 + 43 + 22651 Partition 40355 into 3 primes: 3 + 139 + 40213
Prolog
prime_partition(N, 1, [N], Min):-
is_prime(N),
N > Min,
!.
prime_partition(N, K, [P|Rest], Min):-
K > 1,
is_prime(P),
P > Min,
P < N,
K1 is K - 1,
N1 is N - P,
prime_partition(N1, K1, Rest, P),
!.
prime_partition(N, K, Primes):-
prime_partition(N, K, Primes, 1).
print_primes([Prime]):-
!,
writef('%w\n', [Prime]).
print_primes([Prime|Primes]):-
writef('%w + ', [Prime]),
print_primes(Primes).
print_prime_partition(N, K):-
prime_partition(N, K, Primes),
!,
writef('%w = ', [N]),
print_primes(Primes).
print_prime_partition(N, K):-
writef('%w cannot be partitioned into %w primes.\n', [N, K]).
main:-
find_prime_numbers(100000),
print_prime_partition(99809, 1),
print_prime_partition(18, 2),
print_prime_partition(19, 3),
print_prime_partition(20, 4),
print_prime_partition(2017, 24),
print_prime_partition(22699, 1),
print_prime_partition(22699, 2),
print_prime_partition(22699, 3),
print_prime_partition(22699, 4),
print_prime_partition(40355, 3).
Module for finding prime numbers up to some limit:
:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
find_prime_numbers(N):-
retractall(is_prime(_)),
assertz(is_prime(2)),
init_sieve(N, 3),
sieve(N, 3).
init_sieve(N, P):-
P > N,
!.
init_sieve(N, P):-
assertz(is_prime(P)),
Q is P + 2,
init_sieve(N, Q).
sieve(N, P):-
P * P > N,
!.
sieve(N, P):-
is_prime(P),
!,
S is P * P,
cross_out(S, N, P),
Q is P + 2,
sieve(N, Q).
sieve(N, P):-
Q is P + 2,
sieve(N, Q).
cross_out(S, N, _):-
S > N,
!.
cross_out(S, N, P):-
retract(is_prime(S)),
!,
Q is S + 2 * P,
cross_out(Q, N, P).
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
Python
from itertools import combinations as cmb
def isP(n):
if n == 2:
return True
if n % 2 == 0:
return False
return all(n % x > 0 for x in range(3, int(n ** 0.5) + 1, 2))
def genP(n):
p = [2]
p.extend([x for x in range(3, n + 1, 2) if isP(x)])
return p
data = [
(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
(22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]
for n, cnt in data:
ci = iter(cmb(genP(n), cnt))
while True:
try:
c = next(ci)
if sum(c) == n:
print(' '.join(
[repr((n, cnt)), "->", '+'.join(str(s) for s in c)]
))
break
except StopIteration:
print(repr((n, cnt)) + " -> Not possible")
break
- Output:
(99809, 1) -> 99809 (18, 2) -> 5+13 (19, 3) -> 3+5+11 (20, 4) -> Not possible (2017, 24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 (22699, 1) -> 22699 (22699, 2) -> 2+22697 (22699, 3) -> 3+5+22691 (22699, 4) -> 2+3+43+22651 (40355, 3) -> 3+139+40213
Racket
#lang racket
(require math/number-theory)
(define memoised-next-prime
(let ((m# (make-hash)))
(λ (P) (hash-ref! m# P (λ () (next-prime P))))))
(define (partition-X-into-N-primes X N)
(define (partition-x-into-n-primes-starting-at-P x n P result)
(cond ((= n x 0) result)
((or (= n 0) (= x 0) (> P x)) #f)
(else
(let ((P′ (memoised-next-prime P)))
(or (partition-x-into-n-primes-starting-at-P (- x P) (- n 1) P′ (cons P result))
(partition-x-into-n-primes-starting-at-P x n P′ result))))))
(reverse (or (partition-x-into-n-primes-starting-at-P X N 2 null) (list 'no-solution))))
(define (report-partition X N)
(let ((result (partition-X-into-N-primes X N)))
(printf "partition ~a\twith ~a\tprimes: ~a~%" X N (string-join (map ~a result) " + "))))
(module+ test
(report-partition 99809 1)
(report-partition 18 2)
(report-partition 19 3)
(report-partition 20 4)
(report-partition 2017 24)
(report-partition 22699 1)
(report-partition 22699 2)
(report-partition 22699 3)
(report-partition 22699 4)
(report-partition 40355 3))
- Output:
partition 99809 with 1 primes: 99809 partition 18 with 2 primes: 5 + 13 partition 19 with 3 primes: 3 + 5 + 11 partition 20 with 4 primes: no-solution partition 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 partition 22699 with 1 primes: 22699 partition 22699 with 2 primes: 2 + 22697 partition 22699 with 3 primes: 3 + 5 + 22691 partition 22699 with 4 primes: 2 + 3 + 43 + 22651 partition 40355 with 3 primes: 3 + 139 + 40213
Raku
(formerly Perl 6)
# short circuit for '1' partition
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () }
my @primes = lazy (^Inf).grep: &is-prime;
multi partition ( Int $number, Int $parts where * > 1 = 2 ) {
my @these = @primes[^($number div $parts)];
shift @these if (($number %% 2) && ($parts %% 2)) || (($number % 2) && ($parts % 2));
for @these.combinations($parts - 1) {
my $maybe = $number - .sum;
return (|$_, $maybe) if $maybe.is-prime && ($maybe ∉ $_)
};
()
}
# TESTING
(18,2, 19,3, 20,4, 99807,1, 99809,1, 99820,6, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3)\
.race(:1batch).map: -> $number, $parts {
say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
$parts == 1 ?? ': ' !! 's: ', join '+', partition($number, $parts) || 'not possible'
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 99820 into 6 prime pieces: 3+5+7+11+61+99733 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Refal
$ENTRY Go {
= <Each Test <Tests>>;
};
Tests {
= (99809 1) (18 2) (19 3) (20 4) (2017 24)
(22699 1) (22699 2) (22699 3) (22699 4) (40355 3);
};
Test {
(s.X s.N) =
<Prout 'Partitioned ' <Symb s.X> ' with ' <Symb s.N> ' primes: '
<Format <PrimePartition s.X s.N>>>;
};
Format {
F = 'not possible';
T s.N = <Symb s.N>;
T s.N e.X = <Symb s.N> '+' <Format T e.X>;
};
PrimePartition {
s.X s.N = <Partition s.X s.N <Primes s.X>>;
};
Partition {
s.X 1 e.Nums, e.Nums: {
e.1 s.X e.2 = T s.X;
e.1 = F;
};
s.X s.N = F;
s.X s.N s.Num e.Nums, <Compare s.X s.Num>: '-' =
<Partition s.X s.N e.Nums>;
s.X s.N s.Num e.Nums,
<Partition <- s.X s.Num> <- s.N 1> e.Nums>: {
T e.List = T s.Num e.List;
F = <Partition s.X s.N e.Nums>;
};
};
Primes {
s.N = <Sieve <Iota 2 s.N>>;
};
Iota {
s.End s.End = s.End;
s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};
Cross {
s.Step e.List = <Cross (s.Step 1) s.Step e.List>;
(s.Step s.Skip) = ;
(s.Step 1) s.Item e.List = X <Cross (s.Step s.Step) e.List>;
(s.Step s.N) s.Item e.List = s.Item <Cross (s.Step <- s.N 1>) e.List>;
};
Sieve {
= ;
X e.List = <Sieve e.List>;
s.N e.List = s.N <Sieve <Cross s.N e.List>>;
};
Each {
s.F = ;
s.F t.X e.R = <Mu s.F t.X> <Each s.F e.R>;
};- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
REXX
Modules: How to use
Modules: Source code
First, the needed primes are sieved. Then this program maintains a small array 'work', holding indices to the array 'prim'. The task is solved by manipulating 'work' and check its sum.
-- 25 Mar 2025
include Settings
say 'PARTITION AN INTEGER X INTO N PRIMES'
say version
say
call GetPrimes 100000
call ShowPartition 99809,1
call ShowPartition 18,2
call ShowPartition 19,3
call ShowPartition 20,4
call ShowPartition 2017,24
call ShowPartition 22699,1
call ShowPartition 22699,2
call ShowPartition 22699,3
call ShowPartition 22699,4
call ShowPartition 40355,3
exit
GetPrimes:
procedure expose prim.
arg xx
call Time('r')
say 'Get primes up to' xx'...'
call Primes xx
say Format(Time('e'),,3) 'seconds'; say
return
ShowPartition:
procedure expose prim. work.
arg xx,yy
call Time('r')
s = 0
do i = 1 to yy
work.i = i
end
s = Sumwork(yy)
do z = 1
select
when s = xx then
leave z
when s < xx then do
work.yy = work.yy+1
s = Sumwork(yy)
end
when s > xx then do
do i = yy by -1 to 2 while s > xx
i1 = i-1; a = work.i1+1
if prim.a > xx then
leave z
work.i1 = a
do j = i to yy
a = a+1; work.j = a
end
s = Sumwork(yy)
end
end
end
end
if s = xx then do
p = work.1; z = prim.p
do i = 2 to yy
p = work.i; z = z'+'prim.p
end
end
else do
z = 'not possible'
end
say xx 'partioned into' yy 'primes is' z
say Format(Time('e'),,3) 'seconds'; say
return
Sumwork:
procedure expose prim. work.
arg yy
s = 0
do i = 1 to yy
a = work.i; p = prim.a; s = s+p
end
return s
include Sequences
include Functions
include Constants
include Abend
- Output:
PARTITION AN INTEGER X INTO N PRIMES REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022 Get primes up to 100000... 0.049 seconds 99809 partioned into 1 primes is 99809 0.015 seconds 18 partioned into 2 primes is 5+13 0.000 seconds 19 partioned into 3 primes is 3+5+11 0.000 seconds 20 partioned into 4 primes is not possible 0.000 seconds 2017 partioned into 24 primes is 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 0.000 seconds 22699 partioned into 1 primes is 22699 0.000 seconds 22699 partioned into 2 primes is 2+22697 0.016 seconds 22699 partioned into 3 primes is 3+5+22691 2.869 seconds 22699 partioned into 4 primes is 2+3+43+22651 0.048 seconds 40355 partioned into 3 primes is 3+139+40213 8.227 seconds
Ring
# Project : Partition an integer X into N primes
load "stdlib.ring"
nr = 0
num = 0
list = list(100000)
items = newlist(pow(2,len(list))-1,100000)
while true
nr = nr + 1
if isprime(nr)
num = num + 1
list[num] = nr
ok
if num = 100000
exit
ok
end
powerset(list,100000)
showarray(items,100000)
see nl
func showarray(items,ind)
for p = 1 to 20
if (p > 17 and p < 21) or p = 99809 or p = 2017 or p = 22699 or p = 40355
for n = 1 to len(items)
flag = 0
for m = 1 to ind
if items[n][m] = 0
exit
ok
flag = flag + items[n][m]
next
if flag = p
str = ""
for x = 1 to len(items[n])
if items[n][x] != 0
str = str + items[n][x] + " "
ok
next
str = left(str, len(str) - 1)
str = str + "]"
if substr(str, " ") > 0
see "" + p + " = ["
see str + nl
exit
else
str = ""
ok
ok
next
ok
next
func powerset(list,ind)
num = 0
num2 = 0
items = newlist(pow(2,len(list))-1,ind)
for i = 2 to (2 << len(list)) - 1 step 2
num2 = 0
num = num + 1
for j = 1 to len(list)
if i & (1 << j)
num2 = num2 + 1
if list[j] != 0
items[num][num2] = list[j]
ok
ok
next
next
return itemsOutput:
99809 = [99809] 18 = [5 13] 19 = [3 5 11] 20 = [] 2017 = [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 97 1129] 22699 = [22699] 22699 = [2 22697] 22699 = [3 5 22691] 22699 = [2 3 43 22651] 40355 = [3 139 40213]
Ruby
require "prime"
def prime_partition(x, n)
Prime.each(x).to_a.combination(n).detect{|primes| primes.sum == x}
end
TESTCASES = [[99809, 1], [18, 2], [19, 3], [20, 4], [2017, 24],
[22699, 1], [22699, 2], [22699, 3], [22699, 4], [40355, 3]]
TESTCASES.each do |prime, num|
res = prime_partition(prime, num)
str = res.nil? ? "no solution" : res.join(" + ")
puts "Partitioned #{prime} with #{num} primes: #{str}"
end
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5 + 13 Partitioned 19 with 3 primes: 3 + 5 + 11 Partitioned 20 with 4 primes: no solution Partitioned 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2 + 22697 Partitioned 22699 with 3 primes: 3 + 5 + 22691 Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651 Partitioned 40355 with 3 primes: 3 + 139 + 40213
Rust
// main.rs
mod bit_array;
mod prime_sieve;
use prime_sieve::PrimeSieve;
fn find_prime_partition(
sieve: &PrimeSieve,
number: usize,
count: usize,
min_prime: usize,
primes: &mut Vec<usize>,
index: usize,
) -> bool {
if count == 1 {
if number >= min_prime && sieve.is_prime(number) {
primes[index] = number;
return true;
}
return false;
}
for p in min_prime..number {
if sieve.is_prime(p)
&& find_prime_partition(sieve, number - p, count - 1, p + 1, primes, index + 1)
{
primes[index] = p;
return true;
}
}
false
}
fn print_prime_partition(sieve: &PrimeSieve, number: usize, count: usize) {
let mut primes = vec![0; count];
if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) {
println!("{} cannot be partitioned into {} primes.", number, count);
} else {
print!("{} = {}", number, primes[0]);
for i in 1..count {
print!(" + {}", primes[i]);
}
println!();
}
}
fn main() {
let s = PrimeSieve::new(100000);
print_prime_partition(&s, 99809, 1);
print_prime_partition(&s, 18, 2);
print_prime_partition(&s, 19, 3);
print_prime_partition(&s, 20, 4);
print_prime_partition(&s, 2017, 24);
print_prime_partition(&s, 22699, 1);
print_prime_partition(&s, 22699, 2);
print_prime_partition(&s, 22699, 3);
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
}
// prime_sieve.rs
use crate::bit_array;
pub struct PrimeSieve {
composite: bit_array::BitArray,
}
impl PrimeSieve {
pub fn new(limit: usize) -> PrimeSieve {
let mut sieve = PrimeSieve {
composite: bit_array::BitArray::new(limit / 2),
};
let mut p = 3;
while p * p <= limit {
if !sieve.composite.get(p / 2 - 1) {
let inc = p * 2;
let mut q = p * p;
while q <= limit {
sieve.composite.set(q / 2 - 1, true);
q += inc;
}
}
p += 2;
}
sieve
}
pub fn is_prime(&self, n: usize) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
!self.composite.get(n / 2 - 1)
}
}
// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
}
impl BitArray {
pub fn new(size: usize) -> BitArray {
BitArray {
array: vec![0; (size + 31) / 32],
}
}
pub fn get(&self, index: usize) -> bool {
let bit = 1 << (index & 31);
(self.array[index >> 5] & bit) != 0
}
pub fn set(&mut self, index: usize, new_val: bool) {
let bit = 1 << (index & 31);
if new_val {
self.array[index >> 5] |= bit;
} else {
self.array[index >> 5] &= !bit;
}
}
}
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
Scala
object PartitionInteger {
def sieve(nums: LazyList[Int]): LazyList[Int] =
LazyList.cons(nums.head, sieve((nums.tail) filter (_ % nums.head != 0)))
// An 'infinite' stream of primes, lazy evaluation and memo-ized
private val oddPrimes = sieve(LazyList.from(3, 2))
private val primes = sieve(2 #:: oddPrimes).take(3600 /*50_000*/)
private def findCombo(k: Int, x: Int, m: Int, n: Int, combo: Array[Int]): Boolean = {
var foundCombo = combo.map(i => primes(i)).sum == x
if (k >= m) {
if (foundCombo) {
val s: String = if (m > 1) "s" else ""
printf("Partitioned %5d with %2d prime%s: ", x, m, s)
for (i <- 0 until m) {
print(primes(combo(i)))
if (i < m - 1) print('+') else println()
}
}
} else for (j <- 0 until n if k == 0 || j > combo(k - 1)) {
combo(k) = j
if (!foundCombo) foundCombo = findCombo(k + 1, x, m, n, combo)
}
foundCombo
}
private def partition(x: Int, m: Int): Unit = {
val n: Int = primes.count(it => it <= x)
if (n < m) throw new IllegalArgumentException("Not enough primes")
if (!findCombo(0, x, m, n, new Array[Int](m)))
printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, if (m > 1) "s" else " ")
}
def main(args: Array[String]): Unit = {
partition(99809, 1)
partition(18, 2)
partition(19, 3)
partition(20, 4)
partition(2017, 24)
partition(22699, 1)
partition(22699, 2)
partition(22699, 3)
partition(22699, 4)
partition(40355, 3)
}
}
SETL
program primes_partition;
tests := [[99809,1], [18,2], [19,3], [20,4], [2017,24],
[22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
loop for [x, n] in tests do
nprint("Partitioned",x,"with",n,"primes:");
if (p := partition(x,n)) = om then
print(" not possible");
else
print(" " + (+/["+" + str pr : pr in p])(2..));
end if;
end loop;
proc partition(x,n);
return findpart(x,n,sieve(x));
end proc;
proc findpart(x,n,nums);
if n=1 then
return if x in nums then [x] else om end;
end if;
loop while nums /= [] do
k fromb nums;
if (l := findpart(x-k, n-1, nums)) /= om then
return [k] + l;
end if;
end loop;
return om;
end proc;
proc sieve(n);
primes := [1..n];
primes(1) := om;
loop for p in [2..floor sqrt n] do
loop for c in [p*p, p*p+p..n] do
primes(c) := om;
end loop;
end loop;
return [p : p in primes | p /= om];
end proc;
end program;- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Sidef
func prime_partition(num, parts) {
if (parts == 1) {
return (num.is_prime ? [num] : [])
}
num.primes.combinations(parts, {|*c|
return c if (c.sum == num)
})
return []
}
var tests = [
[ 18, 2], [ 19, 3], [ 20, 4],
[99807, 1], [99809, 1], [ 2017, 24],
[22699, 1], [22699, 2], [22699, 3],
[22699, 4], [40355, 3],
]
for num,parts (tests) {
say ("Partition %5d into %2d prime piece" % (num, parts),
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible')
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Swift
import Foundation
class BitArray {
var array: [UInt32]
init(size: Int) {
array = Array(repeating: 0, count: (size + 31)/32)
}
func get(index: Int) -> Bool {
let bit = UInt32(1) << (index & 31)
return (array[index >> 5] & bit) != 0
}
func set(index: Int, value: Bool) {
let bit = UInt32(1) << (index & 31)
if value {
array[index >> 5] |= bit
} else {
array[index >> 5] &= ~bit
}
}
}
class PrimeSieve {
let composite: BitArray
init(size: Int) {
composite = BitArray(size: size/2)
var p = 3
while p * p <= size {
if !composite.get(index: p/2 - 1) {
let inc = p * 2
var q = p * p
while q <= size {
composite.set(index: q/2 - 1, value: true)
q += inc
}
}
p += 2
}
}
func isPrime(number: Int) -> Bool {
if number < 2 {
return false
}
if (number & 1) == 0 {
return number == 2
}
return !composite.get(index: number/2 - 1)
}
}
func findPrimePartition(sieve: PrimeSieve, number: Int,
count: Int, minPrime: Int,
primes: inout [Int], index: Int) -> Bool {
if count == 1 {
if number >= minPrime && sieve.isPrime(number: number) {
primes[index] = number
return true
}
return false
}
if minPrime >= number {
return false
}
for p in minPrime..<number {
if sieve.isPrime(number: p)
&& findPrimePartition(sieve: sieve, number: number - p,
count: count - 1, minPrime: p + 1,
primes: &primes, index: index + 1) {
primes[index] = p
return true
}
}
return false
}
func printPrimePartition(sieve: PrimeSieve, number: Int, count: Int) {
var primes = Array(repeating: 0, count: count)
if !findPrimePartition(sieve: sieve, number: number, count: count,
minPrime: 2, primes: &primes, index: 0) {
print("\(number) cannot be partitioned into \(count) primes.")
} else {
print("\(number) = \(primes[0])", terminator: "")
for i in 1..<count {
print(" + \(primes[i])", terminator: "")
}
print()
}
}
let sieve = PrimeSieve(size: 100000)
printPrimePartition(sieve: sieve, number: 99809, count: 1)
printPrimePartition(sieve: sieve, number: 18, count: 2)
printPrimePartition(sieve: sieve, number: 19, count: 3)
printPrimePartition(sieve: sieve, number: 20, count: 4)
printPrimePartition(sieve: sieve, number: 2017, count: 24)
printPrimePartition(sieve: sieve, number: 22699, count: 1)
printPrimePartition(sieve: sieve, number: 22699, count: 2)
printPrimePartition(sieve: sieve, number: 22699, count: 3)
printPrimePartition(sieve: sieve, number: 22699, count: 4)
printPrimePartition(sieve: sieve, number: 40355, count: 3)
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
VBScript
' Partition an integer X into N primes
dim p(),a(32),b(32),v,g: redim p(64)
what="99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 3"
t1=split(what," ")
for j=0 to ubound(t1)
t2=split(t1(j)): x=t2(0): n=t2(1)
t3=split(x,"-"): x=clng(t3(0))
if ubound(t3)=1 then y=clng(t3(1)) else y=x
t3=split(n,"-"): n=clng(t3(0))
if ubound(t3)=1 then m=clng(t3(1)) else m=n
genp y 'generate primes in p
for g=x to y
for q=n to m: part: next 'q
next 'g
next 'j
sub genp(high)
p(1)=2: p(2)=3: c=2: i=p(c)+2
do 'i
k=2: bk=false
do while k*k<=i and not bk 'k
if i mod p(k)=0 then bk=true
k=k+1
loop 'k
if not bk then
c=c+1: if c>ubound(p) then redim preserve p(ubound(p)+8)
p(c)=i
end if
i=i+2
loop until p(c)>high 'i
end sub 'genp
sub getp(z)
if a(z)=0 then w=z-1: a(z)=a(w)
a(z)=a(z)+1: w=a(z): b(z)=p(w)
end sub 'getp
function list()
w=b(1)
if v=g then for i=2 to q: w=w&"+"&b(i): next else w="(not possible)"
list="primes: "&w
end function 'list
sub part()
for i=lbound(a) to ubound(a): a(i)=0: next 'i
for i=1 to q: call getp(i): next 'i
do while true: v=0: bu=false
for s=1 to q
v=v+b(s)
if v>g then
if s=1 then exit do
for k=s to q: a(k)=0: next 'k
for r=s-1 to q: call getp(r): next 'r
bu=true: exit for
end if
next 's
if not bu then
if v=g then exit do
if v<g then call getp(q)
end if
loop
wscript.echo "partition "&g&" into "&q&" "&list
end sub 'part
- Output:
partition 99809 into 1 primes: 99809 partition 18 into 2 primes: 5+13 partition 19 into 3 primes: 3+5+11 partition 20 into 4 primes: (not possible) partition 2017 into 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 partition 22699 into 1 primes: 22699 partition 22699 into 2 primes: 2+22697 partition 22699 into 3 primes: 3+5+22691 partition 22699 into 4 primes: 2+3+43+22651 partition 40355 into 3 primes: 3+139+40213
Visual Basic .NET
' Partition an integer X into N primes - 29/03/2017
Option Explicit On
Module PartitionIntoPrimes
Dim p(8), a(32), b(32), v, g, q As Long
Sub Main()
Dim what, t1(), t2(), t3(), xx, nn As String
Dim x, y, n, m As Long
what = "99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 3"
t1 = Split(what, " ")
For j = 0 To UBound(t1)
t2 = Split(t1(j)) : xx = t2(0) : nn = t2(1)
t3 = Split(xx, "-") : x = CLng(t3(0))
If UBound(t3) = 1 Then y = CLng(t3(1)) Else y = x
t3 = Split(nn, "-") : n = CLng(t3(0))
If UBound(t3) = 1 Then m = CLng(t3(1)) Else m = n
genp(y) 'generate primes in p
For g = x To y
For q = n To m : part() : Next 'q
Next 'g
Next 'j
End Sub 'Main
Sub genp(high As Long)
Dim c, i, k As Long
Dim bk As Boolean
p(1) = 2 : p(2) = 3 : c = 2 : i = p(c) + 2
Do 'i
k = 2 : bk = False
Do While k * k <= i And Not bk 'k
If i Mod p(k) = 0 Then bk = True
k = k + 1
Loop 'k
If Not bk Then
c = c + 1 : If c > UBound(p) Then ReDim Preserve p(UBound(p) + 8)
p(c) = i
End If
i = i + 2
Loop Until p(c) > high 'i
End Sub 'genp
Sub getp(z As Long)
Dim w As Long
If a(z) = 0 Then w = z - 1 : a(z) = a(w)
a(z) = a(z) + 1 : w = a(z) : b(z) = p(w)
End Sub 'getp
Function list()
Dim w As String
w = b(1)
If v = g Then
For i = 2 To q : w = w & "+" & b(i) : Next
Else
w = "(not possible)"
End If
Return "primes: " & w
End Function 'list
Sub part()
For i = LBound(a) To UBound(a) : a(i) = 0 : Next 'i
For i = 1 To q : Call getp(i) : Next 'i
Do While True : v = 0
For s = 1 To q
v = v + b(s)
If v > g Then
If s = 1 Then Exit Do
For k = s To q : a(k) = 0 : Next 'k
For r = s - 1 To q : Call getp(r) : Next 'r
Continue Do
End If
Next 's
If v = g Then Exit Do
If v < g Then Call getp(q)
Loop
Console.WriteLine("partition " & g & " into " & q & " " & list())
End Sub 'part
End Module 'PartitionIntoPrimes
- Output:
partition 99809 into 1 primes: 99809 partition 18 into 2 primes: 5+13 partition 19 into 3 primes: 3+5+11 partition 20 into 4 primes: (not possible) partition 2017 into 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 partition 22699 into 1 primes: 22699 partition 22699 into 2 primes: 2+22697 partition 22699 into 3 primes: 3+5+22691 partition 22699 into 4 primes: 2+3+43+22651 partition 40355 into 3 primes: 3+139+40213
Wren
The relevant primes are generated here by a sieve.
import "./math" for Int, Nums
import "./fmt" for Fmt
var primes = Int.primeSieve(1e5)
var foundCombo = false
var findCombo // recursive
findCombo = Fn.new { |k, x, m, n, combo|
if (k >= m) {
if (Nums.sum(combo.map { |i| primes[i] }.toList) == x) {
var s = (m > 1) ? "s" : ""
Fmt.write("Partitioned $5d with $2d prime$s: ", x, m, s)
for (i in 0...m) {
System.write(primes[combo[i]])
System.write((i < m - 1) ? "+" : "\n")
}
foundCombo = true
}
} else {
for (j in 0...n) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j
if (!foundCombo) findCombo.call(k + 1, x, m, n, combo)
}
}
}
}
var partition = Fn.new { |x, m|
if (x < 2 || m < 1 || m >= x) Fiber.abort("Invalid argument(s)")
var n = primes.where { |p| p <= x }.count
if (n < m) Fiber.abort("Not enough primes")
var combo = List.filled(m, 0)
foundCombo = false
findCombo.call(0, x, m, n, combo)
if (!foundCombo) {
var s = (m > 1) ? "s" : ""
Fmt.print("Partitioned $5d with $2d prime$s: (not possible)", x, m, s)
}
}
var a = [
[99809, 1],
[18, 2],
[19, 3],
[20, 4],
[2017, 24],
[22699, 1],
[22699, 2],
[22699, 3],
[22699, 4],
[40355, 3]
]
for (p in a) partition.call(p[0], p[1])
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
zkl
Using the prime generator from task Extensible prime generator#zkl.
// Partition integer N into M unique primes
fcn partition(N,M,idx=0,ps=List()){
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);
var [const] primes=List();
while(sieve.peek()<=N){ primes.append(sieve.next()) }
if(M<2){
z:=primes.find(N);
return(if(Void!=z and z>=idx) ps.append(N) else Void);
}
foreach z in ([idx..primes.len()-1]){
p:=primes[z];
if(p<=N and self.fcn(N-p,M-1,z+1,ps)) return(ps.insert(0,p));
if(p>N) break;
}
Void // no solution
}foreach n,m in (T( T(18,2),T(19,3),T(99809,1),T(20,4),T(2017,24),
T(22699,1),T(22699,2),T(22699,3),T(22699,4),T(40355,3), )){
ps:=partition(n,m);
if(ps) println("Partition %d with %d prime(s): %s".fmt(n,m,ps.concat("+")));
else println("Can not partition %d with %d prime(s)".fmt(n,m));
}- Output:
Partition 18 with 2 prime(s): 5+13 Partition 19 with 3 prime(s): 3+5+11 Partition 99809 with 1 prime(s): 99809 Can not partition 20 with 4 prime(s) Partition 2017 with 24 prime(s): 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 with 1 prime(s): 22699 Partition 22699 with 2 prime(s): 2+22697 Partition 22699 with 3 prime(s): 3+5+22691 Partition 22699 with 4 prime(s): 2+3+43+22651 Partition 40355 with 3 prime(s): 3+139+40213