## Feynman’s Puzzle

### June 12, 2009

Since there is no remainder, and it’s easier to work with multiplication than division, we restate the problem: determine bAc × deAf subject to various constraints.

We begin by establishing variables for A, b, c, d, e and f, ensuring that A is different from the others, and calculating bAc × deAf. The product must be a seven-digit number, and the fifth digit (fourth counting from zero) must be A. The first line of the division shows that d × bAc must be AA modulo 100, and the second line of the division shows that e × bAc must be A modulo 10. Finally, from the third line of the division we know that A × bAc is a four-digit number, and its second digit is A. Here is the first attempt at a solution:

```> (list-of (list (list b a c) (list d e a f))   ; initialize digits     (a range 10) (b range 1 10) (c range 10)     (d range 1 10) (e range 10) (f range 10)   ; A differs from the other digits     (not (= a b)) (not (= a c)) (not (= a d))     (not (= a e)) (not (= a f))   ; calculate the two numbers     (n1 is (+ (* b 100) (* a 10) c))     (n2 is (+ (* d 1000) (* e 100) (* a 10) f))   ; answer must be seven digits     (< 999999 (* n1 n2) 10000000)   ; fifth digit of answer must be A     (= (list-ref (digits (* n1 n2)) 4) a)   ; d * bAc must be AA modulo 100     (= (modulo (* d n1) 100) (+ (* a 10) a))   ; e * bAc must be A modulo 10     (= (modulo (* e n1) 10) a)   ; A * bAc must be four digits     (< 999 (* a n1))   ; second digit of A * bAc must be A     (= (list-ref (digits (* a n1)) 1) a)) (((4 3 7) (9 9 3 9)) ((4 8 4) (7 2 8 9)) ((4 8 4) (7 7 8 9)))```

So there are three possibilities, and we have to do some more work. We know that e must be less than d, since e × bAc is a three-digit number but d × bAc is a four-digit number:

```> (list-of (list (list b a c) (list d e a f))   ; initialize digits     (a range 10) (b range 1 10) (c range 10)     (d range 1 10) (e range 10) (f range 10)   ; A differs from the other digits     (not (= a b)) (not (= a c)) (not (= a d))     (not (= a e)) (not (= a f))   ; calculate the two numbers     (n1 is (+ (* b 100) (* a 10) c))     (n2 is (+ (* d 1000) (* e 100) (* a 10) f))   ; answer must be seven digits     (< 999999 (* n1 n2) 10000000)   ; fifth digit of answer must be A     (= (list-ref (digits (* n1 n2)) 4) a)   ; d * bAc must be AA modulo 100     (= (modulo (* d n1) 100) (+ (* a 10) a))   ; e * bAc must be A modulo 10     (= (modulo (* e n1) 10) a)   ; A * bAc must be four digits     (< 999 (* a n1))   ; second digit of A * bAc must be A     (= (list-ref (digits (* a n1)) 1) a)   ; e must be less than d     (< e d)) (((4 8 4) (7 2 8 9)))```

This solution uses list comprehensions and the `digits` function from the Standard Prelude. The completed long division looks like this:

```              7 2 8 9       - - - - - - - - 4 8 4 ) 3 5 2 7 8 7 6         3 3 8 8         - - - -           1 3 9 8             9 6 8           - - - -             4 3 0 7             3 8 7 2             - - - -               4 3 5 6               4 3 5 6               - - - -                     0```

This puzzle appeared on Reddit a few weeks ago. Keith Lofstrom tells the story of this puzzle and gives a manual solution at http://wiki.keithl.com/index.cgi?FeynmanPuzzle. You can run the solution given above at http://programmingpraxis.codepad.org/50ygwf6g.

What a fun puzzle!

Pages: 1 2

### 4 Responses to “Feynman’s Puzzle”

1. […] Praxis – Feynman’s Puzzle By Remco Niemeijer Today’s Programming Praxis problem is about a long division puzzle by Richard Feynman. The provided […]

2. Remco Niemeijer said