3F1000000 （3 の フィボナッチ数列の第100万項乗）の下 6 桁を求めて下さい。念のため，
3F10 = 355 = 174449211009120179071170507 この数の下6桁は 170507
前にも，同様の質問があったけど，今回はそのときよりも大きな数になる。
しかし，ひるむ必要はない。
解答例は，この記事のコメントを参照。
最新の画像［もっと見る］
-
算額（その2135）
10時間前
-
算額（その2134）
16時間前
-
算額（その2133）
1日前
-
算額（その2132）
3日前
-
算額（その2131）
4日前
-
算額（その2130）
4日前
-
算額（その2129）
5日前
-
算額（その2128）
5日前
-
算額（その2127）
6日前
-
算額（その2126）
6日前
> i = 0
> x = 1
> repeat {
+ i = i+1
+ x = (3 * x) %% 1000000
+ if (x == 1) break
+ }
> cat(i)
50000
念のため，確認
> library(gmp)
> as.bigz(3) ^ as.bigz(49999) %% 1000000
Big Integer ('bigz') :
[1] 666667
> as.bigz(3) ^ as.bigz(50000) %% 1000000
Big Integer ('bigz') :
[1] 1
> as.bigz(3) ^ as.bigz(50001) %% 1000000
Big Integer ('bigz') :
[1] 3
つまり，3 のべき乗の下 6 桁は，50000 を法とした冪数で一致する。
念のため確認
> as.bigz(3) ^ as.bigz(123456) %% 1000000
Big Integer ('bigz') :
[1] 619521
> as.bigz(3) ^ as.bigz(623456) %% 1000000
Big Integer ('bigz') :
[1] 619521
50000を法としたとき，100万項のフィボナッチ数 F(1000000)は
> fib = function(n) {
+ a = b = 1
+ for (i in 3:n) {
+ c = (a+b) %% 50000
+ a = b
+ b = c
+ }
+ c
+ }
> fib(100000000)
[1] 46875
念のため
> fibnum(1000000) %% 50000
Big Integer ('bigz') :
[1] 46875
3 の F(1000000) 乗の下 6 桁は 3 の 46875 乗の下 6 桁と同じになる。
その数値は
> pow3 = function(n) {
+ x = 1
+ for (n in 1:n) {
+ x = (3 * x) %% 1000000
+ }
+ x
+ }
> pow3(46875)
[1] 733307
念のため
> as.bigz(3)^46875 %% 1000000
Big Integer ('bigz') :
[1] 733307
求める数は 733307 である。