2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this homework? If so, tag it as such. In any case, what have you tried? This is not the Mathematica mechanical turk site...it's for helping those having problems trying to implement things, not for doing the work for others. $\endgroup$ – ciao Sep 16 '15 at 23:40
  • $\begingroup$ This isn't my homework. I am just interested, how to compute such things. I could do it manually and this would take some time so I wonder how it could be calculated via some lines of code. So where is your problem? You don't have to answer the question if your answer doesn't play a part to solve my problem. $\endgroup$ – Masirius Sep 16 '15 at 23:58
  • 2
    $\begingroup$ Any registered member with more than 3000 reputation points can vote to close a question. I takes five such votes in total to effect the closing. $\endgroup$ – m_goldberg Sep 17 '15 at 0:58
  • 6
    $\begingroup$ @Masirius - please lower the temperature. You might find this useful: mathematica.stackexchange.com/help/closed-questions The fact is, experienced users are empowered to "close" questions if they do not feel the question is a good fit for the site. Please understand that people volunteer their time here to answer questions, and it is disrespectful of their time when other people post questions that show no effort of their own. I hope you have a good learning journey with Mathematica. $\endgroup$ – Verbeia Sep 17 '15 at 1:15
  • 1
    $\begingroup$ @m_goldberg. I +1'd your comment just for correct usage of the verb "effect". $\endgroup$ – march Sep 17 '15 at 1:19
11
$\begingroup$

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]
$\endgroup$
6
$\begingroup$

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

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]

Mathematica graphics

{True, True, True, True, True, True, True}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.