CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Partition an integer X into N primes

From Rosetta Code
Partition an integer X into N primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Partition a positive integer   X   into   N   primes.


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   and 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



Haskell[edit]

import Data.List (delete, intercalate)
 
-- PRIME PARTITIONS ----------------------------------------------------------
partition :: Int -> Int -> [Int]
partition x n
| n <= 1 =
[ x
| last ps == x ]
| otherwise = partition_ ps x n
where
ps = takeWhile (<= x) primes
partition_ ps_ x 1 =
[ x
| x `elem` ps_ ]
partition_ ps_ x n =
let found = foldMap partitionsFound ps_
in nullOr found [] (head found)
where
partitionsFound p =
let r = x - p
rs = partition_ (delete p (takeWhile (<= r) ps_)) r (n - 1)
in nullOr rs [] [p : rs]
 
-- TEST ----------------------------------------------------------------------
main :: IO ()
main =
mapM_ putStrLn $
(\(x, n) ->
(intercalate
" -> "
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partition x n
in nullOr xs "(no solution)" (intercalate "+" (show <$> xs))
])) <$>
concat
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
, (\x -> (22699, x)) <$> [1 .. 4]
, [(40355, 3)]
]
 
-- GENERIC --------------------------------------------------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)
 
nullOr
:: Foldable t1
=> t1 a -> t -> t -> t
nullOr expression nullValue orValue =
if null expression
then nullValue
else orValue
 
primes :: [Int]
primes =
2 :
pruned
[3 ..]
(listUnion
[ (p *) <$> [p ..]
| p <- primes ])
where
pruned :: [Int] -> [Int] -> [Int]
pruned (x:xs) (y:ys)
| x < y = x : pruned xs (y : ys)
| x == y = pruned xs ys
| x > y = pruned (x : xs) ys
listUnion :: [[Int]] -> [Int]
listUnion = foldr union []
where
union (x:xs) ys = x : union_ xs ys
union_ (x:xs) (y:ys)
| x < y = x : union_ xs (y : ys)
| x == y = x : union_ xs ys
| x > y = y : union_ (x : xs) ys
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

Perl 6[edit]

Works with: Rakudo version 2017.02
my @primes = 2, 3, 5, -> $p { ($p + 2, $p + 4 ... &is-prime).tail } ... *; # lazy infinite list of primes
 
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! [] } # short circuit for '1' partition
 
multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
my @these = @primes[ ^( @primes.first: * > $number, :k ) ];
for @these.combinations($parts) -> @this { return @this if @this.sum == $number }
[]
}
 
# TESTING
for 18,2, 19,3, 20,4, 99807,1, 99809,1, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3
-> $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  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

REXX[edit]

Usage note:   entering ranges of   X   and   N   numbers (arguments) from the command line:

  X-Y   N-M     ∙∙∙

which means:   partition all integers (inclusive) from   X ──► Y   with   N ──► M   primes.
The   to   number   (Y   or   M)   can be omitted.

/*REXX program  partitions  integer(s)    (greater than unity)   into   N   primes.     */
parse arg what /*obtain an optional list from the C.L.*/
do until what=='' /*possibly process a series of integers*/
parse var what x n what; parse var x x '-' y /*get possible range and # partitions.*/
parse var n n '-' m /*get possible range and # partitions.*/
if x=='' | x=="," then x=19 /*Not specified? Then use the default.*/
if y=='' | y=="," then y=x /* " " " " " " */
if n=='' | n=="," then n= 3 /* " " " " " " */
if m=='' | m=="," then m=n /* " " " " " " */
call genP y /*generate Y number of primes. */
do g=x to y /*partition X ───► Y into partitions.*/
do q=n to m; call part; end /*q*/ /*partition G into Q primes. */
end /*g*/
end /*until*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: arg high; @.1=2; @.2=3; #=2 /*get highest prime, assign some vars. */
do j=@.#+2 by 2 until @.#>high /*only find odd primes from here on. */
do k=2 while k*k<=j /*divide by some known low odd primes. */
if j // @.k==0 then iterate j /*Is J divisible by P? Then ¬ prime.*/
end /*k*/ /* [↓] a prime (J) has been found. */
#=#+1; @.#=j /*bump prime count; assign prime to @.*/
end /*j*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
getP: procedure expose i. p. @.; parse arg z /*bump the prime in the partition list.*/
if i.z==0 then do; _=z-1; i.z=i._; end
i.z=i.z+1; _=i.z; p.z=@._; return 0
/*──────────────────────────────────────────────────────────────────────────────────────*/
list: _=p.1; if $==g then do j=2 to q; _=_ p.j; end; else _= '__(not_possible)'
the= 'primes:'; if q==1 then the= 'prime: '; return the translate(_,"+ ",' _')
/*──────────────────────────────────────────────────────────────────────────────────────*/
part: i.=0; do j=1 for q; call getP j; end /*j*/
do !=0 by 0; $=0 /*!: a DO variable for LEAVE & ITERATE*/
do s=1 for q; $=$+p.s /* [↓] is sum of the primes too large?*/
if $>g then do; if s==1 then leave ! /*perform a quick exit?*/
do k=s to q; i.k=0; end /*k*/
do r=s-1 to q; call getP r; end /*r*/
iterate !
end
end /*s*/
if $==g then leave /*is sum of the primes exactly right ? */
if $ <g then do; call getP q; iterate; end
end /*!*/ /* [↑] Is sum too low? Bump a prime.*/
say 'partitioned' center(g,9) "into" center(q, 5) list()
return

{{out|output|text=  when using the input of:   99809 1   18 2   19 3  20 4   2017 24   22699 1-4   40355

partitioned   99809   into   1   prime:  99809
partitioned    18     into   2   primes: 5+13
partitioned    19     into   3   primes: 3+5+11
partitioned    20     into   4   primes:   (not possible)
partitioned   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
partitioned   22699   into   1   prime:  22699
partitioned   22699   into   2   primes: 2+22697
partitioned   22699   into   3   primes: 3+5+22691
partitioned   22699   into   4   primes: 2+3+43+22651
partitioned   40355   into   3   primes: 3+139+40213

zkl[edit]

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