09/02/04 07:08:15
>>865
0～(10^n)-1 の整数で、7 がつかず、7 で割って余りが m になるものの数を a[n,m] とする
a[n,m] は、a[0] = 1, a[1] = a[2] = … = a[6] = 0,
a[n+1,m] = a[n, (m-8*10^n) mod 7] + a[n, (m-9*10^n) mod 7] + Σ[k=0,6]a[n,k]
(x mod y は整数 x を整数 y で割った余りで、0 ≦ x mod y ＜ y とする)
を満たし、計算すると、
a[0,0]～a[0,6] : 1 0 0 0 0 0 0
a[1,0]～a[1,6] : 1 2 2 1 1 1 1
a[2,0]～a[2,6] : 12 12 11 11 12 12 11
a[3,0]～a[3,6] : 104 104 105 104 104 104 104
a[4,0]～a[4,6] : 938 938 937 937 937 937 937
a[5,0]～a[5,6] : 8435 8436 8436 8435 8436 8436 8435
a[6,0]～a[6,6] : 75921 75920 75920 75920 75920 75920 75920
a[7,0]～a[7,6] : 683281 683282 683282 683281 683281 683281 683281
a[8,0]～a[8,6] : 6149532 6149532 6149531 6149531 6149532 6149532 6149531
a[9,0]～a[9,6] : 55345784 55345784 55345785 55345784 55345784 55345784 55345784
a[n,m] = [(9^n)/7] または [(9^n)/7] + 1 ([ ] はガウス記号)
で、+1 がつくかつかないかは n に関して 6 の周期で同じことの繰り返しになると推測できる
これを数学的帰納法で証明すればいい
つまり、b[n,m] (0≦n≦5, 0≦m≦6) を
b[0,0]～b[0,6] : 1 0 0 0 0 0 0
b[1,0]～b[1,6] : 0 1 1 0 0 0 0
b[2,0]～b[2,6] : 1 1 0 0 1 1 0
b[3,0]～b[3,6] : 0 0 1 0 0 0 0
b[4,0]～b[4,6] : 1 1 0 0 0 0 0
b[5,0]～b[5,6] : 0 1 1 0 1 1 0
として
a[n,m] = [(9^n)/7] + b[n mod 6, m]
が最初の漸化式を満足することを確かめればいい
(6*7パターン確かめないといけないから、手間はかかる)