Number puzzle

[jemidiah]

I found this number puzzle elsewhere online, and since my solution was very computational I figured someone here might enjoy it. I've actually modified it a bit. I would link to the original except it contains my answer.


Person A picks two whole numbers between 1 and 100, excluding both 1 and 100. The numbers are not necessarily distinct. Person A tells Person S the sum of the numbers and Person P their product. S and P have the following conversation, where everything they say is true:

P: "I know only the product and not the sum."
S: "I know that you know only the product and not the sum."
P: "Now I know the numbers."

Easier version: if P's product was 182, what were the numbers?
Harder version: After S and P's conversation ends, A remarks, "Amazing! If you repeated this exact conversation with any other pair of numbers, the sum would be different!" What were the numbers?

[Logophobic]

Very computational? Hmm... I've seen this puzzle before, but had not previously solved it. I figured out how to solve it, and that was enough for me.

1) There are a finite number of possible products, many of which are eliminated by the first statement.
2) There are a finite number of sums for which the second statement can be true.
3) There are a finite number of products for which the third statement can be true.
4) There is only one sum from (2) that allows for only one of the products from (3)

1) 2843 possible products.
2) 10 candidate sums.
3) 86 candidate products.
4) The sum is ##, the product is ##, and the numbers are # and ##.

I hope I haven't revealed too much...

[Logophobic]

I am curious as to what you consider 'very computational'. The problem can be solved manually with less than 200 calculations. I'll concede that it is easier to solve it programatically with a few thousand, though I would not consider this very computational.

[jemidiah]

Hmm, now I have to remember my solution.... Ah, I remember most of it. Solving the problem given a specific product does only take a few ~dozen steps [figure out which numbers could have generated that product via factoring it; for each sum of those numbers figure out each possible secondary product; for each secondary product figure out if it can only be generated by a single sum]. When I coded it, though, I used a wildly inefficient (but easy to code) method that bore little resemblance to the way a human would solve it. The method didn't matter much, since it still only took a second or two to run, but it did millions of calculations. I forget precisely what I did, though hopefully this account is enough to answer the question of what I consider "very computational". This solution was for the "hard" version, by the way.

I would probably call a program solving the easy version in the manner of a human as I described above simply "computational". Solving the hard version in that same manner by using the same method for each easy version would probably again be "very computational", though if memoization were used it would probably be back down to "computational".

[Logophobic]

Solving the 'hard' version, manually:
1) The product is not semiprime, does not have a prime factor greater than 50, and is not twice the square of a prime greater than 10.
2) The sum is an odd number less than 54, is not p+2 for any prime p, and is not 3*p for any prime p > 10.
3) The 10 possible sums provide for 169 number pairs, 86 of which have a unique product. Calculation of these products is the bulk of the work.
4) Cross reference the sums with the unique products. One sum is linked to only one product, and this pair provides the solution.

Solving the 'hard' version, programatically:
1) Calculate all possible products.
2) Eliminate all sums associated with any product that occurs only once.
3) Calculate all products associated with any of the remaining sums.
4) Count the number of unique products associated with each sum.
5) The sum associated with only one unique product, along with that product, provides the solution.