MarriageTheoremさんの2929問題に答えてみる

ちょっとした問題 - 出題編
http://d.hatena.ne.jp/MarriageTheorem/20100109/1262963130

回答編も書かれているとのことですが，とりあえず見ずに回答してみる．
昼休み考えて，さっき内職して書いてみた．

■問題1
（難易度：ふつう） 29292929・・・と、「29」をいくつか繋げてできる数を
考えます。この数が29の二乗の倍数になることはあるでしょうか？
もしあるとしたら、そのような最も小さい数は、「29」をいくつ繋げた数でしょうか？

29を10進数としてn個並べた数字は
29 * Σ(i=1,...,n)100^(i-1) で表現できる．

29^2で割り切れるためには
Σ(i=1,...,n)100^(i-1) が 29 で割り切れればOK

100 mod 29 = 21 なので
Σ(i=1,...,n)100^(i-1) =
1 + 100 + 10^4 + ... = 1 + g + g^2 + ... where g = 21
が 29 で割れるnを求める問題であることがわかる．

g の位数が何かを考えたい，なぜなら，もし g^k = -1 mod 29 であれば
1 + g + g^2 +... + g^k + g^(k+1) + g^(2k-1) =
{1 + g + g^2 +... + g(k-1)} + (-1){1 + g + g^2 +... + g(k-1)} = 0 mod 29

実際 21^7 mod 29 = -1 なので 14個並べればOKとわかる．
ただ，k<7 で {1 + g + g^2 +... + g(k-1)} が 0 となるケースがあるかチェック
するしかない． 21^7 mod 29の計算も含め手計算でそれは無いことを確認

■問題2
（難易度：そこそこ難しい） 素数pについて、pを（10進数表記して）
k個繋げてできる数（kは正整数）をN(p,k)と書くことにします。
例えばN(5,3) = 555、N(29,2) = 2929です。このとき、「N(p,k)がpの二乗の倍数となる最小のkの値はk=pである」・・・（＊）という条件を
満たす2桁以内の素数pは全部でいくつあるでしょう？

pが2桁のケースは問題1が問題2を解く上での実値になっている．
g = 100 mod p とおいたとき g = 1 のときだけ満たす．
なぜなら g^k = -1 mod p になると問題1のようなケースに帰着してしまうから．

2桁の素数をすべてチェックするのは面倒のように見えるけど50以上はないよね．
11,13,17,19,23,29,31,37,41,43,47 は大きい順につぶしてみる．
すると mod 11 で g=1となるので2桁では11のみ．

pが1桁(p=2,3,5,7)のケースは g = 10 mod p で考えればよい．これは3のみ．

答え：3,11 の2個だけ．

■問題3
（難易度：けっこう難しい） 同様に、今年は平成22年ということで
条件（＊）を満たす22桁以内の素数pは全部でいくつあるでしょう？

d桁のときに g = 100^(d-1) mod p が 1になるときを探す問題
→ 100^(d-1) -1 が p で割り切れる問題に．

d=3のとき 9999 = 3^2 * 1111 = 3^2 * 11 * 101 なので3桁になる素数は
101,303,909 の3ケースのみ．

d=4のとき 999999 = 3^2 * 111111 = 3^2 * 111 * 1001 = 3^3 * 37 * 1001 =
3^3 * 37 * 7 * 11 * 13 なので
満たす素数は無し

d=5のとき 99999999 = 3^2 * 11111111 = 3^2 * 1111 * 10001
10001 が素数かどうか知らないので "手計算でやるの" 終了...

糸冬 もうやだこの問題...

少なくとも 10^d + 1 が素数かどうかに帰着することがわかった．
@factoring_bot たんにさっき調べてもらったら d=5,6,7 のときに該当する
ものは無いことが判明．