|
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 |