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

TarZの日記: 「ぱっと見素数」 9

日記 by TarZ

91のような「パッと見で素数に見えちゃう数」には五つの条件がある

 これは10進数限定か。例えば 8進数では 91 は 0o133 なので、1+3+3=7 より 7 で割り切れると判る(もちろん、7進数とか13進数なら自明)。

 基数を限定しない「ぱっと見素数」は、カーマイケル数みたいなのが該当するかな。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by manmos (29892) on 2016年12月13日 18時25分 (#3129331) 日記

    N進数で各桁足して(N-1)の倍数になったら N-1で割れるってのは案外知られてない。

    まあ91は7x13っていうそこそこレベル高めの合成数ってとこが10進数2桁の合成数では最強の"Glance Prime"ですね。

    ちなみに、車のナンバーを8191にしようかと思って、「なんで」って聞かれて「4桁最大のメルセンヌ素数」って答えたのは私。

    #結局小さいメルセンヌ素数で収まった。掛布の背番号だし。まあ31は悪くない。13も331も3331も素数だし。

    • by TarZ (28055) on 2016年12月14日 19時05分 (#3130025) 日記

       10進数以外の場合、直感的な素数判定の(10進数における)暗黙のルールがいろいろと崩れてくるので注意が必要ですよね。

       「10の倍数、5の倍数が10進数ならすぐに判定できるが、他の基数では成り立つとは限らない」点はわりと直感的に理解できますが、偶数か奇数の判定すらも基数が偶数でなければ自明ではない、なんてのは見落としがち。(3進数での偶数は、2, 11, 20, 22, 31, ... 。各桁の数字を足して2の倍数なら偶数)

      ちなみに、車のナンバーを8191にしようかと思って、「なんで」って聞かれて「4桁最大のメルセンヌ素数」って答えたのは私。

       これいいですね。2^nは馴染みがあるのですが、クルマのナンバーに使うとすると、ちょっとありきたりすぎる面もある。ちょっとひねるとすると 2^n-1 で、メルセンヌ素数みたいな数だと適度にヒネってあって、ぱっと見だと分らずいい感じです。

       1729 だとヒネりすぎ。

      親コメント
  • by yasuchiyo (11756) on 2016年12月13日 19時28分 (#3129371) 日記

    > 素数大富豪初心者がまず覚えるべきなのは100以下の素数です。
    この5条件を意識できる人なら、後付けで出てきてる各桁の和で3の倍数を見つけられることくらい知ってるんじゃないかなぁ。
    で、そこまで頭が回るんなら、九九で末尾が1になるのは3×7(順不同)か9×9しかないので(1×1とか言うなよ)、二ケタ範囲なら

    91=21+70

    はすぐに気付きそうなんですけど。

    • by shibuya (17159) on 2016年12月13日 19時54分 (#3129393) 日記

      91=21+70

      はすぐに気付きそうなんですけど。

      ですよねえ。
      「こういうときは、素数を数えるんだ!」
      という場面にたびたび遭遇して何度もこなしてますよねえ。

      親コメント
      • by Anonymous Coward

        3桁到達を目の前に断念するケースが多いのではないでしょうか。
        それに、訓練ばかりでは気が抜けますよね。実戦、はよ。

    • by Anonymous Coward on 2016年12月13日 22時32分 (#3129483)

      ていうかnが素数でないなら、nの1でない約数の少なくとも1つは√n以下なんだから、2桁(100未満)の数だったら2、3、5、7で割れば済む。2、5は一瞬でわかるし3もよく知られた方法があるから、実質7で割ってみればいいだけ。

      親コメント
    • by Anonymous Coward

      でも割と気づきづらい方じゃないですかね。下から割っていっても遅めだし。
      その辺の判定は感覚の問題ですしね。
      記事は納得できると感じました。

      自分は91=7*13ってのは知らずに覚えていたみたいで割とすんなり出てきました。
      3で割れるかは足して3で割るよりは実際に割る。そして素数か怪しい時に最初にやるのはこれですね。

      • by Anonymous Coward
        割とアレ?って思う数字ではあるよね。
        10秒あれば間違えないが、早押しで答えろって言われたら間違えそう。
typodupeerror

アレゲは一日にしてならず -- アレゲ研究家

読み込み中...