Programming Praxis

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