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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2009/06/12/programming-praxis-feynman%E2%80%99s-puzzle/ for a version with comments):

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 [/sourcecode]

[…] The following is an interesting puzzle posted on the programming praxis website: Feynman’s Puzzle […]

[…] (Credits: I learnt of this problem from Thaddeus Abiy on brilliant.org. Image of Feynman’s notebook is from this site.) […]