Partition an integer x into n primes

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 the following format:

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.

REXX

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. <lang rexx>/*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</lang>

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

Perl 6

Works with: Rakudo version 2017.02

<lang perl6>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 !! 'not possible' } # 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) -> @t { return @t if @t.sum == $number }
   'not possible'

}

1. TESTING

for 18,2, 19,3, 99809,1, 20,4, 99,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

}</lang>

Output:

Partition    18 into  2 prime pieces: 5+13
Partition    19 into  3 prime pieces: 3+5+11
Partition 99809 into  1 prime piece : 99809
Partition    20 into  4 prime pieces: not possible
Partition    99 into  1 prime piece : not possible
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

zkl

Using the prime generator from task Extensible prime generator#zkl. <lang 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

}</lang> <lang zkl>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));

}</lang>

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