Project Euler 368(2)

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

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


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

ak+1,0 = ak,0 + ak,10 + ... + ak,90
ak+1,1 = ak,1 + ak,11 + ... + ak,91
...
a2,0 = ... = a2,9 = 0
a2,10 = ... = a2,99 = 1

対称性を考慮して、

bkak,0
ckak,1 = ... = ak,9
dkak,11 = ak,22 = ... = ak,99
ekak,10 = ak,12 = ... = ak,98

と置くと、

bk+1 = 9ek
ck+1 = bk + 9ek
dk+1 = ck + 8ek
ek+1 = ck + dk + 8ek

これを解くと、

r = 9.9083269132
bk ≒ 0.824422632452rk-2
ck ≒ 0.907627661886rk-2
dk ≒ 0.824422632452rk-2
ek ≒ 0.907627661886rk-2

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

89.9307158942rk-2

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

0.899307158942log10(r/10)k-2

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