October 23, 2009 9:00 AM
John McCarthy, who discovered Lisp, attributes this puzzle to Hans Freudenthal:
We pick two numbers a and b, so that 99 ≥ a ≥ b ≥ 2. We tell Mr. P. the product a × b and Mr. S. the sum a + b. Then Mr. S. and Mr. P. engage in the following dialog:
Mr. P.: I don’t know the numbers.
Mr. S.: I knew you didn’t know. I don’t know either.
Mr. P.: Now I know the numbers.
Mr. S.: Now I know them too.
Find the numbers a and b.
Your task is to find the two numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
This puzzle is quite intriguing. There’s a Japanese website where users can post programming puzzles and solutions, and a variation of this puzzle was posted some time ago. You can browse solutions in whole bunch of different languages:
http://ja.doukaku.org/34/nested/ (descriptions are in japanese, but code is universal).
I like the solution using Python’s list comprehension. Haskell ones are also concise.
(Note: some posted solutions contained bugs and later corrected by comments).
The original puzzle posted in the above url limited the number of the range between 1 <= a <= b <= 13. Then upper bound became a variable N. As N gets larger there can be more than one solutions, and an interesting question was posted that whether you could tell the relationship between N and the number of solutions. Some guys checked solutions with varying N up to 1000 to find out the relation but couldn't. Do you know any reference that analyzes the pattern of solutions of this puzzle with varying N?
By shiro on October 23, 2009 at 7:34 PM
@Shiro: thanks for the link! A lot of gems are hidden away behind language barriers…
For those who are interested, I translated Oleg’s code into Clojure. It’s Lispy, it runs on the JVM, and best of all, it has lazy sequences a la Haskell.
http://github.com/hircus/clj-puzzles/blob/master/Mr-S-P.clj
By Michel on October 24, 2009 at 10:18 AM
@shiro intriguing indeed! Thanks for sharing the Japanese site — all too often, gems on the Internet lie undiscovered because of language barriers (even though the code itself is universal).
For those interested in Lispy solutions, I’ve translated Oleg’s code from Haskell to Clojure. It’s Lisp, it’s on the JVM, and best of all, it has lazy sequences. The translation is almost 1-to-1.
http://github.com/hircus/clj-puzzles/blob/master/Mr-S-P.clj
Cheers!
By Michel on October 24, 2009 at 10:30 AM
@shiro interesting indeed, thanks for sharing! While code is universal, sometimes language barrier means these gems don’t get found…
For those interested, I’ve translated Oleg’s Haskell code to Clojure. It’s Lisp, it’s on the JVM, and it has lazy sequences — the translation is virtually 1-to-1, apart from syntactic differences.
http://github.com/hircus/clj-puzzles/blob/master/Mr-S-P.clj
By Michel S. on October 24, 2009 at 10:32 AM
My solution is programmed in Erlang and can be viewed at PasteBin
The source code contains extensive explanation in comments.
Running my solution yields:
io:format(“Solution: ~w~n”, [pssolver:solve(2,99)]).
Solution: [{13,4}]
So the sought number pair is 13 and 4.
It was quite a challenge!
By Rudi Angela on October 25, 2009 at 9:09 PM
fact2 is irrelevant. why?
regards,
_raf
By _raf on November 10, 2009 at 12:53 AM
Fact2?is used in the final calculation ofresult. The calculation fails withoutfact2?. What do you mean?By programmingpraxis on November 10, 2009 at 12:58 AM
fact2? is Mr S’s assertion that he doesn’t know: s=m+n is such that m and n can not be known (or, the list of good-summands for s has length > 1). The only “good-summand” in this sense is 4, but in that case both Mr P and Mr S know the numbers and we wouldn’t be having this pleasant conversation.
Here’s a slightly modified version of your program that produces ((13 4)) in plt-scheme-4.2.2: http://codepad.org/3BAukrSO
regards,
_raf
By _raf on November 10, 2009 at 12:58 PM
Correction: 4 *or 5* and “singleton? good-summands”…
By _raf on November 10, 2009 at 1:51 PM
Just ran my program a bit longer:
Once you increase N to around 850 you’ll have two solutions, not just 4 – 13.
The second solution is 4 – 61.
By Roy van Rijn on August 2, 2010 at 6:37 AM
@Roy van Rijn – you should not get more solutions if you increase the limit. I’m guessing your program uses primes in some way, which is incorrect – it’s about unique factorisation given the limits of numbers, so its possible to uniquely factorise numbers into non-primes
By James Tipper on June 29, 2013 at 11:08 AM