パスワードを忘れた? アカウント作成
504705 journal

airheadの日記: memo: 101

日記 by airhead

(2008/11/12 00:30 Binary 2008より、鴨志田さんの出題とその答えを読んで / 関連エントリ

...なるほど、そういうことか。確かに1010...1(4n+1桁、nは1以上の整数、「1」の個数は2n+1)は素数ではなく、全ての桁が「1」である2n+1桁の数を約数に持つ。

「p進数(pは2以上の整数)」が関係するのは、前出の2n+1桁の数で割って得られる約数。2進数の「1」、8進数の「7」、10進数の「9」、16進数の「F」などのような、p進数の表記に用いられる最大の数字を仮に「Z」とすると、

               1 =          1 * (         1)
           10101 =        111 * (    Z0 + 1)
       101010101 =      11111 * (  Z0Z0 + 1)
   1010101010101 =    1111111 * (Z0Z0Z0 + 1)
                 :

となる(n=0の場合の1=1*1はもちろん素数ではないが、参考として最上段に併記した)。例として16進数 1111111 と F0F0F1 の乗算を見てみよう。

        1111111
*        F0F0F1
---------------
        1111111
       FFFFFFF
     FFFFFFF
+  FFFFFFF
---------------
        1010101
       FFFFFFF
             1
     FFFFFFF
           1
   FFFFFFF
+        1
---------------
        1010101
      10000000
    10000000
+ 10000000
---------------
= 1010101010101

これは、何進数であろうとも、「1」が奇数個という条件においてなら何桁に増えようとも成り立つ。ここに素数はない。

また回答(a)にある通り、何進数であろうとも、「1」が偶数個なら「101」「101 0101」「101 01010 ... 0101」となるわけで、「101」で割り切れるのは明らかだ。

というわけで、素数の可能性はp進数101(=p2+1)にしかない(さらに言えば、pが奇数の場合にはp2+1が偶数になってしまうので、奇数進数の1010...1に素数はない)。

typodupeerror

長期的な見通しやビジョンはあえて持たないようにしてる -- Linus Torvalds

読み込み中...