�������裴�������ʬ�β�����

Taro
11と22があることは早いうちに気づきましたが、問題文中の周期の数を
数え間違えてしまったりしてましたorz
おうち　　 11月10日（木） 0:07:59　　 　　26121
あ〜く＠ジューク
11と22の存在を忘れていましたorz
未完成の蜜柑星　　 11月10日（木） 0:09:41　　 MAIL:ishizaki@qa.so-net.ne.jp 　　26122
トトロ＠Ｎ
1→12→6→3→14→7→18→9→20→10→5→16→8→4→2→1に出てくる15個と
11、22の17個ですね。止まらない数を数えてました。
兵庫県明石市　　 11月10日（木） 0:09:48　　 MAIL:h-sakai@zb3.so-net.ne.jp 　　26123
ウラル
トトロさんと同じ発想するのに12分かかってました。来週こそはリベンジ狙います・・・
http://gtrambler815.blog9.fc2.comでサイトに移れますので、そちらのほうも見ていってください。
　　 11月10日（木） 0:18:28　　 　　26124
shin
３を２回数えてしまいました。
眠いのかな…
石川県　　 11月10日（木） 0:26:59　　 　　26125
吉川　マサル
これ、証明問題にしたら、東大あたりで来年出そうな感じしません？（ここんとこ、東大はこういうの好きだし）

　それはそうと、出題の際に「例を書くべきかどうか」はちょっと迷いました。っていうか、今思えば最後まで書かなくても良かったし、停止する数字である必要もなかったんですね...。
PowerBook G4　　 11月10日（木） 0:35:55　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　26126
スモークマン
計算してみると、1〜11は可能。
ということは、それらの中の奇数に11を足した数も可能。
つまり、1，12，2，3，14，4，5，16，6，7，18，8，9，20，10，11，22の17個。
でも正確にはどう証明するんだろう。。。
金光＠岡山　　 11月10日（木） 0:37:31　　 MAIL:kennji72001@yahoo.co.jp 　　26127
holden
一個数え忘れてました・・・。
　　 11月10日（木） 0:39:06　　 　　26128
Ｍｒ．ドンドコドン
最初、題意がよくつかめませんでした。（＾。＾）
３＞１４＞７＞１８＞９＞２０＞１０＞５＞１６＞８＞４＞２＞１＞１２＞６＞３のサイクルで、これらの数字は、もとの数字に戻ることがわかりました。
では、このサイクルにない１１は、１１＞２２＞１１とすぐ戻ってきます。
１３は、１３＞２４＞１２＞６・・・＞１＞１２＞６となり戻りません。
１５，１７，１９，２１，２３，２４〜も戻りません。
あと、忘れそうになった２２は、２２＞１１＞２２とすぐ戻ります。
答えは問題例のサイクルの１５個と、１１＆２２の合計１７個と求めました。
　　 11月10日（木） 1:23:47　　 MAIL:qqmz48pc9@alpha.ocn.ne.jp 　　26130
早起きxはくy
奇数nに11を足しあわせると偶数になり、2で割った数はn>11+11のとき
nよりも常に小さくなる。そのため操作を繰り返して元の数字に戻るためには
n≦22である必要がある。n<0のとき操作によって得た値が負のときは単調
に増加、一度正になると負に戻らないため不適。
あとは、問題文に出てきた数列以外の1≦n≦22までの数字はしらみつぶし。
　　 11月10日（木） 5:33:24　　 　　26131
スモークマン
nが偶数の時は、次はn/2だから等しくはならない。
n/2+11=n,次は、(n/2+11)/2+11=n,・・・
最初の式から、n=22,次もn=22,・・・

nが奇数の時、n=(n+11)/2,((n+11)/2+11)/2,・・・
最初の式から、n=11,11,・・・

これらから、偶数の最大は、22,奇数の最大は11とわかる。
ここから先が見えない。。。
金光　　 11月10日（木） 8:38:33　　 MAIL:kennji72001@yahoo.co.jp 　　26132
ハラギャーテイ
おはようございます

プログラムでは確かめられないはずですが、プログラムで
解きました。
北九州　　 11月10日（木） 9:09:34　　 HomePage:信号処理に挑戦　　26133
uchinyan
はい、おはようございます。面白い問題でした。
証明にはなっていませんが、直感的には、次のような感じ、17 個で認証しました (^^;
n が奇数のときは、n+11 は偶数なので (n+11)/2 になります。ところが、n > 11 では、(n+11)/2 < n なので、必ず、最初より小さくなります。
n が偶数のときは、明らかに、n/2 < n です。
結局、n > 11 のときは、必ず、最初より小さくなります。また、
3 - 14 - 7 - 18 - 9 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1 - 12 - 6 - 3
のループは例として示されているし、
11 - 22 - 11
は明らかなので、結局、これ以外は、これらのループに入ってきて抜け出せなくなるのでは？、と思いました。
証明としては、これ以外のループがないことを示さないといけないんだけど、今は時間がないし、難しいのかな．．．？
ネコの住む家　　 11月10日（木） 11:24:58　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26134
なか
あるループに現れる最小の数をａとする。ａはもちろん奇数である。
したがって、ａの次はａ＋１１、その次は、（ａ＋１１）／２となる。
ａはループ内最小なのでａ≦（ａ＋１１）／２、よってａ≦１１である。
つまり、ａは、１，３，５，７，９，１１のいずれかである。

これら６つの候補を吟味すると、
まず、１→１２→６→３→１４→７→１８→９→２０→１０→５→１６→８→４→２→１（適）
次に、３，５，７，９の４候補は１を含むループ内に現れたので最小の数になれず不適である。
最後に、１１→２２→１１（適）

以上、ループは２個存在する。そして題意を満たす数は、
１を最小とするループ上に１５個、１１を最小とするループ上に２個、合わせて１７個ある。
　　 11月10日（木） 9:54:31　　 MAIL:naka@sansu.org 　　26135
uchinyan
#26134
＞証明としては、これ以外のループがないことを示さないといけないんだけど、今は時間がないし、難しいのかな．．．？
あは、アホみたいに簡単でした。要するに、
すべての自然数 n は、題意の操作によって、3 を含むループ又は 11 を含むループに入る。
ことを示せばOKです。#26134で既に証明は終わっているといってもいいですが、
ちゃんとした証明は、例えば、数学的帰納法を使って次のようにやればいいでしょう。
まず、n が偶数の場合、奇数になるまで 2 で割ることを繰り返すことによってループが生じることはなく、奇数の場合に帰着します。
n が奇数の場合、n <= 11 のときは、3 を含むループ又は 11 を含むループに入っているので、明らか。
n >= 13 の場合、今、n-2 以下の奇数で成立すると仮定します。すると、n-1 は偶数なので、この仮定は n-1 以下で成立するとしてOKです。
すると、奇数の場合の操作 n+11 で偶数になり (n+11)/2 となりますが、n >= 13 では (n+11)/2 < n なので、
帰納法の仮定によって、(n+1)/2 は、3 を含むループ又は 11 を含むループに入ります。
n -> n+11 -> (n+11)/2 ではループは生じないので、結局、n も3 を含むループ又は 11 を含むループに入ります。
これで、証明できました。
なお、有名なコラッツ予想を思い出しました。
n 奇数：n -> 3n+1, n 偶数：n -> n/2 を繰り返すと、すべて、1 になる。
この場合は、(3n+1)/2 = n + (n+1)/2 なので、単純に減少することはなく、格段に難しくなります。
今回は、奇数の場合の n の係数が 1 なのがポイントですね。
ネコの住む家　　 11月10日（木） 10:57:49　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26136
uchinyan
そうそう、問題文は、「自然数」ではなくて、「整数」ですね。負も考えないといけないか．．．
でも、n < 0 の場合は、明らかに、n < n + 11, n < n/2 なので単調増加で、一度、正になると負には戻らないから、ループはなし、
で、正の場合に帰着しますね。
それと、#26136の
＞帰納法の仮定によって、(n+1)/2 は、3 を含むループ又は 11 を含むループに入ります。
の「(n+1)/2」は、もちろん、「(n+11)/2」の間違いです。
なお、掲示板読みました。
n < 0 の話は、#26131の 早起きxはくy さんの
＞n<0のとき操作によって得た値が負のときは単調 に増加、一度正になると負に戻らないため不適。
で、n < 0 を忘れていることに気付きました。ご指摘ありがとうございます。
#26135のなかさんの証明も簡単でいいですね。
#26126の
＞これ、証明問題にしたら、東大あたりで来年出そうな感じしません？（ここんとこ、東大はこういうの好きだし）
東大の問題としては、少なくともこのままでは、さすがに易しすぎるのでは？ (^^;
ネコの住む家　　 11月10日（木） 13:48:08　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26137
大岡　敏幸
やられました（＾＾；
サイクルから例示してある数は全て該当して残りを探すって感じだなーっと思ったんですが、１１＆２２は該当しないと思いこんでしまったのが今回の間違えでした。１１→２２→１１　これも当てはまるんでした（＾＾；
１５としてもなかなか正解出来ないので、少し悩んでしまった今回です（＾＾）
石川県　　 11月10日（木） 11:35:42　　 MAIL:toshi009@land.hokuriku.ne.jp 　　26138
みかん
２０までの数で試しているうちになんとなく「ループを形成していない数は
どこかでループに入ってきて出られなくなる」という印象はあったので、
２通りが見つかった１７で認証。

でも、これって小学生に分かりやすく「１７個以外にない」ことを教えるのは
大変なような…。
　　 11月10日（木） 11:49:47　　 　　26139
とくそん
はじめまして
n >= (n + 11) / 2 + 11 に該当する n は不要として、1〜33を力押しで検討してました。なかさんの解答が綺麗ですね
負数は、-11が入力できないことと正になった時点で戻らなさそうだったので省きましたが、考慮した方が良かったでしょうか
では、また
　　 11月10日（木） 12:02:06　　 　　26140
M.Hossie
　こんにちは、超お久し振りです。久々にのぞいてみました。
　これは絶対に例示されたループの数と１１，２２以外にはないと直感しました。ちゃんとした証明は考えてないですが、面白い問題ですね。

　マサルさんにはお話ししましたが、来年３月で会社自体が姿を消すエアー北海道 (ADK) の路線を乗りに１２月の３連休は奥尻島へ行くことにしました。機材はつい数年前まで南西航空でも飛んでいましたが、今では日本にたった１機のツインオッター (DHC-6；１９人乗り) です。元旦は「修行初め」としてバーゲンフェアを使って、こちらも来年で廃止が決まっている YS-11 に乗りに福岡＝鹿児島を往復します。この１０月には DC-10 も廃止されました。新旧交代が激しいですね。
某温泉地　　 11月10日（木） 12:23:47　　 　　26141
NV
　これに似た問題で、奇数なら１を加えて２倍。偶数なら２で割る。
これを繰り返すと、必ず４→２→１→４　のループになるというのをどこかで見た気がするのですが。これは、どんなものだったでしょうか？
　　 11月10日（木） 14:40:25　　 　　26142
uchinyan
#26142：
n = 1 で、1 -> 2 * (1+1) = 4 -> 2 -> 1 でループ。
n > 1 なる奇数で、n -> 2(n+1) -> n+1 > (n+1)/2 だから、(n+1)/2 < n、つまり n > 1 の奇数はすべて 1 のループに入りますね。
偶数 n は、n/2 < n で、いつかは奇数に帰着するから、明らかですね。
ネコの住む家　　 11月10日（木） 17:59:36　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26143
Chiba
Ｅｘｃｅｌで計算させてかぞえました。理論は難しそうなのでしらみつぶしの方が速そうなので
ループがきれいに現れていました。
皆さんの解説でなんとなく解りました。
　　 11月11日（金） 1:33:42　　 　　26144
スモークマン
関係ないけど。。。シンプル問
友人からの問題
次の式をみたす正整数nの値を決定せよ
133^5+110^5+84^5+27^5=n^5
金光　　 11月11日（金） 10:59:24　　 MAIL:kennji72001@yahoo.co.jp 　　26145
?????
#26145
144
　　 11月11日（金） 17:30:51　　 　　26147
uchinyan
ちょっとだけ、今回の問題を一般化してみました。
n 奇数：n -> n + c, n 偶数：n -> n/2, n は自然数、c は一般に奇数
この場合の今回の問題の機械が停止する数の個数は、掲示板の書き込みをよく読めば、c 以下の奇数と 2c 以下の偶数、と分かるので、
(3c + 1)/2 個であることは容易に分かると思います。
個人的に、どうなんだろう、と思ったのは、これではなくて、できるループの数です。
何か規則性があるのかな、と思って少し考えても分からず、プログラムで調べてみました。
これに使ったコードは perl ですが、次のとおりです。

$n = 100; @q = ();
for($c = 1; $c < $n; $c += 2) {
　@p = (); $cnt = 0;
　for($i = 1; $i <= $c; $i += 2) {
　　$f = 0;
　　foreach (@p) {
　　　if($i == $_) {
　　　　$f = 1; break;
　　　}
　　}
　　next if($f == 1);
　　$a = $i;
　　do {
　　　push(@p,$a);
　　　if(($a % 2) == 0) {
　　　　$a = $a/2;
　　　}
　　　else {
　　　　$a = $a + $c;
　　　}
　　} until($a == $i);
　　push(@p,'B'); $cnt += 1;
　}
　print "n -> n+$c, n -> n/2, Case : \n";
　$m = @p - $cnt;
　print "Number of Loops : $cnt\n";
　print "Numbers in Loops : $m\n\n";
　push(@q,$cnt);
}
print "Sequense of Loop Number : \n@q\n";

結果は、1 <= c <= 99 で、
1 2 2 3 3 2 2 5 3 2 6 3 3 4 2 7 5 6 2 5 3 4 8 3 5 8 2 5 5 2 2 13 7 2 6 3 9 8 6 3 5 2 12 5 9 10 14 5 3 8
となりました。一見、何の規則性もなさそうです。
やはりこれといって面白いことはないか、と思ったのですが、念のために例の数列サイト、
http://www.research.att.com/~njas/sequences/
で調べたところ、何と、ID Number: A081844 であるようです。

ID Number: A081844
．．．
Name: Number of irreducible factors of x^(2n+1) - 1 over GF(2).
GF(2) 上の x^(2n+1) - 1 の既約因子(既約多項式？)の数
Comments: Also number of nonisomorphic "pure" chain rings with certain parameters.
あるパラメタをもつ非同型？な「純粋？」連鎖環？の数(個数？)でもある。

数学の予備知識のない私にはチンプンカンプンなのですが、GF とは「ガロア体」のことらしく、
群論とかの話とつながっているんでしょうか？　関連論文には、楕円曲線の話もあるようです。
マサルさま、なかさま、常連の皆様、何かご存知でしょうか？
ご存じなければ、無視してください。済みません。
ネコの住む家　　 11月11日（金） 18:11:17　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26148
uchinyan
ついでといっては何ですが．．．^^;
スモークマンさんの#26145は、#26147のとおり、144 ですね。
え、解法？　もちろん、プログラム！
まぁ、強いて言うと、左辺が 6^5 を因数にもつことはすぐに分かるので、そこから電卓でもできますが (^^;
左辺をうまく式変形できるのかな？
ネコの住む家　　 11月11日（金） 18:20:23　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26149
tapu
問題は解けましたが、奇数にたす１１という数はいったいどうやって出てきたのでしょう？教えてください！
　　 11月11日（金） 18:45:56　　 　　26150
スモークマン
#26147,#26149 ？？？さん、uchinyan さん、正解です。

友人からの回答
mod 2　で左辺は1+0+0+1=2≡0
mod 3ハハハ 1^5+(-1)^5+0+0≡0
mod 5ハハハ (-2)^5+0+(-1)^5+2^5=-4≡4
よってn^5は2,3の倍数で5で割ると4余る正整数
一般にk^5≡k　（mod5）であるからn自身が5で割ると4余る
また2,3で割り切れる
よってn=24+30m
133をこえるものは144,174,..
しかし174^5=133^5*(174/133)^5＞133^5*1.3^5
　　　　　　　　＞133^5*3=133^5+133^5+133^5
　　　　　　　　>133^5+110^5+(84+27)^5
　　　　　　　　>左辺
よって可能性があるのは144のみで実際に確かめると
解であることがわかる。

k^5≡k (mod 5) って知ってました？（フェルマーの小定理か！）
でも、すぐには思いつかないですよねえ・・・
金光＠岡山　　 11月11日（金） 23:02:50　　 MAIL:kennji72001@yahoo.co.jp 　　26151
sin
>>NVさん
たぶんコラッツ予想ですね．有名な未解決問題みたいです．
奇数の場合は3倍して１を足す，偶数は２で割る．
この問題もこれに似ている気がするのですが．

私は数論に関しては全く分からないので，
関係ない話題でしたら申し訳ございません．
　　 11月12日（土） 2:28:49　　 　　26152
sin
過去ログ読むと，言及されていましたね．
すみません，下のは無視してください
（削除したかったのですが，パスワード設定していなかったので）．
　　 11月12日（土） 2:45:06　　 　　26153
uchinyan
#26151：スモークマンさんへ。解説ありがとうございます。
なるほど、フェルマーの小定理を使うのですね。他のことに気を取られていて、いい加減な解答で済みませんでした。
ところで、#26148の私の疑問に関して、何かご存じないですか？
ネコの住む家　　 11月12日（土） 9:01:53　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26154
uchinyan
#26148について：
例の数列サイトの情報などをもとに調べた限りでは、証明は全くできていませんが、
ループの個数 = L = ��[d|c]{φ(d)/ord2(d)}
となるようです。ここで、
・d|c は、d は c の約数であることを示します。
・φ(d) は、いつか出てきたオイラー関数で、d より小さい自然数で d と互いに素なものの個数を表します。
・ord2(d) は、2^k ≡ 1 (mod d) となる k のことです。ただし、d = 1 は 1 と定義します。
例えば、今回の問題では、c = 11 なので、
d = 1, or 11, φ(1) = 1, φ(11) = 10, ord2(1) = 1, ord2(11) = 10 (これはフェルマーの小定理から！)
となり、
L = ��[d|c]{φ(d)/ord2(d)} = φ(1)/ord2(1) + φ(11)/ord2(11) = 1/1 + 10/10 = 2
で、確かに一致します。他の場合、例えば、
c = 9 : L = φ(1)/ord2(1) + φ(3)/ord2(3) + φ(9)/ord2(9) = 1/1 + 2/2 + 6/6 = 3
c = 15 : L = φ(1)/ord2(1) + φ(3)/ord2(3) + φ(5)/ord2(5) + φ(15)/ord2(15) = 1/1 + 2/2 + 4/4 + 8/4 = 5
などとなり、確かに、#26148の計算と一致します。
証明は．．．うーむ、私の手に余りそうですが、また、何か分かったらご報告します。
ネコの住む家　　 11月12日（土） 13:00:25　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26155
スモークマン
#26148
uchinyan さんへ。
面白いですね〜としか。。。
いつも、原始根とか、ガロア群の本読んでも挫折してしまいます。。。
分かりやすく解説して下さる方がいらっしゃらないかとず〜っと思ってるんですよ〜
金光　　 11月12日（土） 16:04:00　　 MAIL:kennji72001@yahoo.co.jp 　　26156
スナフキン
解けた・・・けど悔しい！１１と２２を抜かしてた・・・。
１１→２２→１１→２２→１１→２２・・・ってず〜っと続くんだと思ってた。・・・。・・・。ひぃ〜〜〜っ！
　　 11月12日（土） 21:37:10　　 　　26157
N.Nishi
１１と２２がありましたね。
　　 11月12日（土） 22:01:49　　 　　26158
スモークマン
前菜問

月末が同じ曜日になることは最高１年間に何回？
ちなみに来年の月末が木曜になるのは何月？（カレンダー見ないでね！）
金光　　 11月13日（日） 15:35:55　　 MAIL:kennji72001@yahoo.co.jp 　　26159
uchinyan
#26148及び#26155について：
あー、何となく分かったようです。あまり厳密ではないですが、ポイントを中心に報告しておきます。
少し長くなります。ご勘弁を。

まずは、後で関係するので、#26148の
＞この場合の今回の問題の機械が停止する数の個数は、掲示板の書き込みをよく読めば、
＞c 以下の奇数と 2c 以下の偶数、と分かるので、
＞(3c + 1)/2 個であることは容易に分かると思います。
を証明しておきましょう。#26148の操作を操作 C と呼ぶことにします。
まず、n < 0 は、n > 0 に帰着し、n が偶数の場合は奇数の場合に帰着します。
また、n > c の奇数のときは、操作 C を行うことで n より小さな (n+c)/2 になるので、n がループを作らないことは c = 11 の場合と同じです。
そこで、1 <= n <= c の奇数の場合を考えればOKです。このとき、n+c の操作によって、偶数は、2 から 2c までに限定されることに注意します。
さて、操作 C は何回でも可能ですが、0 < n <= c の奇数に対しては、何回行ってもこの範囲を出ないので、
鳩ノ巣論理によって、何回かの操作の後で同じ値になるはずです。この値を m とします。m は、1 <= m <= c の奇数としてOKです。
ここで、今、次のような操作 C' を考えます。
操作 C'：1 <= n <= c のとき、n -> 2n、c < n <= 2c のとき n -> n-c
この操作の初項を先ほどの奇数 m にすると、その系列の n は、1 <= n <= 2c の範囲を出ることはなく、
特に奇数は 1 <= n <= c の範囲を出ないことが分かります。
そして、その定義より、C' は C の逆操作になっていることも分かります。
そこで、もし、1 <= n <= c のある n が n から操作 C によって m になったとすると、m からの操作 C' によって n に一意に戻るので、
n は m のループ上にあることになります。
1 <= n <= c なるすべての奇数 n に対して、このような m が存在することは、先ほど示したとおりです。
ちなみに、c < n なる奇数 n は、m から操作 C' によっては到達できず、ループからの枝分かれになっています。
これで、1 <= n <= c の奇数はすべて何らかのループ上にあり、操作 C の n+c によって 2 <= n <= 2c の偶数もすべてループ上にあり、
結局、ループ上にある数の個数は、c + (c + 1)/2 = (3c + 1)/2 個になります。

さて、本題はここからです。#26155の
＞ループの個数 = L = ��[d|c]{φ(d)/ord2(d)}
を考えます。
今考える対象は、ループ上にある数に限定していいので、1 <= n <= c なる奇数と 1 <= n <= 2c なる偶数です。
このとき、操作 C と先ほどの逆操作 C' とは一対一に対応しているので、操作 C の代わりに逆操作 C' を考えます。
さらに逆操作 C' は次のように書き換えられることに注意します。これを、新たに、操作 A と呼ぶことにします。
操作 A：1 <= n <= c なる奇数 n に対して、2^k * n を c で割った余りを対応させる。
n が偶数の場合は、k に吸収させればよく、c < n <= 2c の操作は、割った余り、に対応します。
さて、n がループ上にあるということは、操作 A を使うと簡単に書けて、
2^k * n ≡ n (mod c)
です。n と c が最大公約数 g をもつ場合には、n = g * a、c = g * d なので、先ほどの合同式は、
2^k * a ≡ a (mod d)
になります。ここで、a と d とは互いに素です。したがって、
2^k ≡ 1 (mod d)
となり、#26155の定義より、k = ord2(d) です。
ここで見方を変えると、c の約数 d を考え、d より小さくて互いに素な a をとってきたときに、n = a * c/d がループ上にある条件が、
2^k * a ≡ a (mod d)
といえます。この式は、a, 2 * a, 2^2 * a, ..., 2^(k-1) * a が同じ式を満たすことを意味しています。
a の個数は、φ(d) 個ですが、上式を満たす a は k 個だけ重複している、つまり、対応する n が同じループ上にあるので、
φ(d)/k = φ(d)/ord2(d) が d に対するループの個数になります。したがって、
全体のループの個数 = ��[d|c]{φ(d)/ord2(d)}
になります。これが、証明すべき式でした。
なお、実際に一つのループ上にある数の個数は、少なくとも偶数に関しては、k といえます。
これは、k は、操作 C' の言葉で言うと、ループの中で 2 をかける回数、操作 C の言葉で言うと、ループの中で 2 で割る回数、だからです。
奇数は、2 をかけていって何回 d を超えるかに対応します。ただ、この定式化はまだよく分かりません。

例を考えてみます。

c = 11 の場合：2^k * n ≡ n (mod 11)
11 は素数なので、対応する方程式は、
2^k ≡ 1 (mod 1), 2^k ≡ 1 (mod 11)
前者は無意味ですが ord2 の定義より ord2(1) = 1、後者は ord2(11) = k = 10 です。
前者は、11 -> 22 -> 11 に対応し、後者は、3 を含むループに対応します。これは、
d = 1 :
2^k * 11 ≡ 11 (mod 11)
11 22
d = 11 :
2^k * 1 ≡ 1 (mod 11)
1 2 4 8 16 5 10 20 9 18 7 14 3 6 12 1
から分かります。
なお、
2^k * a ≡ a (mod 11), a = 2, ..., 10
は、既に、1 の系列で出現していますが、これは、k = 10 の重複を意味しています。

c = 15 の場合：2^k * n ≡ n (mod 15)
15 = 3 * 5 なので、
2^k ≡ 1 (mod 1), 2^k ≡ 1 (mod 3), 2^k ≡ 1 (mod 5), 2^k ≡ 1 (mod 15)
ord2 = 1, 2, 4, 4
ループの個数 = 1/1 + 2/2 + 4/4 + 8/4 = 5
具体的には、
d = 1 :
2^k * 15 ≡ 15 (mod 15)
15 30
d = 3 :
2^k * 5 ≡ 5 (mod 15)
5 10 20 5
2^k * 10 ≡ 10 (mod 15)
5 の系列で既に出現！
d = 5 :
2^k * 3 ≡ 3 (mod 15)
3 6 12 24 9 18 3
2^k * 6 ≡ 6 (mod 15)
3 の系列で既に出現！
2^k * 12 ≡ 12 (mod 15)
3 の系列で既に出現！
2^k * 9 ≡ 9 (mod 15)
3 の系列で既に出現！
d = 15 :
2^k * 1 ≡ 1 (mod 15)
1 2 4 8 16 1
2^k * 2 ≡ 2 (mod 15)
1 の系列で既に出現！
2^k * 4 ≡ 4 (mod 15)
1 の系列で既に出現！
2^k * 8 ≡ 8 (mod 15)
1 の系列で既に出現！
2^k * 7 ≡ 7 (mod 15)
7 14 28 13 26 11 22 7
2^k * 14 ≡ 14 (mod 15)
7 の系列で既に出現！
2^k * 13 ≡ 13 (mod 15)
7 の系列で既に出現！
2^k * 11 ≡ 11 (mod 15)
7 の系列で既に出現！
この例は、恐らく、状況を理解するのによい例だと思います。
ネコの住む家　　 11月13日（日） 21:14:14　　 MAIL:uchi@sco.bekkoame.ne.jp 　　26160
スモークマン
#26160
uchinyam さんの理論と比べたら雲泥の差ですが。。。（まだよく理解できてない。。。）
非常にプリミティブな解法を・・・

nが偶数のとき、
n=<22
nが奇数のとき、
n=<11
nが偶数のとき、
n=m/2
つまり、mが2~22まで存在すれば、奇数nは1~11まで存在する。
確かに鳩ノ巣原理で、11+6=17から、１６回の操作を行い出てくる数を考えて見ればよい。それ以下の回数なら、同じ数字が出てるはずだから。
つまり、 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 の偶数nが最初の数なら、
1回目、 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
2回目、 12, 1, 14, 2, 16, 3, 18, 4, 20, 5, 22
3回目、 6, 12, 7, 1, 8, 14, 9, 2, 10, 16, 11
4回目、 3, 6, 18, 12, 4, 7, 20, 1, 5, 8, 22
5回目、 14, 3, 9, 6, 2, 18, 10, 12, 16, 4, 11
6回目、 7, 14, 20, 3, 1, 9, 5, 6, 8, 2, 22
7回目、 18, 7, 10, 14, 12, 20, 16, 3, 4, 1, 11
8回目、 9, 18, 5, 7, 6, 10, 8, 14, 2, 12, 22
9回目、 20, 9, 16, 18, 3, 5, 4, 7, 1, 6, 11
10回目、10, 20, 8, 9, 14, 16, 2, 18, 12, 3, 22
11回目、 5, 10, 4, 20, 7, 8, 1, 9, 6, 14, 11
12回目、16, 5, 2, 10, 18, 4, 12, 20, 3, 7, 22
13回目、 8, 16, 1, 5, 9, 2, 6, 10, 14, 18, 11
14回目、 4, 8, 12, 16, 20, 1, 3, 5, 7, 9, 22
15回目、 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 11
16回目、 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22
これで、1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,22 のすべてが出てることが分かる。

cが大きいと、計算で確かめるのは無理な方法だ〜
その点、uchinyan さんは、理詰めで証明されてるからすごい！
金光　　 11月14日（月） 18:36:30　　 MAIL:kennji72001@yahoo.co.jp 　　26161
スモークマン
＜追加説明＞
↓同じ数が、同列に最低２回出てるってことが言いたかったんです。
金光＠岡山　　 11月14日（月） 20:58:40　　 MAIL:kennji72001@yahoo.co.jp 　　26162

過去問題一覧へ戻る