PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 172 / 桁の繰り返しが少ない数

どの数字も3回を超えてあらわれないような18桁の数(先頭の0はゆるされない)はいくつあるか?

Problem 172 - Project Euler


漸化式を使って解きました。3回,2回,1回登場する文字がそれぞれ x, y, z 個ある数の個数を f(x, y, z) とおきます。

条件をみたす (x, y, z) は Reduce[ ] で求められます。


漸化式の立式に移りましょう。左から順に一列に数字を並べていきます。一番左は1から9のどれかです。

f(0, 0, 1)=9

次は1桁足したときの変化を考えます。(x, y, z) の数に1桁足すと (x, y, z+1), (x, y+1, z-1), (x+1, y-1, z) のいずれかができます。これを逆に考えると,(x, y, z) ができるのは次のようなときです。

  • (x-1, y+1, z) の y+1 にあたる数を書き足す。y+1 通り。
  • (x, y-1, z+1) の z+1 にあたる数を書き足す。z+1 通り。
  • (x, y, z-1) に新しい数を書き足す。10-x-y-(z-1) 通り。

漸化式はこうなります。

f(x,y,z)
= (y+1)*f(x-1,y+1,z)
+ (z+1)*f(x,y-1,z+1)
+ (10-x-y-(z - 1))*f(x,y,z-1)

あとは Mathematica に頑張ってもらって出来上がりです。