フィボナッチ数列に関する問題 大学入試

フィボナッチ数列1 1 2 3 5 8 13 21 .............. がある
初項は1　第2項は1であり　それ以後の項は前2項の和になっている
この数列の初項から第1000項までに1の位が7である数は全部でいくつあるか


という問題なのですが
書き出してみて規則性を見つけようとしましたが、見つからず
ならば一般項を表現してそれから解こうと思ったのですがそれもできず
うまく解けませんでした

どうやって解けばいいのでしょうか？

No.1 回答者： Nanashi334 回答日時： 2013/02/02 12:40

２で割った余りを並べると規則性が見えてきます

No.2 回答者： berokanda 回答日時： 2013/02/02 13:03

愚直にmod 10で考えると、

1,1,2,3,5,8,3,1,4,5,
9,4,3,7,0,7,7,4,1,5,
6,1,7,8,5,3,8,1,9,0,
9,9,8,7,5,2,7,9,6,5,
1,6,7,3,0,3,3,6,9,5,
4,9,3,2,5,7,2,9,1,0,
1,1,...
（10項ごとに改行しています）

となって周期60であることがわかります。

この後はわかりますよね？

No.3 回答者： asuncion 回答日時： 2013/02/02 13:15

十の位以上は無視してかまわないので、

とりあえず一の位だけを60個ほど書き出してみましょうか。
そうすると、何か規則性が見つかるかもしれません。

この回答へのお礼

なぜ60個書き出そうと思いつくのでしょうか？
この手の問題では規則性を見つけるために書き出すことはしますが
ふつう、たとえば30個程度書き出して、規則性が見つからなければ
あきらめて書き出す以外の方針で解こうとしますよね　少なくても試験場では

60個書き出せば絶対見つかるぞ！みたいなあたりでもつけられるのでしょうか？

お礼日時：2013/02/02 15:34

No.4 ベストアンサー 回答者： tmpname 回答日時： 2013/02/02 16:45

> なぜ60個書き出そうと思いつくのでしょうか？

60個かどうかは分からないにしても、ある項と次の項の1の位の組み合わせは、どう頑張っても10 * 10 = 100通りしかないのだから、多く見積もっても100以下の長さで周期的になっているのは分かるはず。

もっとケチろうとすると、10 = 2 * 5で、2と5が互いに素であることから、2で割った余りと5で割った余りを考える。同様の考察で2で割った余りは最大で2 * 2 = 4以下の長さで周期的になっているはずで、実際
1 1 0 1 1 ....
周期は3になっている。同様に5で割った余りは最大で25以下の長さで周期的になっているはずで、実際

1 1 2 3 0
3 3 1 4 0
4 4 3 2 0
2 2 4 1 0
1 1 ...

と実際周期は20になっている。
そうすると2 * 5 = 10で割った余りは 3 * 20 = 60の長さの周期になっている。

そこで、7 を2で割った余りは1であり、2で割った長さ3の周期列の中に1は2回現れている。同様に7を5で割った余りは2で、5で割った長さ20の周期列の中に2は4回現れていることから、10で割った長さ60の周期列の中に7は2 * 4 = 8回現れるはず。

これで60 * 16 = 960項までは調べ終わっていますから、残り40項で7が何回現れるか調べればよい。でも、結局ここで10で割った余りを計算し直すから、労力はあんまり変わりませんがね...

No.5 回答者： ereserve67 回答日時： 2013/02/02 18:22

理論的かつ数値的に考察しましょう．

第n項を10で割ったあまり（つまり1の位）をr_nとするとr_1～r_{1000}に7がいくつあるかという問題です．

r_1=r_2=1

（☆）r_{n+2}=r_{n+1}+r_n

ここで+は2ケタ以上になったら10の位以降を切り捨てるものとします．すると

r_{13}=3,r_{14}=7

で初めて7が出ます．これ以降7が出る項とその直前を追跡すると，

r_{15}=0,r_{16}=7
r_{16}=7,r_{17}=7
r_{22}=1,r_{23}=7
r_{33}=8,r_{34}=7
r_{36}=2,r_{37}=7
r_{42}=6,r_{43}=7
r_{55}=5,r_{56}=7
r_{73}=3,r_{74}=7

のように60項で同じパターンとなり，☆からこれ以降は周期的になります．つまりm=0,1,・・・として

r_{13+60m}=3,r_{14+60m}=7

となり

m=0のときr_{14+60m}=r_{14}までに1個
m≧1のときr_{15+60(m-1)}～r_{14+60m}に8個

7が存在します．14+60m≦1000とするとm≦16で

m=0とm=1,2,・・・,16に1+8×16=129個

7が存在します．残りの第14+60×16+1=975項から1000項までは第15項から第40項までと同じでこの中に

r_{15}=0,r_{16}=7
r_{16}=7,r_{17}=7
r_{22}=1,r_{23}=7
r_{33}=8,r_{34}=7
r_{36}=2,r_{37}=7

のように5つ7があります．結局

129+5=134個

となります．