【C言語】フィボナッチ数列の10個の和と7番目の数との関係
https://sironekolab.com/archives/3021
1. 命題
フィボナッチ数列において，連続する 10 項の和は，第 7 項の 11 倍である。
2. 確認
フィボナッチ数列の生成関数 Fibonacci() を以下のように定義しておく。
function Fibonacci(n)
x,y = BigInt(0), BigInt(1)
for i in 1:n
x, y = y, x+y
end
return x
end;
x = Fibonacci.(13:22)'
1×10 adjoint(::Vector{BigInt}) with eltype BigInt:
233 377 610 987 1597 2584 4181 6765 10946 17711
x の和と，x[7] の 11 倍は等しい。
sum(x) # 和
45991
x[7] * 11 # 7 番目の要素の 11 倍
45991
SymPy だと簡単に確認できる。
using SymPy
@syms f[1:10]
(Sym[f₁, f₂, f₃, f₄, f₅, f₆, f₇, f₈, f₉, f₁₀],)
for i in 1:10
i >= 3 && (f[i] = f[i-2] + f[i-1])
println("$i: $(f[i])")
end
1: f₁
2: f₂
3: f₁ + f₂
4: f₁ + 2*f₂
5: 2*f₁ + 3*f₂
6: 3*f₁ + 5*f₂
7: 5*f₁ + 8*f₂
8: 8*f₁ + 13*f₂
9: 13*f₁ + 21*f₂
10: 21*f₁ + 34*f₂
(sum(f), 11(5*f[1] + 8*f[2])) |> println
(55*f₁ + 88*f₂, 55*f₁ + 88*f₂)
他にも同様な関係式が成り立つことがあるかどうかチェックしてみよう。
次に関係式が成り立つのは n = 14 のときである。
using SymPy
@syms f[1:14]
(Sym[f₁, f₂, f₃, f₄, f₅, f₆, f₇, f₈, f₉, f₁₀, f₁₁, f₁₂, f₁₃, f₁₄],)
for i in 1:14
i >= 3 && (f[i] = f[i-2] + f[i-1])
println("$i: $(f[i])")
end
1: f₁
2: f₂
3: f₁ + f₂
4: f₁ + 2*f₂
5: 2*f₁ + 3*f₂
6: 3*f₁ + 5*f₂
7: 5*f₁ + 8*f₂
8: 8*f₁ + 13*f₂
9: 13*f₁ + 21*f₂
10: 21*f₁ + 34*f₂
11: 34*f₁ + 55*f₂
12: 55*f₁ + 89*f₂
13: 89*f₁ + 144*f₂
14: 144*f₁ + 233*f₂
(sum(f), 29(13*f[1] + 21*f[2])) |> println
(377*f₁ + 609*f₂, 377*f₁ + 609*f₂)
3. 確認の結果
その他にいくつか試してみると，k = 0, 1, 2, 3, ..., とすると n = 4k + 2 のときに関係式が存在する。
k = 0, n = 2 項の和は 1*f₁ + 1*f₂ で，これは第 3 項 1*f₁ + 1*f₂ の 1 倍である。
k = 1, n = 6 項の和は 8*f₁ + 12*f₂ で，これは第 5 項 2*f₁ + 3*f₂ の 4 倍である。
k = 2, n = 10 項の和は 55*f₁ + 88*f₂ で，これは第 7 項 5*f₁ + 8*f₂ の 11 倍である。
k = 3, n = 14 項の和は 377*f₁ + 609*f₂ で，これは第 9 項 13*f₁ + 21*f₂ の 29 倍である。
k = 4, n = 18 項の和は 2584*f₁ + 4180*f₂ で，これは第 11 項 34*f₁ + 55*f₂ の 76 倍である。
k = 5, n = 22 項の和は 17711*f₁ + 28656*f₂ で，これは第 13 項 89*f₁ + 144*f₂ の 199 倍である。
k = 6, n = 26 項の和は 121393*f₁ + 196417*f₂ で，これは第 15 項 233*f₁ + 377*f₂ の 521 倍である。
OEIS https://oeis.org/?language=japanese も参考にして，各列の数列は以下のように生成される。
4. 関係式の一般項
k 番目の関係式を書き出す関数を定義しておく。
seriese(k) = "k = $k, n = $(4k + 2) 項の和は $(Fibonacci(4k + 2))*f₁ + $(Fibonacci(4k + 3) - 1)*f₂ で，" *
"これは第 $(2k+3) 項 $(Fibonacci(2k + 1))*f₁ + $(Fibonacci(2k + 2))*f₂ の $(Fibonacci(2k) + Fibonacci(2k + 2)) 倍である。";
k = 6 まで，更に k = 20 までについて関係式を求める。
for k = 0:20
println(seriese(k))
end
k = 0, n = 2 項の和は 1*f₁ + 1*f₂ で，これは第 3 項 1*f₁ + 1*f₂ の 1 倍である。
k = 1, n = 6 項の和は 8*f₁ + 12*f₂ で，これは第 5 項 2*f₁ + 3*f₂ の 4 倍である。
k = 2, n = 10 項の和は 55*f₁ + 88*f₂ で，これは第 7 項 5*f₁ + 8*f₂ の 11 倍である。
k = 3, n = 14 項の和は 377*f₁ + 609*f₂ で，これは第 9 項 13*f₁ + 21*f₂ の 29 倍である。
k = 4, n = 18 項の和は 2584*f₁ + 4180*f₂ で，これは第 11 項 34*f₁ + 55*f₂ の 76 倍である。
k = 5, n = 22 項の和は 17711*f₁ + 28656*f₂ で，これは第 13 項 89*f₁ + 144*f₂ の 199 倍である。
k = 6, n = 26 項の和は 121393*f₁ + 196417*f₂ で，これは第 15 項 233*f₁ + 377*f₂ の 521 倍である。
k = 7, n = 30 項の和は 832040*f₁ + 1346268*f₂ で，これは第 17 項 610*f₁ + 987*f₂ の 1364 倍である。
k = 8, n = 34 項の和は 5702887*f₁ + 9227464*f₂ で，これは第 19 項 1597*f₁ + 2584*f₂ の 3571 倍である。
k = 9, n = 38 項の和は 39088169*f₁ + 63245985*f₂ で，これは第 21 項 4181*f₁ + 6765*f₂ の 9349 倍である。
k = 10, n = 42 項の和は 267914296*f₁ + 433494436*f₂ で，これは第 23 項 10946*f₁ + 17711*f₂ の 24476 倍である。
k = 11, n = 46 項の和は 1836311903*f₁ + 2971215072*f₂ で，これは第 25 項 28657*f₁ + 46368*f₂ の 64079 倍である。
k = 12, n = 50 項の和は 12586269025*f₁ + 20365011073*f₂ で，これは第 27 項 75025*f₁ + 121393*f₂ の 167761 倍である。
k = 13, n = 54 項の和は 86267571272*f₁ + 139583862444*f₂ で，これは第 29 項 196418*f₁ + 317811*f₂ の 439204 倍である。
k = 14, n = 58 項の和は 591286729879*f₁ + 956722026040*f₂ で，これは第 31 項 514229*f₁ + 832040*f₂ の 1149851 倍である。
k = 15, n = 62 項の和は 4052739537881*f₁ + 6557470319841*f₂ で，これは第 33 項 1346269*f₁ + 2178309*f₂ の 3010349 倍である。
k = 16, n = 66 項の和は 27777890035288*f₁ + 44945570212852*f₂ で，これは第 35 項 3524578*f₁ + 5702887*f₂ の 7881196 倍である。
k = 17, n = 70 項の和は 190392490709135*f₁ + 308061521170128*f₂ で，これは第 37 項 9227465*f₁ + 14930352*f₂ の 20633239 倍である。
k = 18, n = 74 項の和は 1304969544928657*f₁ + 2111485077978049*f₂ で，これは第 39 項 24157817*f₁ + 39088169*f₂ の 54018521 倍である。
k = 19, n = 78 項の和は 8944394323791464*f₁ + 14472334024676220*f₂ で，これは第 41 項 63245986*f₁ + 102334155*f₂ の 141422324 倍である。
k = 20, n = 82 項の和は 61305790721611591*f₁ + 99194853094755496*f₂ で，これは第 43 項 165580141*f₁ + 267914296*f₂ の 370248451 倍である。
5. 検算
k = 20, n = 82 のとき，第 11 項から第 92 項までのフィボナッチ数列を，n = 82 個の要素を持つベクトルに設定する。
x = Fibonacci.(11:92)
82-element Vector{BigInt}:
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
⋮
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
x の総和 sum(x) は x[43] の 370248451 倍に等しい。
sum(x), 61305790721611591*x[1] + 99194853094755496*x[2] # 和, x の型は BigInt
(19740274219868223023, 19740274219868223023)
x[43], 165580141*x[1] + 267914296*x[2] # 43 番目の要素
(53316291173, 53316291173)
370248451 * x[43], 370248451 * (165580141*x[1] + 267914296*x[2]) # 倍数 * 43 番目の要素
(19740274219868223023, 19740274219868223023)
