## 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

### 3 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

```digit :: Int -> Int -> Int
nth `digit` n = n `mod` 10 ^ nth `div` 10 ^ (nth - 1)

feinman :: [(Int, Int)]
feinman = [ (n1, n2)
| b <- [1..9], a <- [0..9], c <- [0..9],
d <- [1..9], e <- [0..9], f <- [0..9],
a /= b, a /= c, a /= d, a /= e, a /= f, e < d,
let n1 = 100 * b + 10 * a + c,
let n2 = 1000 * d + 100 * e + 10 * a + f,
n1 * n2 > 999999, n1 * n2 < 10000000,
digit 3 (n1 * n2) == a,
digit 1 (d * n1) == a, digit 2 (d * n1) == a,
digit 1 (e * n1) == a, digit 3 (a * n1) == a]

main :: IO ()
main = print feinman
```
3. [...] The following is an interesting puzzle posted on the programming praxis website: Feynman’s Puzzle [...]