Project Euler 368（2）

http://projecteuler.net/index.php?section=problems&id=368

フォーラムにあった論文をちょっと見たが、たぶん同じ考え方だった。残念。Mathmaticaってそういう意味だったか。

昨日最初に考えようと思った、数字が3つ続かない数を数えてみましょう。
a_k,mを下2桁がmのk桁の自然数の個数とすると、

a_k+1,0 = a_k,0 + a_k,10 + ... + a_k,90
a_k+1,1 = a_k,1 + a_k,11 + ... + a_k,91
...
a_2,0 = ... = a_2,9 = 0
a_2,10 = ... = a_2,99 = 1

対称性を考慮して、

b_k ≡ a_k,0
c_k ≡ a_k,1 = ... = a_k,9
d_k ≡ a_k,11 = a_k,22 = ... = a_k,99
e_k ≡ a_k,10 = a_k,12 = ... = a_k,98

と置くと、

b_k+1 = 9e_k
c_k+1 = b_k + 9e_k
d_k+1 = c_k + 8e_k
e_k+1 = c_k + d_k + 8e_k

これを解くと、

r = 9.9083269132
b_k ≒ 0.824422632452r^k-2
c_k ≒ 0.907627661886r^k-2
d_k ≒ 0.824422632452r^k-2
e_k ≒ 0.907627661886r^k-2

k桁の自然数が3つ続かない数の個数は、

89.9307158942r^k-2

k桁の自然数の逆数の和はだいたい、

0.899307158942log10(r/10)^k-2

r/10 = 0.99083269132 < 1だから収束するわけです。