二桁の数の秘密

残念なできごと

　つい先日、何かの調べ物をしていて、なかなか面白いサイトを見つけました。しばし仕事も忘れて読みふけっていたのですが、その中にとても興味深いネタがあったので、つい検証プログラムを書いてしまいました。

　で、３月に入ってまた見てみると、驚いたことにそのサイトのサービス自体が2012年2月末で停止していました。僕は停止寸前のサイトをたまたま見ていたのです。
　http://page.cafe.ocn.ne.jp/profile/suugakupazuru/diary/d2337

　このサイト、とても面白いので、どこかでまた復活してもらえるとうれしいのですが・・・その想いもこめて、先日書いた検証プログラムをここに載せてみたいと思います。

お題

　Googleのキャッシュはいつ消えてしまうかわからないので、失礼とは思いますが全文を引用させていただきます。

２桁の自分の好きな数を書いてください。その数字を逆の順序に並べた数を作り、元の数に足します。

求めた和に、又、同じ手続きを繰り返します。
実験してみればわかるように、この手続きを何回か繰り返すと、必ず、左から読んでも、右から読んでも、
同じ、左右対称の数に行き着くのです。
３８　　　　　　　　　　５９　　　　　　　　　　６７　
８３　　　　　　　　　　９５　　　　　　　　　　７６
１２１　　　　　　　　１５４　　　　　　　　　１４３
　　　　　　　　　　　　４５１　　　　　　　　　３４１　
　　　　　　　　　　　６０５　　　　　　　　　４８４　
５０６　
１１１１
　　  　　　　　
すぐに左右対称になった人は、運が良いのかもしれません。
しかし、運悪く８９を選んだとしたら？
何と、２４段目にして、８８１３２０００２３１８８にたどり着きます。

さあ、試してみましょう！

これには、私の忘れもしない苦い思い出があります。
私が買った本には、２桁の数に限らず、全ての勝手な数で、この結果が導き出されるとありました。

鵜呑みに出来なかった私は、３桁の数全てで試してみたのです。
狐に憑かれたような日々でした。

そして私は、ある「発見」をしたのです。
（１９６、２９５、３９４、４９３、５９２、６９１）の組から始めると、いつまで行っても、
左右対称にならない！
ここで、組と書いたのは、この６個の数は、次の足し算の段階で、全て８８７になるからです。

地元の新聞にも取り上げてもらい、その結果、コンピューターのできる高校生が、５万回繰り返しても
左右対称にならない事を、新聞社に投稿してくれました。

しかし、これでも数学的には証明されたことにならないのです。

運悪く、５０，００１回目以降に左右対称になるかもしれないから。

なんとも凄い少年ですね！！

巨大数の計算

　このお題ポイントは巨大な数を扱うところです。100回の計算を繰り返すとざっと2回に1回桁が増えると考えても50桁の数になります。これはInt32どころかInt64でも全く歯が立たない数です。
　こういう巨大数のために、.NetフレームワークにはBigIntegerという型が用意されています。が、今回は数値をリバースする必要もあるので、一桁の数のリストで巨大数を表現することにして、その計算を定義していくことにします。当時の高校生もきっとそうしたはずです。

let adder n m carry =
  let x = n + m + carry
  x / 10, x % 10

let listAdder l1 l2 =
  let rec listAdder' yo l1 l2 a =
    match l1, l2 with
    | [], [] -> if yo = 0 then a else yo :: a
    | [], _  -> failwith "BadParam."
    | _, []  -> failwith "BadParam."
    | x :: xs, y :: ys ->
      let carry, d = adder x y yo
      listAdder' carry xs ys (d :: a)
  listAdder' 0 l1 l2 []

let revAdd l =
  List.rev l |>
  listAdder l

let int2List n =
  let rec int2List' n a =
    if n / 10 = 0 then n :: a
                  else int2List' (n / 10) ((n % 10) :: a)
  int2List' n []

let List2Str (l : int list) =
  List.fold (fun s v -> s + (string v)) "" l

　最初のadder関数は、1桁の数同士と下の桁からの繰り上がりを足して1、新たな一桁と繰り上がりを返します。
　次のlistAdderは、二つのリストを数値に見立てて加算する関数です。
　revAddは、数値を表したリストを反転したものと加算します。ここがメインと言ってもいいでしょう。
　int2Listは、数値をリストに変換する関数です。スタート地点はそれほど大きい数ではないので、これで起点を指定します。
　最後のlist2Strは、計算結果を表示するために文字列に変換します。

結果のチェック

　巨大数の計算ができるようになったら、それが対称などの条件を満たすか確認します。

let checkRev l =
  (List.rev l) = l

let rec check n times =
  if times = 0 
    then times, n
    else
      let next = revAdd n
      if checkRev next
        then (times - 1), next
        else check next (times - 1)

let doCheck n times =
  let cnt, res = check (int2List n) times
  let s = List2Str res
  printfn "%d   : %d回 : %d桁 : %s" n (times - cnt) (s.Length) s

　一つ目のcheckRevは、あるリストはが左右対称かを返します。本当いうと半分まで調べればいいのですが手抜きしてます。
　二つ目のcheckは、ある数nを反転し、元の数を足したものが対象になるかどうかを指定回数まで繰り返す関数です。結果、対象になった（もしくはならなかった）数と、カウントダウンするカウンターの値を返します。
　最後のdoCheckは、checkを呼び出して結果をprintするだけの関数です。
　それでは実行してみましょう。

実行結果

> doCheck 125 500;;
125   : 1回 : 3桁 : 646
> doCheck 89 500;;
89   : 24回 : 13桁 : 8813200023188
> for i = 1 to 100 do doCheck i 100;;
1   : 1回 : 1桁 : 2
2   : 1回 : 1桁 : 4
3   : 1回 : 1桁 : 6
4   : 1回 : 1桁 : 8
5   : 2回 : 2桁 : 11
～　中略　～
67   : 2回 : 3桁 : 484
68   : 3回 : 4桁 : 1111
69   : 4回 : 4桁 : 4884
70   : 1回 : 2桁 : 77
71   : 1回 : 2桁 : 88
72   : 1回 : 2桁 : 99
73   : 2回 : 3桁 : 121
74   : 1回 : 3桁 : 121
75   : 2回 : 3桁 : 363
76   : 2回 : 3桁 : 484
77   : 3回 : 4桁 : 1111
78   : 4回 : 4桁 : 4884
79   : 6回 : 5桁 : 44044
80   : 1回 : 2桁 : 88
81   : 1回 : 2桁 : 99
82   : 2回 : 3桁 : 121
83   : 1回 : 3桁 : 121
84   : 2回 : 3桁 : 363
85   : 2回 : 3桁 : 484
86   : 3回 : 4桁 : 1111
87   : 4回 : 4桁 : 4884
88   : 6回 : 5桁 : 44044
89   : 24回 : 13桁 : 8813200023188
90   : 1回 : 2桁 : 99
91   : 2回 : 3桁 : 121
92   : 1回 : 3桁 : 121
93   : 2回 : 3桁 : 363
94   : 2回 : 3桁 : 484
95   : 3回 : 4桁 : 1111
96   : 4回 : 4桁 : 4884
97   : 6回 : 5桁 : 44044
98   : 24回 : 13桁 : 8813200023188
99   : 6回 : 5桁 : 79497
100   : 1回 : 3桁 : 101

こんな感じになりました。

ちなみに、196から5万回を試してみると、

> doCheck 196 50000;;
196   : 50000回 : 20779桁 : 9315172055507185830661130891050700195895328458484974932650 ～ 略 ～
リアル: 00:04:29.731、CPU: 00:04:27.822、GC gen0: 9074, gen1: 2957, gen2: 3

　4分半で帰ってきました。僕のマシンはいわゆるネットブック相当のCPUなので決して早くはないですが、それでも当時の高校生が使っていたパソコンより何桁も速いはずです。彼も同じように、おそらく配列上に数を並べて10進演算の仕組みを自分で書き、何日もコンピュータを回して5万回にたどり着いたのだと思います。ちょっと胸熱ですね。
　ちなみに、僕が大学生の頃、某教官から借りたFM-11BSでマンデルブロート集合を描画するプログラムを書き、正月に回したまま帰省したのですが、休み明け東京に戻ってもまだ半分も終わってませんでした。

フラクタルっぽい？

　上のように、1から順に試していき、その結果をビットマップに描画（何回で抜けたかで色を変える）していくと、何やらフラクタルっぽい図形になります。やっていることがマンデルブロート集合の計算にちょっと似ているところもあるうえ、0～4までの数が多い場合と5～9が多い場合で明らかに抜け出す回数の分布が変わってくるので、フラクタルな周期性を帯びるのは当然とも考えられますが、いろいろ試してみるといいかもしれません。

それにしても・・・

　この計算を手でやった少年には脱帽するしかありません。これに今現在の時点でなんらかの証明があるのかどうかはわかりませんが、整数論のあたりにはまだまだ、やろうと思えば小学生でもたどり着ける謎が沢山転がっているように思えます。プログラムを書いて追試をした高校生もあっぱれと言いたいです。きっと今は著名なエンジニアや研究者になっているのではないでしょうか。
　ところで本に書いた人は、証明が手元にあって「全ての勝手な数で、この結果が導き出される」と書いたんでしょうかね・・・

（文責：片山功士　　2012/03/06）

今日： - 人
昨日： - 人
トータル： - 人

「二桁の数の秘密」をウィキ内検索

最終更新：2013年09月20日 15:10