Find the maximum Z in {(X + Y)==Z} using all the digits 0-9 only once

Question

II want to add two integers with different digits to get a third integer with different digits. At the end, all 10 digits have to be different. So there should be 10 digits in total. How you distribute them is your (or Mathematica's) decision.

Lets say these numbers are $X$, $Y$ and $Z$, so that $X + Y = Z$. There is no rule how many digits a number should have. For example $X$ can have two digits or it can have three digits. What is the maximum possible value for $Z$?

How can I tell Mathematica to chose such two numbers in order to get a third one which satisfies the conditions I impose above? Please explain your answer in simple terms. I am a beginner, and I want to understand the code in the answer so I could do it on my own at some later time.

Answer 1

Brute forcing it: (The edit at the end is a much faster alternative)

n = 9;
IntegerPartitions[n + 1, {3}]
(* {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, {6, 2, 2}, {5, 4, 1}, 
    {5, 3, 2}, {4, 4, 2}, {4, 3, 3}}*)

are the ways to split ten digits.
The numbers on the first row can't produce viable sums, so we need to check only the partitions on the bottom row.
Then:

k = {{5, 3, 2}, {4, 4, 2}, {4, 3, 3}};

and we run (due to memory constraints) the following for each k (x = 1 ...3) (you may use Map instead of Outer)

nums = Union @@ 
   Outer[((If[#[[1]] == #[[2]] + #[[3]], #, ## &[]]) &@(FromDigits /@ 
         Internal`PartitionRagged[##])) &, Permutations[Range[0, n]], 
         k[[x ;; x]], 1];

The first k returns no results and the other two return a bunch.

The larger Z returned is 6021 made by:

{{6021, 5934, 87}, {6021, 5937, 84}, {6021, 5943, 78}, {6021, 5948, 73}, 
 {6021, 5973, 48}, {6021, 5978, 43}, {6021, 5984, 37}, {6021, 5987, 34}}

---

Edit, much faster and less memory usage: (uses this FromDigits syntax )

n = 9;
k = IntegerPartitions[n + 1, {3}];
pn = Permutations[Range[0, n]];
res = {};
Monitor[For[i = 6, i <= Length@k, i++,
  aa = Internal`PartitionRagged[Transpose@pn, k[[i]]];
  bb = FromDigits /@ 
       (If[Length@#< 3, Prepend[#, r@@ConstantArray[0, {3-Length@#, (n + 1)!}]], #]/. 
                                                              r -> Sequence & /@ aa);
  AppendTo[ res, (If[#[[1]] == #[[2]] + #[[3]], -#, ## &[]] & /@    Transpose@bb)]];
 (* Memory recovery *)
 aa =.; bb =.; Share[];, i]
final = Flatten[-Union[Sort /@ res], 1]

Answer 2

I solved many puzzle and problems with LinearProgramming and wrote many answer about this method. For example:

• Given a large binary matrix, find the largest submatrix containing non-zero elements
• Elegant way to partition list to be faster than ParallelTable
• Puzzle with Mathematica
• Elegant solution to the Zebra [logic] Puzzle (“Einstein's Riddle”)

So I didn't repeat common things. If you are interested I can add some comment to this specific problem.

This is the way I'll do. First a function to solve for a specific set of digits for each addendum (obtained by IntegerPartions as of the answer of @Dr.Belisarius):

puzzleSolve[q : {__Integer?Positive} /; Total[q] == 10] :=
 Module[{n, qs, d, p, a, cl, vl, bm, sl},
  n = Length@q;
  qs = Sort[q];

  d[i_, j_] := Sum[k a[i, j, k], {k, 0, 9}];
  p[i_] := FromDigits@Reverse@Array[d[i, #] &, qs[[i]]];

  cl = {
     Table[Sum[a[i, j, k], {k, 0, 9}] == 1, {i, n}, {j, qs[[i]]}],
     Table[Sum[a[i, j, k], {i, n}, {j, qs[[i]]}] == 1, {k, 0, 9}],
     p[n] == Total[p /@ Range[n - 1]],
     Table[p[i] <= p[i + 1], {i, n - 1}] (* Not necessary, but improve performances  *)
     } // Flatten;
  vl = Cases[cl, _a, \[Infinity]] // Union;

  bm = CoefficientArrays[Equal @@@ cl, vl];
  sl = Quiet[LinearProgramming[
     -Last@CoefficientArrays[p[n], vl],
     bm[[2]],
     Transpose@{-bm[[1]], 
       cl[[All, 0]] /. {Equal -> 0, LessEqual -> -1, 
         GreaterEqual -> 1}},
     ConstantArray[{0, 1}, Length@vl],
     Integers
     ], {LinearProgramming::lpip, LinearProgramming::lpsnf}];

  If[Head[sl] === LinearProgramming,
   ConstantArray[Indeterminate, n],
   Array[p, n] /. Thread[vl -> sl]]
  ]

and then a function that try all integer partitions of $10$ into exactly $n$ integers

puzzleSolve[n_Integer /; n >= 2] :=
 Module[{res},
  res = Table[{p, puzzleSolve[p]}, {p, IntegerPartitions[10, {n}]}] //
       Timing // EchoFunction["Timing:", First] // Last;
  TakeLargestBy[res, Last@*Last, 1][[1, 2]]
  ]

First try with $n=3$:

puzzleSolve[3]

Timing: 2.14063

{48, 5973, 6021}

Also works for other $n$:

(t = Table[
    With[{sl = puzzleSolve[n]}, 
     Inactive[Plus] @@ Most@sl == Last@sl], {n, 3, 9}]) // Column
Activate[t]

{True, True, True, True, True, True, True}