Partition an integer x into n primes
- 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
- count in factors
- prime decomposition
- factors of an integer
- Sieve of Eratosthenes
- primality by trial division
- factors of a Mersenne number
- trial factoring of a Mersenne number
- sequence of primes by Trial Division
Haskell
<lang haskell>{-# LANGUAGE TupleSections #-}
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)]
, (22699, ) <$> [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</lang>
- 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
Kotlin
<lang scala>// 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)
}</lang>
- 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
Perl 6
<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 !! [] } # 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'
}</lang>
- 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
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
VBScript
<lang vb>' 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 </lang>
- 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
<lang vbnet>' 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 </lang>
- 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
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