掛け算九九での積和試行の最大値

はじめに

掛け算九九において、7x7=49は特殊な数である。
1から9の数のうち、2つの数（重複を許す）を掛けて十の位と一の位の数を足すという操作を繰り返すことを考える。この操作を0になるまで繰り返したときの試行回数が最大となるのは、7x7のときである。今回はそれをpythonを用いて証明する。

問題設定

例えば以下のような感じである。
7x7=49
4x9=36
3x6=18
1x8=08
0x8=00
となるような操作を0まで行う。
この場合、0になるまでに行った試行回数は5回であるが、この場合の時、試行回数が最大になることをプログラムを用いて示す。

プログラム

以下のようなプログラムを書いた。

kuku.py

import numpy as np

def cal_99(a,b):

  m=a*b
  n=0
  while m > 0:
    m= a*b
    p=m%10
    q=(m-p)/10

    a=q
    b=p

    n=n+1
  return n

n=9

X=np.zeros((n,n))
#print(X)

for i in range(n):
  for k in range(n):
    X[i][k]=cal_99(i+1,k+1)

#print(np.argmax(X))
r= np.argmax(X)+1
print(r)

r1=r%9
r2=(r-r1)/9+1

print('9x9の中で、積→和の操作回数が最大となるものは、 %sx %s の時である' % (r1, int(r2)))

これにより、7x7=49のとき、試行回数が最大になることが分かった。

解空間のグラフ化

掛け算九九の解空間をグラフ化するために、以下のようなプログラムを作成した。

python kuku_con.py

import numpy as np
import matplotlib.pyplot as plt

def cal_99(a,b):

  m=a*b
  n=0
  while m > 0:
    m= a*b
    p=m%10
    q=(m-p)/10

    a=q
    b=p

    n=n+1
  return n

n=9

X=np.zeros((n,n))

X1=np.zeros((n,n))
X2=np.zeros((n,n))
#print(X)

for i in range(n):
  for k in range(n):
    X1[i][k]= i+1
    X2[i][k]=k+1
    X[i][k]=cal_99(i+1,k+1)


plt.contourf(X1,X2,X)
plt.colorbar()
plt.savefig("九九試行回数の分布.png")
plt.show()

これによって、生成したグラフを以下に示す。

このように、7x7のときに試行回数は最大となり、かつ分布はy=xのグラフに対して線対称になることがわかる。

まとめ

今回のような、整数問題は数式を用いて解析的に解くのが難しく、手当たり次第に解いていく方法が一般には好ましいと考えられる。そのときに考えられる方法がプログラミングによる解法である。総当たりでの探索を行う場合は、計算時間を考慮する必要性が出てくるが、今回のようなケースでは一瞬で解くことができた。