Partition an integer x into n primes: Difference between revisions
Content added Content deleted
m (added whitespace to the task's preamble.) |
|||
| Line 1,250: | Line 1,250: | ||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |
||
<lang Mathematica> |
|||
{{incomplete|Mathematica| <br><br> the output for partitioning of <br> '''42017''', '''22699''', and ''' 40355''' <br> isn't shown. <br><br>}} |
|||
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*) |
|||
This can be done with IntegerPartitions: |
|||
<lang Mathematica>partition[x_,n_]:= "Partitioned "<>ToString[x]<>" with "<>ToString[n]<>" primes: "<>StringRiffle[ |
|||
ToString/@First[Sort[Sort/@Select[IntegerPartitions[x,{n},Prime/@Range[PrimePi[x]]],Length[Union[#]]===n&]],{"impossible"}] |
|||
,"+"] |
|||
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*) |
|||
partition[18, 2] |
|||
partition[19, 3] |
|||
NextCandidate[{list_, target_}] := |
|||
partition[20, 4]</lang> |
|||
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 |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Partitioned |
0.111699 Partitioned 99809 with 1 prime: 99809 |
||
Partitioned |
0.000407 Partitioned 18 with 2 primes: 5+13 |
||
Partitioned |
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 |
|||
</pre> |
</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||