hibitの技術系メモ

数学とか3Dとか翻訳とか

数学が先かプログラムが先か、あるいはよりよい回文数式の可能性

 今日も元気にtwitterをしていたら、以下のようなツイートが目に入ってきました。

 これを見た時に

  • 他にもこの形で成り立つ回文数式はないか
  • なぜ1〜9を1つずつ使っていないのか、もしかして使えないのか

 と感じるのは、健康的な成人男子なら当然の衝動*1かと思われます。検証していきましょう。

他にもこの形で成り立つ回文数式はないか

 もし私に無限の時間と体力があるなら、紙とペンを持ち出して一つずつ数を書き出して検証していくでしょうが、それを行おうとすると9^{9}=387,420,489回の試行が必要になります。1試行10秒で終わるとしても約1,076,168時間もかかっています。プログラムにやってもらった方が良さそうです。

 私はこういう、数を並べる系のプログラムはVBAでささっと書いてしまいます。何も考えずに実装したら以下のようになるでしょうか。

Sub zatsu()

col = 1

For a = 1 To 9
For b = 1 To 9
For c = 1 To 9
For d = 1 To 9
For e = 1 To 9
For f = 1 To 9
For g = 1 To 9
For h = 1 To 9
For i = 1 To 9

    If (100 * a + 10 * b + c) + (100 * d + 10 * e + f) * (100 * g + 10 * h + i) = (100 * i + 10 * h + g) * (100 * f + 10 * e + d) + (100 * c + 10 * b + a) Then
        col = col + 1
        Cells(col, 1) = a
        Cells(col, 2) = b
        Cells(col, 3) = c
        Cells(col, 4) = d
        Cells(col, 5) = e
        Cells(col, 6) = f
        Cells(col, 7) = g
        Cells(col, 8) = h
        Cells(col, 9) = i
        Cells(col, 10) = (100 * a + 10 * b + c) + (100 * d + 10 * e + f) * (100 * g + 10 * h + i)
        Cells(col, 11) = (100 * i + 10 * h + g) * (100 * f + 10 * e + d) + (100 * c + 10 * b + a)
    End If

Next i
Next h
Next g
Next f
Next e
Next d
Next c
Next b
Next a

End Sub

 ……ネスト深すぎるわ!

 パソコンは人間に比べたら作業が早く忍耐強いですが、それでもこれをマトモに計算させたら(私のPCでは)5分ぐらい固まります。このような単純労働を強いるのは基本的PC権の侵害であると言えるでしょうし、何より桁数が増えた時に計算量が爆発してしまいます*2

 雑にプログラムを組むよりも、人間側が工夫して無駄な計算をさせないようにした方がよさそうです。この段階になって初めて人間が紙とペンで数学する必要が出てきます。

 さて、件の回文をabc+def \times ghi = ihg \times fed+cbaという形で変数を当てはめると、以下のように整理できます。

f:id:hibit_at:20190708220734j:plain

 これがa〜iが満たすべき条件です。各項の成分が独立であればすべての係数が0がその条件になりますが、今回はそうではないので各項同士が相殺するという状態も考えなければいけません。(後日追記)ここら辺、大きな勘違いがあり、以下の場合は限られた一部ということがわかりました。訂正いたします。

 つまり、以下のようになります。

f:id:hibit_at:20190708220746j:plain

 これをプログラムにも反映させていきましょう。それぞれの条件でプロシージャを分けて、条件を満たさなければ途中で計算を打ち切るようにするだけでもだいぶ計算量を省くことができます。

Sub step1()

col = 1

For d = 1 To 9
For g = 1 To 9
For f = 1 To 9
For i = 1 To 9
    If Abs(d * g - f * i) = 1 Then
       step2
    End If
Next i
Next f
Next g
Next d

End Sub
Sub step2()

For e = 1 To 9
For h = 1 To 9
    If e * (g - i) + h * (d - f) + 10 * (d * g - f * i) = 0 Then
        step3
    End If
Next h
Next e

End Sub
Sub step3()

For a = 1 To 9
For c = 1 To 9
    If d * g - f * i + a - c = 0 Then
        step4
    End If
Next c
Next a

End Sub
Sub step4()

For b = 1 To 9
    col = col + 1
    Cells(col, 1) = a
    Cells(col, 2) = b
    Cells(col, 3) = c
    Cells(col, 4) = d
    Cells(col, 5) = e
    Cells(col, 6) = f
    Cells(col, 7) = g
    Cells(col, 8) = h
    Cells(col, 9) = i
    
    Cells(col, 10) = (100 * a + 10 * b + c) + (100 * d + 10 * e + f) * (100 * g + 10 * h + i)
    Cells(col, 11) = (100 * i + 10 * h + g) * (100 * f + 10 * e + d) + (100 * c + 10 * b + a)
Next b

End Sub

 実際に回した結果がこちら。10秒ぐらいで計算できるようになりました。

f:id:hibit_at:20190708213138p:plain

 あまりにも多すぎて載せきれませんが、なんと11,520617,598通りもあります。まあ、以下のような4つの組み合わせは、文の形は違えど実質的には同じものと言えるかもしれませんが。

f:id:hibit_at:20190708215142p:plain

 それでも2,880154,400以上の*3通りあるので、この形の回文数式にあまりありがたみはなさそうです。

f:id:hibit_at:20190708213001p:plain

 冒頭のツイートにあるやつも出てきました。

なぜ1〜9を1つずつ使っていないのか

 計算の過程で、1〜9を使っている数式も普通に出てきました。例えば以下のようなやつ。

152+483 \times 769 = 967 \times 384 + 251

※両辺はともに371,579

 なお、このようなタイプ(1〜9を満遍なく使っているタイプ)は全部で4452通りあるようです。上で述べた補正をしても1113通りなので、わりとありますね。回文数式の例としてはこういったものの方がベターではないでしょうか?

あとがきポエム

 個人的には、ある計算を行いたい場合、数学(紙とペン的な意味で)とプログラムのどちらを使うかという問いかけにあまり意味はないと思います。手計算で大変そうだったらプログラムを組む、プログラムの最適化が必要そうだったら人間が考える、という形で相補的に働くものだと思っています。今回のような例はごくごく簡単な例ですが、いつかはもっと難しい問題で圧倒的効率化をした上で圧倒的計算ができればよいなと思いました(小学生か)。

 皆さんもよき数学orプログラミングライフを。

*1:つい筆が滑りましたが、もちろん成人女子いや老若男女においても当然の衝動かと思われます

*2:O(9^{n})で合ってるんでしょうか(自信がない)

*3:例えばa~iがすべてが1であるような場合、バリエーションはないので見かけが4倍、ということにはなりません