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!

About these ads

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

    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
    
  3. [...] The following is an interesting puzzle posted on the programming praxis website: Feynman’s Puzzle [...]

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: