素数と基数。国語脳と数学脳。

締切済

質問者：菱菱菱
質問日時：2021/08/14 05:41
回答数：2件

十進法表記だと素数は、
2 3 5 7 11 13 17 19 ...
九進法表記では、
2 3 5 7 12 14 18 21 ...

九進法表記では直感的な素数判定が著しく困難に感じるのですが、
これは単に慣れの問題なのか、それとも十進数がもつ特徴なのでしょうか？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (2件)

最新から表示
回答順に表示

No.2

回答者： windwald
回答日時：2021/08/14 10:32

後者の影響はあるでしょうが、基本的には前者でしょう。

ずっと十進法で計算などをしてきた経験の蓄積があるので、37が素数で39が合成数というのはぱっと判断が出来るのです。これには九九の暗唱の影響は大きいと思います。九九から外れていくと人によっては 71 や 91 あたりでも直感的判定が思いっきり外れてくるでしょうし、713 が素数か合成数か、咄嗟の判断はしにくいと思います。。
ですので普段から九進法で数を書き表し計算もしていればおそらく「十進法では直感的な素数判定が著しく困難だ」と感じることでしょう。

十進法では10の素因数が2と5なので、2の倍数(末尾が0,2,4,6,8)と5の倍数(末尾が0,5)は除外できます。
普段から十進数で数を扱うことでこういう特徴を知らず知らずに身につけています。

九進法だと、合成数であると即座に除外できるのは、9の倍数を別にすれば、3の倍数(末尾が0,3,6)だけです。これは9の素因数に3だけしか無いことが理由です
つまり末尾の数を見るだけで合成数と判断できる割合が九進数では3/9=1/3、十進数では6/10=3/5と、十進数のほうが多く除外できます。

またn進法においては、n-1およびその素因数の倍数であるかどうかはかんたんな方法で判断できます。
・n進法で表されたある数の各位の合計がn-1の倍数であれば、ある数はn-1の倍数
・n進法で表されたある数の各位の合計がn-1の素因数kの倍数であれば、ある数はkの倍数
これは、十進法について言うと、
・ある数の各位の合計が9の倍数であれば、ある数は9の倍数
・ある数の各位の合計が3の倍数であれば、ある数は3の倍数
となります。
これも即座に除外できるとすると十進法は全体22/30=11/15≒73%が除外されます。

では除外されるモノが多ければ良いのかというと、
六進法では末尾で2および3の倍数が判定でき、各位の合計で5の倍数が判定できるので十進法と同じく22/30≒73%が除外されますが、
六進法において素数の列記
　2 3 5 11 15 21 25 31 35 45 51 101 105 111……
と、これも咄嗟の判断が難しくなりませんか？

よって十進法の特徴ではあるが、慣れの影響は大きいと判断します。