「解けるかな？史上最難問10題」という記事を見かけました。「解けるはずないだろ～」と思って読んでいたのですが、8番目の「マーティン・ガードナーの最難問」は、頭脳では解けそうにないけれどもプログラミングで解けたりしないだろうか？と感じました。次のような問題です（少し原文を改変しています。原文を見られたい方はこちら）。
ある数の「粘度」を、すべての桁を掛けて出る答えが1桁になるまでに要するかけ算の回数で表すことにする。それぞれの桁の数を掛け算して出るのが2番目の数で、そのまた全桁の数を掛けて出るのが3番目の数…こうして1桁の数が出るまでやり、出るまでに行ったかけ算の回数を数える。
_
例: 77の粘度は4である。なぜなら、1桁の数になるまでに
77→49→36→18→8
のように4回かけ算をしなければならないから。
_
粘度1で一番小さい数=10
粘度2で一番小さい数=25
粘度3で一番小さい数=39
粘度4で一番小さい数=77
_
となっている。では粘度5で一番小さい数は何か？
10,25,39,77ときたら、次は？数百か数千あたりに答えがあるのでしょうか？しかし最難問というからには、ここで一気に大きな数にジャンプしてしまうのでは。などなど迷いましたが、まあ「案ずるより産むが易し」と言いますので、ちょっとしたプログラムを使って調べてみました。
調べ方
もう単純に、1から順に数を大きくしていきながら、その数の各桁の数を1桁になるまでかけ算し、かけ算の回数をカウントする・・・というプログラムを書きました。エクセル2010のVBAというものを用いています。以下に貼り付けていますので、チェックをしてみたい方（笑）などはご利用ください。
このプログラムのいいところを強いて挙げるとすれば、途中で中断できるということでしょうか。エクセルを他の用途に使いたいときにはこちらのプログラムを一時中断して、用事が済んだらまた再開・・・といったことができます。まあ大した長所ではありませんが。
Sub search_nendo()
_
____Application.ScreenUpdating = False
____‘スタートの数（中断したところ）を読込
____num_kaisi = Cells(1, 2).Value + 1
____num = num_kaisi
_
____Do
________‘各桁の数をかけていく
________num_mul = num
________nendo = 0
_
________Do
____________‘桁数の割り出し
____________keta = Application.WorksheetFunction.RoundDown(Log(num_mul) / Log(10), 0) + 1
____________num_mul_tmp = 1
_
____________For k = 1 To keta
____________num_k = Val(Mid(CStr(num_mul), k, 1))
____________num_mul_tmp = num_mul_tmp * num_k
____________Next k
____________num_mul = num_mul_tmp
_
____________nendo = nendo + 1
_
________Loop While num_mul >= 10
_
________‘0.001秒スリープを入れる
________Sleep 1
_
________‘集計結果を記入
________Cells(1, 2).Value = num
________Cells(nendo + 2, 2).Value = Cells(nendo + 2, 2).Value + 1
_
________‘粘度が5以上だったらその数も記録する
________If nendo >= 5 Then
____________Cells(nendo + 2, Cells(nendo + 2, 1).End(xlToRight).Column + 1).Value = num
________End If
_
________‘ある程度大きな数ごとに中断を選べる
________If num Mod 1000 = 0 Then
____________ThisWorkbook.Save ‘上書き保存しておく
____________Application.ScreenUpdating = True
____________Set WSH = CreateObject(“WScript.Shell”)
____________tmp = WSH.Popup(“中断しますか？「はい」で中断します。”, 1, “自動で続行します”, vbYesNo)
____________If tmp = vbYes Then Exit Sub
____________Set WSH = Nothing
____________Application.ScreenUpdating = False
________End If
_
____num = num + 1
____Loop
_
End Sub
調べてみると！
な、な、なんと！案外すぐ見つかりました！粘度5ばかりか、粘度6、粘度7もわりとすぐ見つかりました。
最小の粘度5の数=679（679→378→168→48→32→6）
最小の粘度6の数=6788（6788→2688→768→336→54→20→0）
最小の粘度7の数=68889（68889→27648→2688→768→336→54→20→0）
というわけで、難問の答えは「679」となりました。あっさりしてますね（汗）
模範的な解法は？？
「最難問」というからには、どう考えてもこのように「PCでチョチョイと調べてみましょう」という趣旨の問題のはずがないですよね。とはいうものの、「小さい数から総当たりする」という思想そのものは許されてもいいはず。と考えたとき、模範的な解法というのはあるのでしょうか・・・。誰か「模範的解法」で解けた方はぜひ教えてください。
ちょっと思うのは、【「粘度5の数の各桁の数をかけた数」は「粘度4の数」になっているはずだ】ということです。例えば679（粘度5）の各桁の数をかけた数378は、粘度4の数になっています（378→168→48→32→6）。このように考えると、最小の粘度5の数を探したい場合には次のようにすればよいのでは？と思いつきます。
★最小の粘度5の数の探し方はこうすればよい？★
粘度5の数の各桁の数をかけると粘度4の数になる
_ ↓ということは
粘度4の数を1つずつ見ながら、「かけ算したらその数になりそうな1桁の数のグループ」を探す
_ ↓そして
その「1桁の数のグループ」を並べ替えて、一番小さい数になったものが「最小の粘度5の数」となる
意味不明ですかね？少し易しくして「最小の粘度4の数を探したい」としましょうか。その場合、粘度3の数を1つずつ調べていくのです。粘度3の数は39,47,49,55…とたくさんありますが、
- 39=3×13
- 47=素数
- 49=7×7→77が粘度4の数
- 55=5×11
のようになっていて、意外と「1桁の数の積」で表せるものは多くないんですよ。49の次は75=3×5×5まで飛びます（355,535,553が粘度4の数となります）。このようにして調べていくと、粘度3の数から粘度4の数を生み出すことができます。全ての粘度3の数を調べれば、全ての粘度4の数が生み出せるはずです。
同じことをすれば、粘度4の数から粘度5の数が生み出せるわけですが・・・。ここで疑問なのは、「最小の粘度4の数から、最小の粘度5の数が生み出されるとは限らない」ということです。実はたまたま「378」という粘度4の数は、「1桁の数の積で表される最小の粘度4の数（378=2×3×3×3×7）」であり、しかも「最小の粘度5の数（679）を生み出す数」でもあったわけですが、必ずしもこのようにうまくいく保証はないのでは？
と思いつつ、もう少し調べてみると・・・
またまた不思議なことが・・・（ここまで読まれている方は希少だと思いますので、少し書き方を変えます）。先ほど気にしたことは
「1桁の数の積に分解できる最小の粘度nの数に対し、その1桁の数を適切に並べ替えると、最小の粘度n+1の数が得られる」とは限らない
ということでした。念のため、「1桁の数の積に分解できる最小の粘度nの数」は「最小の粘度nの数」ではないかもしれないので注意してくださいね（例えば、1桁の数の積に分解できる最小の粘度3の数は49ですが、最小の粘度3の数は39）。ところが・・・
◆1桁の数の積に分解できる最小の粘度3の数=49（=7×7）
→この1桁の数を並べると77（=最小の粘度4の数）
◆1桁の数の積に分解できる最小の粘度4の数=378（=2×3×3×3×7）
→この1桁の数を「適切に」並べ替えると679（=最小の粘度5の数）
◆1桁の数の積に分解できる最小の粘度5の数=2688（=2×2×2×2×2×2×2×3×7）
→この1桁の数を「適切に」並べ替えると6788（=最小の粘度6の数）
◆1桁の数の積に分解できる最小の粘度6の数=27648（=2×2×2×2×2×2×2×2×2×2×3×3×3）
→この1桁の数を「適切に」並べ替えると68889（=最小の粘度7の数）
このように、先ほど「とは限らない」と思ったことがことごとく成り立っています。ということは、最小の粘度8の数は、「1桁に分解できる最小の粘度7の数」から生み出されるのではないでしょうか？
実はこの原稿を書いているときは、まだプログラムは「46万」までしか調べていません。ここまでで見つかった粘度7の数は431個あります。その中で「1桁に分解できる最小の粘度7の数」はすでに見つかっています！
1桁に分解できる最小の粘度7の数 = 338688（=2×2×2×2×2×2×2×2×3×3×3×7×7）
です！これを「適切に」並べ替えると・・・いくらになるんでしょう。何となく「2677889」になるような気がします。これが最小の粘度8の数になるでしょうか？そのためにはしばらくPCを動かし続けねばなりませんが・・・。いずれ続報を書きますので、それまでお楽しみに！というよりも、ちゃんとした「模範的解答」で解けた方はぜひ教えてください！
予想: 最小の粘度8の数は「2677889」
もひとつ予想: 1桁の数の積に分解できる最小の粘度nの数に対し、その1桁の数を適切に並べ替えると、最小の粘度n+1の数が得られる。
「予想」と書きましたが、何となく当たり前のような気がしてきました・・・。いや、だいたい「当たり前」と思うときに限って穴があるので、また暇なときに考えてみます。（2013/8/15追記:これ、やっぱり間違ってますね。「1桁の数の積に分解できる最小の粘度2の数」は25ですが、そこから得られる粘度3の数は55であり、これは「最小の粘度3の数=39」とは違いますね・・・）
こちらの方も
実は私が「679」を探し当てたとき、すでにこちらの方が同じようなことをされていたんですね（笑）。しかも100万まで調べていて、もう結果まで出されている。いや～脱帽です。しかしこの方は100万でストップしているためか、粘度8までは見つかっていないようです。一緒に調べていただけないかしらん？
つづきます
次の記事に続きます。
ほかのブログへ
↑クリックするといろんな科学ブログを探せます。ついでに「カガクのじかん」のランキングも上昇します（ありがとうございます）。
