2010

Knuth先生のホームページに
Did you know that 2009 is (1/2+3)*(4+5*(6*7+8*9))?
と書いてある. (年があけてからはHappy 2010 (i.e., MMIX++) to all!になった.)

今年は2010年. 今度はどうなるかと思ってプログラムを書いた.
結論からいうと

(- (- (+ 1 2) (* (* (* (- (- 3 4) 5) 6) 7) 8)) 9)
(* (/ (* 1 2) 3) (- (* (* (* (+ 4 5) 6) 7) 8) 9))
(+ (- 1 (* (+ 2 (* (* (- (- 3 4) 5) 6) 7)) 8)) 9)
(* (- (- 1 2) 3) (- (/ (+ 4 5) 6) (* (* 7 8) 9)))
(* (* (/ (* 1 2) 3) (+ (- 4 5) (* (* 6 7) 8))) 9)
(* (+ (+ 1 2) (* 3 4)) (+ (- 5 6) (* (+ 7 8) 9)))
(* (+ 1 (* 2 (+ 3 4))) (+ (- 5 6) (* (+ 7 8) 9)))
(* (+ (* 1 2) (* (- 3 (* 4 (- (/ 5 6) 7))) 8)) 9)
(* (* 1 (+ 2 (* (- 3 (* 4 (- (/ 5 6) 7))) 8))) 9)
(+ (+ 1 2) (* (- (* (+ (* 3 (+ 4 5)) 6) 7) 8) 9))
(+ (+ 1 2) (* (+ 3 (* 4 (+ (+ 5 (* 6 7)) 8))) 9))
(+ (+ 1 (* (* 2 (- (* (* 3 4) (+ 5 6)) 7)) 8)) 9)
(* (+ (+ 1 2) 3) (- (* 4 (+ (* 5 6) (* 7 8))) 9))
(* (* (* 1 2) 3) (- (* 4 (+ (* 5 6) (* 7 8))) 9))
(+ (+ 1 2) (* (+ 3 (* 4 (+ (- 5 6) (* 7 8)))) 9))
(* (+ (- (- 1 2) 3) (* 4 (+ (/ 5 6) (* 7 8)))) 9)
(+ (+ 1 2) (* 3 (+ (* (* 4 (+ 5 6)) (+ 7 8)) 9)))

の17通りが2010になる. 11番目と最後の加算と乗算だけの式は美しい.
規則としては, 数字は1から9までこの順に使う. 演算子は+, -, *, /だけである.

実はTAOCPの第4巻, 分冊4の7.2.1.6小項の演習問題122は,

100=1+2*3+4*5-6+7+8*9=(1+2-3-4)*(5-6-7-8-9)
                     =((1/((2+3)/4-5+6))*7+8)*9

などの例の後で, このような100の作り方はどれだけあるかというのである. 候補の式の数は, 10646016あり, 100になるのは1640通りあるそうだ.

100の美しい式は 1+2+3+4+5+6+7+8*9 である.

このような式で表せない最小の正の整数は, 2284だそうだから, まだ当分楽しめる.

上の17通りの全解探索に要した計算時間は, MacBookAirで50分弱であった.
MIT Schemeを使ったが, 分数が使えるので, こういう計算には便利である.


後記
折角プログラムを書いたので, 100になる式をやってみた. ところが1640個ではなく1641個が得られた. Knuth先生にメイルしたところ, 珍しく早々にメイルで返事が来た. もちろん先生の秘書から来る.
それによると
2004年に書いたプログラムにはミスがあり, 1641が正しい.
先頭に単項の-をつけると2010になる式には他に26通りある.
ということだ.