Mr. S. and Mr. P.
October 23, 2009
We will follow Oleg Kiselyov’s solution. First, we define the list of good numbers that can participate in the solution:
(define good-nums (range 2 100))
Given a number p, we want to find all its good factors a and b, with a ≥ b, and return them (the pairs of factors) in a list. We use the obvious and straight forward memoization, pre-computing the factors in a list:
(define good-factors-table
(let ((gf (lambda (p)
(list-of (list a b)
(a in good-nums)
(b in good-nums)
(>= a b)
(= p (* a b))))))
(map gf (range 0 10000))))
(define (good-factors p)
(list-ref good-factors-table p))
The upper limit of 99 × 99 ≈ 10000 must be specified because Scheme’s eager lists are finite; Oleg didn’t have to specify the upper limit because Haskell’s lazy lists are infinite. We apply the same memoization to find all the good summands a and b, with a ≥ b, and return the pairs of summands in a list:
(define good-summands-table
(let ((gs (lambda (s)
(list-of (list a b)
(a in good-nums)
(b in good-nums)
(>= a b)
(= s (+ a b))))))
(map gs (range 0 10000))))
(define (good-summands s)
(list-ref good-summands-table s))
We need to test if a list has only one item:
(define (singleton? xs)
(and (pair? xs) (null? (cdr xs))))
We can now encode the dialog between Mr. P. and Mr. S., which provides five facts. The first fact is that Mr. P. doesn’t know the numbers. But Mr. P. would have know the numbers if the product had had a unique good factorization, so we say:
(define (fact1? ab)
(not (singleton? (good-factors (apply * ab)))))
The second fact is similar; Mr. S. doesn’t know the numbers either:
(define (fact2? ab)
(not (singleton? (good-summands (apply + ab)))))
The third fact is that Mr. S. knows that Mr. P. doesn’t know the numbers. In other words, for all possible summands that make a+b, Mr. P. cannot be certain of the numbers:
(define (fact3? ab)
(all? fact1? (good-summands (apply + ab))))
Mr. S. now knows that Mr. P. doesn’t know the numbers. Thus, the fourth fact is that of all factorizations of a×b there exists only one that makes the third fact true:
(define (fact4? ab)
(singleton? (filter fact3? (good-factors (apply * ab)))))
The fifth fact is that Mr. S. knows that Mr. P. found the numbers. Thus, only one decomposition of a+b makes the fourth fact true:
(define (fact5? ab)
(singleton? (filter fact4? (good-summands (apply + ab)))))
Finally, we define the list of all pairs of numbers that satisfy all five facts:
(define result
(list-of (list a b)
(a in good-nums)
(b in good-nums)
(>= a b)
(all? (lambda (pred?) (pred? (list a b)))
(list fact1? fact2? fact3? fact4? fact5?))))
And the answer is:
> result
((13 4))
For product 52 and sum 17, fact1? and fact2? are obviously true. The good summands of 17 produce 30, 42, 52, 60, 66, 70 and 72 when multiplied, all of which have multiple factor-pairs, so fact3? is true. The good factors of 52 produce 17 and 28 when summed, which both have multiple summanand-pairs, so fact4? is true. And fact5? is true, since the good-summands list of 17 and the good-factors list of 52 have only the pair 13 and 4 in common. The calculation of result performs brute-force search through all pairings of a and b, performing an analysis similar to the one given above; it finds only one pairing that makes all five facts true, which is the unique solution.
Our solution uses list-of, filter, all? and range from the Standard Prelude. The code is collected at http://programmingpraxis.codepad.org/cFiBzALC, but running it results in a timeout error.
Programming Praxis 
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?
@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
@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!
@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
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!
fact2 is irrelevant. why?
regards,
_raf
Fact2?is used in the final calculation ofresult. The calculation fails withoutfact2?. What do you mean?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
Correction: 4 *or 5* and “singleton? good-summands”…
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.
@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