The Sum and Product Puzzle

I talked about an interesting math problem in Sun Bin PK Pang Juan. I had onsite-inteviews from Wolfram in April 2013, and I decided to talk how to solve the problem using Mathematica. I did some research and realized that the problem is a well-known one which is called the Sum and Product Puzzle (aka the Impossible Puzzle). The Sum and Product Puzzle has several different versions. I reframe the one mentioned in my previous post as follows.

Two numbers (not necessarily unique) between 2 and 99 are chosen. The sum of them is told to Sam and the product of them is told to Peter .

Sam: “Now I don’t know what the 2 numbers are, but I’m sure you don’t know either.”

Peter: “I have to thank you for the information, because I did have no idea of what the 2 numbers are, but now I already know.”

Sam: “Now the same here.”

Question: what are the two numbers?

Notations¶

R: range of the 2 numbers, which is {2,3,. . . ,99} in this case

x0 , y0: a (the) solution to the Puzzle

Mathematical Information Hidden in Words¶

“Now I don’t know what the 2 numbers are, but I’m pretty sure you don’t know either.”

$\exists$ multiple pairs of $x, y\in R$ such that $x+y=x_0+y_0$
For each pair of $x,y\in R$ such that $x+y=x_0+y_0$ , $\exists$ multiple pairs of $x',y'\in R$ such that $x'\times y'=x \times y$

Let’s called the above conditions set I.

“I have to thank you for the information, because I did have no idea of what the 2 numbers are, but now I already know.”

$\exists$ multiple pairs of $x, y\in R$ such that $x\times y=x_0\times y_0$ (already in conditions set I).
Among all pairs $x,y\in R$ such that $x\times y=x_0\times y_0$ , $\exists$ an unique pair satisfying conditions set I.

Let’s called the above conditions set II.

“Now the same here”

$\exists$ multiple pairs of $x, y\in R$ such that $x+y=x_0+y_0$ (already in conditions set I).
Among all pairs $x,y\in R$ such that $x+y=x_0+y_0$ , $\exists$ an unique pair satisfying conditions set II.

Let’s called the above conditions set III.

Algorithm to Solve the Sum and Product Puzzle¶

A/The solution (pair of $x_0$ and $y_0$ ) must satisfies conditions set I, II and III at the same time.

Construct all possible combinations of $x,y\in R$ .
Select pairs (among all possible pairs) that satisfy conditions set I, II and III at the same time.

Mathematica Code for the Sum and Product Puzzle¶

TwoAddends[s_Integer, range_List] := Module[{lower, upper},
   lower = range[[1]];
   upper = range[[2]];
   Table[{i, s - i}, {i, Max[lower, s - upper], Min[upper, s - lower, s/2]}]
];

TwoFactors[p_Integer, range_List] := Module[{lower, upper, div, n},
   lower = range[[1]];
   upper = range[[2]];
   div = Select[Divisors[p], # >= Max[lower, p/upper] && # <= Min[upper, p/lower, Sqrt[p]] &];
   Map[{#, p/#} &, div]
];

S1[pair_List, range_List] := Module[{s, candidates},
   s = Total[pair];
   candidates = TwoAddends[s, range];
   Length[candidates] > 1 && Apply[And, Length[TwoFactors[Times @@ #, range]] > 1 & /@ candidates]
];

P1[pair_List, range_List] := Module[{p, candidates},
   p = Times @@ pair;
   candidates = TwoFactors[p, range];
   Length[candidates] > 1 && Total[Boole[S1[#, range] & /@ candidates]] == 1
];

S2[pair_List, range_List] := Module[{s, candidates},
   s = Total[pair];
   candidates = TwoAddends[s, range];
   Length[candidates] > 1 && Total[Boole[P1[#, range] & /@ candidates]] == 1
];

SumProductPuzzle[range_List] := Module[{lower, upper, candidates},
   lower = range[[1]];
   upper = range[[2]];
   candidates = Flatten[Table[{i, j}, {i, lower, upper}, {j, i, upper}], 1];
   Select[candidates, S1[#, range] && P1[#, range] && S2[#, range] &]
]

All code and results for this project are hosted on GitHub at sum_prod. As I will continue to study this problem, it is the best place to find the most updated code and results for this problem.

Result¶

Run the function SumProductPuzzle to find a/the solution to the puzzle.

SumProductPuzzle[{2, 99}]
{{4, 13}}

Some Discussions about the Sum and Product Puzzle¶

It is of great interest to find all ranges of the form $[2, U]$ such that there is an unique solution to the puzzle in these ranges.

Use the following code to do computation in parallel

DistributeDefinitions[TwoAddends, TwoFactors, S1, P1, S2, SumProductPuzzle]
rr = Table[ParallelSubmit[{i}, SumProductPuzzle[{2, i}]], {i, 61, 600}]
WaitAll[rr]

The solution depends on the range (can have no, unique or multiple answers).
There is no solution in [2, U] for $2 \le U \le 61$ .
I have verified that an unique solution exists in [2, U] for $62 \le U \le 610$ .
As the Mathematica code I wrote is more for illustrating my ideas and runs slowly. I will reimplement the algorithm with previous calculated results cached in Java to further study this problem.