循環数列について

質問

数列aをa=bq-2^nとし、aとqは、自然数とします。ｎの値を代入するとき、a>0を満たす最小のｑの値をｑに代入します。例えば、ｂ＝３のとき、a=3q-2^n で、1.2.1.2・・・の循環する数列になります。ｂ＝７のときは、5.3.6のループに。ｂ＝９のときは、7.5.1.2.4.8・・・のループに。ｂの値とループの規則性をできるだけ一般化しようと取り組んでいます。何か分かる方がいらしたらお願いします。

回答No.2

nakaizu · ベストアンサー

この数列はとても奥深いものがあります。専門家にとってもまだわからないことがたくさんあります。
以下ではbが偶数のときは考慮からはずしておきます。
まず、周期の長さですが、No1の方が言われるようにφ(b)に関連あります。正確には周期はφ(b)の約数になります。約数のうちのどれになるのかは大変難しい問題です。
bが素数の時には、bを8で割った余りが1か7のときには
周期が(b-1)/2の約数になり、8で割った余りが3か5のときには周期が(b-1)/2の約数にならないことが知られています。
周期については、それ以外のことはよくわかっていません。専門家による研究はいくつかありますが、普通の人には理解できないと思われます。

φ(b)の定義はNo１の方の書かれている通りですが、「互いに素である」ということをご存じないかもしれません。互いに素とは最大公約数が１であることです。
ｂが素数ならばφ(b)=b-1となります。
ほかに簡単にわかる特徴としてはループの最後は必ずb-1になります。
また1が現れるときは必ず前半の最後になります。さらに前半の数をbから引くと後半の数になります。
自動的に1が現れるときは周期は偶数となります。
それからaの求め方ですが、次のようにすると簡単です。
まず、2から始めて数値を2倍にしていきます。ｂを超えたらｂを引いて下さい(→で表しました)。
b=11のときには次のようになります。
2,4,8,16→5,10,20→9,18→7,14→3,6,12→1
この数値をｂ=11から引きます
9,7,3,6,1,2,4,8,5,10
これが求める数列です。

お礼

分かりやすく回答していただき、参考になりました。ありがとうございます。

回答No.1

grothendieck

ｎを正整数とします。このとき，１からｎまでの整数で，ｎと互いに素となるものの個数をφ(ｎ) と表しオイラー関数と呼びます。代数学では次の有名な定理があります。
ａをｎと互いに素な整数とする。このとき，
　ａ^φ(ｎ) ≡１　ｍｏｄ ｎ (オイラーの定理)
したがってご質問の数列の周期を求めることは、φ(ｎ)を求めることに帰着されます。

参考URL：

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html

お礼

回答ありがとうございます。ホームページ参考になりました。