『トリボナッチ数列の性質』解答

◆東京都　ぽこぺん さんからの解答。

【補題１】

m を任意の自然数とするとき，m を法として数列 {A(n)} は初項から循環する。

【証明】

法 m のもとで，A(n) は有限個（高々 m 通り）の値しか取らないので，
三つ組 (A(n+1), A(n+2), A(n+3)) も有限個（高々 m³ 通り）の組み合わせしか取ることはない。

したがって，

A(n+1) ≡ A(n'+1), A(n+2) ≡ A(n'+2), A(n+3) ≡ A(n'+3)　(mod m)

が成立する整数の組 n, n' (n＞n'≧0) が存在する。

このような n' のうち最小のものを r とするとき，もし r＞0 ならば，

A(n) ＝ A(n+3) - A(n+2) - A(n+1) ≡ A(r+3) - A(r+2) - A(r+1) ＝ A(r)

となって r の最小性に反するので，r＝0 である。このとき

A(n+1) ≡ A(1), A(n+2) ≡ A(2), A(n+3) ≡ A(3)　(mod m)

が成立する最小の n を n₀ とすれば， 数列 {A(n)} は
n₀ を周期として第 n₀ + 1 項以降は初項からの値が循環する。■

【補題２】

任意の自然数 M に対してある自然数 n が存在して，A(n) が M を超えない、いかなる素数によっても割り切れないようにできる。

【証明】

M を超えないすべての素数を p₁, p₂, …, p_k とし，
それぞれを法とするときの{A(n)} の周期を w₁, w₂, …, w_k とする。

このとき，たとえば w₁, w₂, …, w_k の最小公倍数 h を取ると，
すべての p_i (i＝1, 2, …, k) に対して

　A(h+1) ≡ 1　(mod p_i)

となる。■

【問題の証明】

補題２の M と n に対して，A(n) の 1 以外の約数は M より大きいから，
M を 10^N-1 と取ればよい。■

【例】

N＝3 のとき，M＝100 と取ると，M を超えない素数は 2, 3, …, 97 の 25 個ある。

このいずれの素数によっても A(n) が割り切れないような n (＞1) としては， 下表１の 1, 9, 16, 33, … があるが，それぞれに対する A(n) を素因数分解すると， 下表２のようになる。■

【コメント】

もし，Tribonacci数列 {A(n)} に含まれる素数が無限個あることがわかれば，本問は自明である。
しかし，Fibonacci数列に含まれる素数ですら，その個数が無限個あるかどうかはわかっていない。

Fibonacci数列 {F(n)} の場合には，F(mn) は F(m)，F(n) の倍数になるから，
F(n) が素数になるのは，n が素数であるときに限る。
しかし，この逆は成り立たない。

これまでに知られている素数は n の値が下記の場合だけである：

3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433,449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757,35999, 81839

一方，Tribonacci数列の場合には，加法定理

A(m+n) ＝ A(m)A(n) + A(m-1)A(n-1) + A(m-2)A(n-1) + A(m-1)A(n-2)

が証明できるので，

A(2n)＝A(n)2+A(n-1)2+2A(n-1)A(n-2)
A(3n)＝A(n)3+A(n-2)3+3 A(n)A(n-1)2-3A(n-1)2A(n-2)-6 A(n)A(n-1)A(n-2)

【表１】

法 p_i のもとでの A(n) の値（A(n) が 0 にならない n に対して）

【表２】

A(n) の素因数分解

 9                         149 = (素数)
16                       10609 = 1032
33                   334745777 = 1032 * 139 * 227
40                 23837527729 = 167 * 142739687
48               3122171529233 = 199 * 15689304167
53              65720971788709 = 163 * 257 * 647 * 1229 * 1973
56             408933139743937 = 29531 * 13847588627
65           98513851446415969 = 199 * 495044479630231
72         7015254043203144209 = 1259 * 5572084228120051
85     19341322569415713958901 = (素数)
93   2533271375725618104752561 = 645626791 * 3923739552074471
96  15762679542071167858843489 = (素数)

解答そのものは数行で終わってしまうのですが，コメントに述べたような発展性があり，非常に楽しい問題だと思います。

◆出題者のコメント。

ぽこぺんさんのおっしゃる通り、なかなか面白い問題ですね。
ちなみにこの問題を少し発展させて、それからもう少しスパイスを効かせると次のような問題になります。

【追加問題】

ｍをある定められた自然数とする。

このｍに対して、

　A(k)=２^k-1　（k=1,2,…ｍ）、　
　A(n+m)=A(n+m-1)+A(n+m-2)+…+A(n+1)+A(n)　
　　（ｎは任意の自然数）

というような数列{A(n)}を定める。また、

　D(n)＝（A(n)の最小の素因数）

とするとき、任意の自然数Ｎに対して次の条件を満たすｎが無数にあることを示せ。

（条件）D(n)≧ＮかつD(n+m+2)≧Ｎ

◆茨城県　こんにちは さんからの解答。

【追加問題解答】

【補題１】

sを任意の自然数とする。
任意の自然数nに対してA(n+w)≡A(n)　(mod　s)となるような自然数wが存在する。

【証明】

Tを任意の整数とする。
A(t)をsで割った余りは高々s通りの値しかない。
{A(t),A(t+1),…,A(t+m-1)}をsで割った余りも高々s^m個である。

よって

A(i)≡A(j)　(mod　s)、
A(i+1)≡A(j+1)　(mod　s)、
　…、
A(i+m-1)≡A(j+m-1)　(mod　s)

となるような自然数i＜jが存在する。

A(i+m)≡A(i+m-1)+・・・+A(i)
      ≡A(j+m-1)+…+A(j)
      ≡A(j+m)　(mod　s)

A(i-1)≡A(i+m)-A(i+m-1)-…-A(i)
      ≡A(j+m)-A(j+m-1)-…-A(j)
      ≡A(j-1)　(mod　s)、

【補題２】

sとwは補題1と同じものとする。
A(w+1)≡A(w)≡1　(mod　s)、
A(w-m)≡1　(mod　s)、
A(w-m-1)≡-1　(mod　s)

【証明】

補題1よりA(w+1)≡A(1)≡1　(mod　s)

2m-1≡A(m)
    ≡A(w+m)
    ≡A(w+m-1)+…+A(w+1)+A(w)
    ≡A(m-1)+…+A(1)+A(w)
    ≡2m-1-1+A(w)　(mod　s)

2m-2≡A(m-1)
    ≡A(w+m-1)
    ≡A(w+m-2)+…+A(w)+A(w-1)
    ≡A(m-2)+…+A(w)+A(w-1)
    ≡2m-2+A(w-1)　(mod　s)

同様に　
A(w-2)≡0　(mod　s)、
　…、
A(w-m+1)≡0　(mod　s)が言える。

1≡A(w)≡A(w-1)+…+A(w-m+1)+A(w-m)≡A(w-m)　(mod　s)

0≡A(w-1)≡A(w-2)+…+A(w-m)+A(w-m-1)≡1+A(w-m-1)　(mod　s)

A(w-m-1)≡-1　(mod　s)

【感想】

ちょっとした発想の転換が必要でした、面白かったです。

　『トリボナッチ数列の性質』へ

　数学の部屋へもどる