TarZの日記: 「ぱっと見素数」 9
日記 by
TarZ
91のような「パッと見で素数に見えちゃう数」には五つの条件がある
これは10進数限定か。例えば 8進数では 91 は 0o133 なので、1+3+3=7 より 7 で割り切れると判る(もちろん、7進数とか13進数なら自明)。
基数を限定しない「ぱっと見素数」は、カーマイケル数みたいなのが該当するかな。
91のような「パッと見で素数に見えちゃう数」には五つの条件がある
これは10進数限定か。例えば 8進数では 91 は 0o133 なので、1+3+3=7 より 7 で割り切れると判る(もちろん、7進数とか13進数なら自明)。
基数を限定しない「ぱっと見素数」は、カーマイケル数みたいなのが該当するかな。
アレゲは一日にしてならず -- アレゲ研究家
N進数 (スコア:2)
N進数で各桁足して(N-1)の倍数になったら N-1で割れるってのは案外知られてない。
まあ91は7x13っていうそこそこレベル高めの合成数ってとこが10進数2桁の合成数では最強の"Glance Prime"ですね。
ちなみに、車のナンバーを8191にしようかと思って、「なんで」って聞かれて「4桁最大のメルセンヌ素数」って答えたのは私。
#結局小さいメルセンヌ素数で収まった。掛布の背番号だし。まあ31は悪くない。13も331も3331も素数だし。
Re:N進数 (スコア:2)
10進数以外の場合、直感的な素数判定の(10進数における)暗黙のルールがいろいろと崩れてくるので注意が必要ですよね。
「10の倍数、5の倍数が10進数ならすぐに判定できるが、他の基数では成り立つとは限らない」点はわりと直感的に理解できますが、偶数か奇数の判定すらも基数が偶数でなければ自明ではない、なんてのは見落としがち。(3進数での偶数は、2, 11, 20, 22, 31, ... 。各桁の数字を足して2の倍数なら偶数)
これいいですね。2^nは馴染みがあるのですが、クルマのナンバーに使うとすると、ちょっとありきたりすぎる面もある。ちょっとひねるとすると 2^n-1 で、メルセンヌ素数みたいな数だと適度にヒネってあって、ぱっと見だと分らずいい感じです。
1729 だとヒネりすぎ。
二ケタ範囲内だと (スコア:1)
> 素数大富豪初心者がまず覚えるべきなのは100以下の素数です。
この5条件を意識できる人なら、後付けで出てきてる各桁の和で3の倍数を見つけられることくらい知ってるんじゃないかなぁ。
で、そこまで頭が回るんなら、九九で末尾が1になるのは3×7(順不同)か9×9しかないので(1×1とか言うなよ)、二ケタ範囲なら
91=21+70
はすぐに気付きそうなんですけど。
Re:二ケタ範囲内だと (スコア:1)
91=21+70
はすぐに気付きそうなんですけど。
ですよねえ。
「こういうときは、素数を数えるんだ!」
という場面にたびたび遭遇して何度もこなしてますよねえ。
ぱっと見素敵 (スコア:0)
3桁到達を目の前に断念するケースが多いのではないでしょうか。
それに、訓練ばかりでは気が抜けますよね。実戦、はよ。
Re:二ケタ範囲内だと (スコア:1)
ていうかnが素数でないなら、nの1でない約数の少なくとも1つは√n以下なんだから、2桁(100未満)の数だったら2、3、5、7で割れば済む。2、5は一瞬でわかるし3もよく知られた方法があるから、実質7で割ってみればいいだけ。
Re:二ケタ範囲内だと (スコア:2)
7x11 = 77 はすぐわかるので、7x13 = 91 だけ暗記しちゃえばいい感じもしますね。
Re: (スコア:0)
でも割と気づきづらい方じゃないですかね。下から割っていっても遅めだし。
その辺の判定は感覚の問題ですしね。
記事は納得できると感じました。
自分は91=7*13ってのは知らずに覚えていたみたいで割とすんなり出てきました。
3で割れるかは足して3で割るよりは実際に割る。そして素数か怪しい時に最初にやるのはこれですね。
Re: (スコア:0)
10秒あれば間違えないが、早押しで答えろって言われたら間違えそう。