メモ(数論1): 暗算で素数表 - Project P

チラ裏 > 数論 > メモ1

チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

プッチ神父は、素数を数えるとき383を抜かした。この種の過不足防止には、素数番号が役立つ。

***

2021-11-21 【150法】コンウェイの秘技【3~4桁の数を暗算で因数分解】

2の倍数・3の倍数・5の倍数は明らか。7の倍数以降の判別法もあるにはあるけど(それ自体としては面白いけど)、実用上は「実際に割ってみた方が手っ取り早い」という感じがする。ところが…

Conway は、7の倍数~19の倍数を一気に検出するすごい裏技を編み出していた!

ただし、合成数倍については、個別に考えない。例えば、15で割り切れるかどうかを判定するには「5の倍数かどうか」を考え、イエスなら「3の倍数かどうか」と考えればいい。

【1】 説明のための例として、x = 209 を分解してみよう。

まず150のN倍で x を近似する。この場合、N=1、つまり150自体で近似すると、誤差は59。

手のひらを広げて「1回引いたら深呼吸」と言いながら、59からNを引く。手のひらの上に58をイメージする。

「親、行く」と言いながら、親指を見て、またNを引いた57をイメージする。親指を折り曲げる。

「ひどいな」と言いながら、人差し指を見て、またNを引いた56をイメージする。

「仲いいな」と言いながら、中指を見て、またNを引いた55をイメージする。中指を半分折り曲げる。

「くっさい」と言いながら、薬指を見て、またNを引いた54をイメージする。

最後に「恋さ」と言いながら、小指を見て、またNを引いた53をイメージする。

親指が曲がって、中指が半分曲がっている。これで 209 が 19 と 11 で割れることが判明。実際 209 = 19 × 11。

何をやってるのかというと…。「親、行く」は「親指イク=19」。57が19で割れるか考える。商3で割り切れるので、イエス。記録として、親指を折り曲げておく。

「ひどいな」は「人差し指イナ=17」。このステップでは、56が17で割れるか考える。ノー。

「仲いいな」は「中指イイ・ナ=11と7」。このステップでは、55が11または7で割れるか考える。イエス、11で割れる。記録として、中指を半分折り曲げておく。

「くっさい」は「薬指サイ=31」。このステップでは、54が31で割れるかチェック。ノー。

「恋さ」は「小指イサ=13」。このステップでは、53が13で割れるかチェック。ノー。

この方法で、7~19の素因数は、漏れなく検出される(31も検出される)。

【2】 別の例、x = 533。

N=3 とする。450を引いて83。以下、繰り返しNを引く。

1回引いたら深呼吸 → 手のひらの上に80がある。

親指  親)いく → 77÷19。割り切れない。

人差し指  ひど)いな → 74÷17。割り切れない。

中指  仲)いいな → 71÷11 と 71÷7 を考える。割り切れない。

薬指  くっ)さい → 68÷31。割り切れない。

小指  こ)いさ → 65÷13。商5で割り切れる。小指を曲げておく。

結論として 533 は 13 で割り切れる。13 の 2 倍は 26、そのまた 2 倍は 52 なので、13 の 40 倍は 520。それに留意しつつ暗算で割り算すると、商41。この商は素数なので、533 = 13 × 41 は素因数分解。

【3】 逆方向に、足しながらやってもいい。x = 1023。N=7 として、1050 に切り上げた方が誤差が小さい。差は27。(この x は一目で3の倍数だが、説明の例として、構わず進める。)

1回足したら深呼吸 → 手のひらの上に34がある。今度はNを繰り返し足す。

親)いく → 41÷19。割り切れない。

ひど)いな → 48÷17。割り切れない。

仲)いいな → 55÷11 と 55÷7 を考える。11で割り切れるので、中指を半分曲げておく。

くっ)さい → 62÷31。これも割り切れるので、薬指を曲げておく。

こ)いさ → 69÷13。割り切れない。

結論として x = 1023 は 11 と 31 で割り切れる。31 × 11 = 310 + 31 = 341。x が 3 で割れることは最初から分かってるので 1023 = 3 × 11 × 31 となる。

参考として、最初と同じ引き算方向でやると N = 6。900を引いて差は123。

1回引いたら深呼吸 → 117。

親)いく → 111÷19。割り切れない。

ひど)いな → 105÷17。割り切れない。

仲)いいな → 99÷11 と 99÷7 を考える。11で割り切れるので、中指を半分曲げておく。

くっ)さい → 93÷31。これも割り切れるので、薬指を曲げておく。

こ)いさ → 87÷13。割り切れない。

ちゃんと同じ結論になった!

【4】 この方法でなぜうまくいくのかの説明、さらに拡張する方法については、次の文献をごらんください。
Arthur T. Benjamin: Factoring Numbers with Conway’s 150 Method
https://math.hmc.edu/benjamin/wp-content/uploads/sites/5/2019/06/Factoring-Numbers-with-Conway%E2%80%99s-150-Method.pdf

この方法の注意点として、因数が見つからないことの方が多いです。例題では、説明のため因数があるケースを取り上げましたが、整数が7で割れる確率は単純計算で1/7、11で割れる確率は1/11等々なので、各因数が見つかる確率は比較的小さく、3回に2回くらいは7~19の因数が一つも出ないでしょう。ヒットしなくてもがっかりせず、「それで当たり前」「その範囲の因数がないことを確定判定できた!」と肯定的に考える心構えが重要かと。順次引き算または足し算する数 N は、状況によって変わるので、単純な計算ミスに注意すること。指との「同期」がずれると正しく判定できないので、落ち着いて「1回引いたら(足したら)深呼吸」をやること。中指は 7 と 11 の2種類の因数に対応するので、混乱しないように、7 だったら軽く曲げ、11 だったら半分曲げ、7 × 11 だったら思い切り曲げるといいかも。

この方法は、Conway が1996年にイベントで披露したものだそうです。Benjamin は直接それを見聞きして、2018年に上記の記事を書いたようです。The author thanks the referee for many helpful suggestions, and especially wishes to thank John Conway for his permission to share his algorithm... までは普通の結びですが、続けて ...and for being such a large prime factor in the mathematics community. とうまいことを…。Benjamin の書いた文章のことは、インドの RESONANCE 2021年5月号で知りました。Arvind Ayyer と B. Sury の「John Horton Conway: The Magical Genius Who Loved Games」の末尾でチラッと言及されていたのです。
https://www.ias.ac.in/article/fulltext/reso/026/05/0595-0601
雰囲気的には、楕円曲線法で分解を試みるときの Baby Steps に似てる。こういうことを知るたび、世の中にはすごいことを考える人がいるもんだな~とびっくり!

理解できないような難しい研究をする学者がいるのは普通に分かるけど、簡単な算数みたいなことでも、すごいことができるんだなぁ…

(コメント) 検索エンジンで「素因数分解の技法」のようなキーワードを使っても、ベンジャミンの論文は出てこないだろう。巨大検索エンジンからは見えないことが、小さな趣味のサイトからはピンポイントでリンクできる。この現象は、脱中心の重要性を示唆しているのではないか?

⁂

2021-12-11 11で割り切れるかの判定法

【1】 3桁の数(例: ‌143)について、左端の数と右端の数の和(例: 1 + 3)が真ん中の数(例: 4)に等しい場合、その3桁の数は 11 で割り切れる。
  実際、143 = 110 + 33 = 11 × 10 + 11 × 3 = 11 × 13

この判定法を使うと、121 も 187 も 253 も、一瞬で 11 の倍数と分かる。11 の倍数だと分かれば、簡単に暗算で分解できる:
  121 = 110 + 11 とか 187 = 110 + 77 とか 253 = 220 + 33 と考えればいい…

このうち、平方数 121 = 112 は、よく登場するので、見覚えがあるかもしれない。

【2】 【1】のパターンについては、「両端の数の和、マイナス、真ん中の数」がゼロと言い換えることができる。
  例: 187 両端の数の和は 1 + 7 = 8 で、真ん中の数は 8 → 8 − 8 = 0 → 187 は 11 の倍数
  例: 253 両端の数の和は 2 + 3 = 5 で、真ん中の数は 5 → 5 − 5 = 0 → 253 は 11 の倍数

「両端の数の和、マイナス、真ん中の数」が 11 の場合にも、その3桁の数は 11 で割り切れる。
  例: 319 両端の数の和は 3 + 9 = 12 で、真ん中の数は 1 → 12 − 1 = 11 → 319 は 11 の倍数
  例: 209 両端の数の和は 2 + 9 = 11 で、真ん中の数は 0 → 11 − 0 = 11 → 209 は 11 の倍数

実際に 11 で割ってみなくても、100の位の数字と1の位の数字を足して、10の位の数字と比較するだけで、11の倍数かどうか分かる。何の役に立つかはともかく、ちょっと面白い。

このことから、407 や 517 や 539 も一瞬で 11 の倍数と分かる。このパターンについても【1】と同様、筆算の割り算と同様のことを暗算でできる。
  319 = 220 + 99 = 11 × 20 + 11 × 9 = 11 × 29
急いでる場合、末尾が 9 なら 11 を足した方が簡単に計算できることがある:
  319 + 11 = 330 = 11 × 30 だから 319 = 11 × 29
  (前半で 11 を 1 個、貸したので、後半で 11 を 1 個、返してもらう)

同様に、末尾が 7 なら 33 を足してもいい:
  407 + 33 = 440 = 11 × 40 だから 407 = 11 × 37
  (前半で 11 を 3 個、貸したので、後半で 11 を 3 個、返してもらう)

【3】 2の倍数と5の倍数は、一目で分かる。桁数が少なければ、各桁の数字を足してみることで、3の倍数も一瞬で分かる。それ以外の場合(つまり3 でも 5 でも割り切れない奇数の場合)、一般には、素数か合成数かの判定は難しい。

けれど、3桁の数については、11で割れるか割れないかは、「両端の数を足して、真ん中の数を引く」という簡単な計算で確認できる。

偶数と5の倍数を除外すると、3桁の 11 の倍数は、次の4系列、各8個に整理される:
  11 × 11 + 110k 型 121, 231*, 341, 451, 561*, 671, 781, 891*
  11 × 13 + 110k 型 143, 253, 363*, 473, 583, 693*, 803, 913
  11 × 17 + 110k 型 187, 297*, 407, 517, 627*, 737, 847, 957*
  11 × 19 + 110k 型 209, 319, 429*, 539, 649, 759*, 869, 979

(各行は、110 ずつ増える等差数列。初項は、それぞれ 121 = 112, 143 = 121 + 22, 187 = 143 + 44, 209 = 187 + 22。)

このうち*印の10個は、一目で3の倍数(3の倍数かの判定では、正直に各桁の数字を全部足さず 3, 6, 9 を無視するといい…例えば 957* については 9 + 5 + 7 ではなく 5 + 7 で判定): 素数かどうか判定したいだけなら、11で割れるかを考える以前に予選落ち。残り22個は、3の倍数ではない。3 で割り切れるかどうかはともかく、【1】【2】によって 11 の倍数を判別できる。

【4】 2桁の数が11の倍数の場合は、ぞろ目なのですぐ分かる(11, 22, 33, 44, 55, 66, 77, 88, 99)。では、4桁以上の数は?

「両端の数を足して、真ん中の数を引く」という3桁の計算を拡張すると、「奇数桁目の数の和から、偶数桁目の数の和を引く」となる:
  例: 1463 奇数桁目の数の和は 4 + 3 = 7 で、偶数桁目の数の和は 1 + 6 = 7 → 7 − 7 = 0 → 1463 は 11 の倍数
  例: 12345 奇数桁目の数の和は 1 + 3 + 5 = 9 で、偶数桁目の数の和は 2 + 4 = 6 → 9 − 6 = 3 → 12345 を 11 で割ると 3 余る

これが成り立つ訳は次の通り。左から a, b, c という3個の数字(0~9のいずれか)を並べた3桁の数は 100a + 10b + c に当たる。
  例: 253 = 100 × 2 + 10 × 5 + 3 つまり a = 2, b = 5, c = 3
ところで 99 は 11 の倍数なので、99a は 11 で割り切れる。だから 100a を 11 で割った余りは、100a − 99a = a を 11 で割った余りに等しい。
  例: 200 を 11 で割った余りは、2 を 11 で割った余り(つまり 2)に等しい。
一方、11b は 11 で割り切れるので、10b を 11 で割った余りは 10b − 11b = −b を 11 で割った余りに等しい。
  例: 50 を 11 で割った余りは、−5 を 11 で割った余りに等しい。−5 を 11 で割ると、商が 0 で余りが −5 とも言えるし、商が −1 で余りが 6 とも言える。
最後に、1桁の数 c を 11 で割った余りは、当然 c 自身。以上を総合すると、100a + 10b + c を 11 で割った余りは、a − b + c に等しい。これは、もともとの3桁の数の両端の桁 a と c を足し合わせて、真ん中の桁 b を引き算することに当たる。

より一般的に、10 ≡ −1 (mod 11) なので、n が偶数のとき、10n ≡ 1。従って、1の位、100の位、1万の位…など(奇数桁目)の数が x だったとすると、10nx を 11 で割った余りは、x を 11 で割った余りに等しい。一方、n が奇数のとき、10n ≡ −1。従って、10の位、1000の位、10万の位…など(偶数桁目)の数が x だったとすると、10nx を 11 で割った余りは、−x を 11 で割った余りに等しい。各桁ごとに発生する余りを全部かき集めると、全体を11で割ったときの余りとなる。最初と逆に、1の位を A、10の位を B、100の位を C…と書くと:
  A + 10B + 102C + 103D + … を 11 で割った余りは
  A − B + C − D + … を 11 で割った余りに等しい。

⁂

2021-12-15 11の倍数の秘密

1で終わる3桁の数は、上位桁に 1→2, 2→3, 3→4 のような「1個上がるパターン」があれば11の倍数:

2で終わる3桁の数は、上位桁に 1→3, 2→4, 3→5 のような「2個上がるパターン」があれば11の倍数:

3で終わる3桁の数は、上位桁に 1→4, 2→5, 3→6 のような「3個上がるパターン」があれば11の倍数:

…以下同様に進めて、7で終わる3桁の数は、上位桁に 1→8, 2→9 という「7個上がるパターン」があれば11の倍数だが、10進法の性質上、真ん中の桁は9より大きくなれない。この場合、その限界に達した後では 4→0, 5→1 のような「4個下がるパターン」に切り替わる:

+7 ≡ −4 (mod 11) なので、2種類のパターンは本質的に同じ。このような切り替わりは、どのパターンでも起こり得る。

8で終わる3桁の数は、上位桁に 1→9 という「8個上がるパターン」があれば11の倍数だが、その先では「3個下がるパターン」に切り替わる:

9で終わる3桁の数については、「9個上がるパターン」はもともと無理なので、もし11の倍数なら、上位桁に 2→0, 3→1, 4→2 のような「2個下がるパターン」が現れる:

一般に、最下位桁が N のとき、上位桁が「N 個上がる」か「11−N 個下がる」なら、それは11の倍数。

この性質は部分的には、4桁の数にも拡張可能。

11の倍数の判定法自体は簡単だけど、こういうパターンがあるんだなぁ…ということを心の片隅にとどめておくと、11の倍数の「におい」が何となく感じられるかもしれない。

⁂

2021-12-12 7で割り切れるかの判定法

7の倍数の判定法はいろいろあって、どれも面白い。今回はその一つを検討したい。この方法が最善かどうかはケースバイケースだが、やり方は単純明快。

【1】 基礎となる操作は、与えられた自然数を「右端」(末尾の桁)と「残り」(末尾の桁以外の部分)に切り分けること。例えば:
  203 → 「右端」は 3 で「残り」は 20
  456 → 「右端」は 6 で「残り」は 45
  91 → 「右端」は 1 で「残り」は 9

計算としては、「右端」の2倍を「残り」から引く。例えば:
  203 → 20 − 6 = 14
  456 → 45 − 12 = 33
  91 → 9 − 2 = 7

結果が7の倍数になったら、もともとの数も7の倍数; 結果が7の倍数にならなければ、もともとの数も7の倍数ではない。上の例では:
  203 と 91 は7の倍数;
  456 は7の倍数ではない。

【2】 必要ならこの方法を反復適用すると、通常1回ごとに1桁短くなり、やがて容易に判定できる小さな数にたどり着く。例えば 1234 は 7 で割り切れるだろうか?
  1234 → 「右端」が 4、「残り」が 123 → 123 − 8 = 115
この数 115 が7で割り切れるかどうか、直接割り算してもいいのだが、115 に再び同じ判定法を適用すると:
  115 → 「右端」が 5、「残り」が 11 → 11 − 10 = 1 → 7の倍数でない

実は、この方法にはいろいろと高速化の余地がある。以下、文献には載っていないようなショートカットを紹介するが、全部オプション。「計算を省力化するためには、場合分けの手間が発生する」というトレードオフがある。複雑なことを考えたくない場合、基本モードだけを使う方がいいだろう。
☆ 基本モード 右端が何であれ、その2倍を残りから引く。

【3】 ショートカット1 右端が 0 または 7 のときは、問答無用でその数を消していい。例えば:
  427 → 基本モードでは 42 − 14 = 28 → 7の倍数
  427 → 右端を消して 42 → 7の倍数
  3907 → 右端を消して 390 → 右端を消して 39 → 7の倍数でない

ショートカット1が成り立つ理由: 10A + 0 または 10A + 7 が 7 で割り切れるかどうかは、A が 7 で割り切れるかどうかと同じ。ここで 0 または 7 は「右端」に当たり、A は「残り」に当たる。

同様の理由から、下2桁・下3桁などが7の倍数だったら、その部分を問答無用で消していい。例えば「21 は7の倍数」「43 は7の倍数でない」ということが一目で分かるなら、「4321 は7で割り切れない」ということも一目で分かる。4321 の 21 を消して、43 で判定できるから。

左端の1桁・2桁・3桁などが7の倍数だったら、その部分も問答無用で消していい。例えば…
  219 → 21 は7の倍数なので消す → 9 は7の倍数ではない
  766 → 7 は7の倍数なので消す → 66 は7の倍数ではない
  3591 → 35 は7の倍数なので消す → 91 は7の倍数

【4】 ショートカット2 右端が 8 以上のときは、7 を引いてから判定した方が楽。例えば:
  508 → 基本モードでは 50 − 16 = 34 → 7の倍数でない
  508 → 501 → 50 − 2 = 48 → 7の倍数でない
  119 → 基本モードでは 11 − 18 = −7 → 7の倍数
  119 → 112 → 11 − 4 = 7 → 7の倍数

ショートカット2が成り立つ理由: ある数 n が 7 で割り切れるなら n ± 7 も 7 で割り切れる; n が 7 で割り切れないなら n ± 7 も 7 で割り切れない。…この性質は、以下でも活用される。

【5】 右端が9の場合。基本モードでは 18 を引くことになるが、ショートカット2を使うと、代わりに 4 を引けばいい(上記)。実際には、代わりに 3 を足すとさらに少し楽ができる。例えば:
  119 → 11 − 4 = 7 → 7の倍数
  119 → 11 + 3 = 14 → 7の倍数 この方が少し楽

注目点: 末尾9の数が7の倍数になるためには、「残り」が7の倍数マイナス3であることが必要。言い換えると、「残り」が7の倍数 ± 2の範囲にあるなら、もともとの数は決して7の倍数ではない。感覚がつかめると、多くのケースで、計算自体を全部省略できる。例えば…
  209 → 20 は7の倍数に近いので、209 は7の倍数ではない(判定するまでもない)
  219 → 21 は7の倍数なので、219 は7の倍数ではない(判定するまでもない)
  229 → 22 は7の倍数に近いので、229 は7の倍数ではない(判定するまでもない)

「9で終わる7の倍数」は、次の例のように、右端の 9 を消した「残り」に3を足すと、7の倍数になる:
  49, 119, 189, 259, 329, 399
☆ 高速モード(オプション) 右端が9のときは、それを消して残りに3を足す。

【6】 右端が3の場合。基本モードでは 6 を引くことになるが、ほとんどの場合、代わりに 1 を足した方が楽:
  133 → 13 − 6 = 7 → 7の倍数
  133 → 13 + 1 = 14 → 7の倍数 少し楽
  393 → 39 − 6 = 33 → 7の倍数でない
  393 → 39 + 1 = 40 → 7の倍数でない 少し楽

注目点: 末尾3の数が7の倍数になるためには、「残り」が7の倍数マイナス1であることが必要。言い換えると「残り」が7の倍数と2以上ずれているとき、もともとの数は決して7の倍数ではない。例えば…
  173 → 17 は7の倍数から遠いので、173 は7の倍数ではない(判定するまでもない)
  183 → 18 は7の倍数から遠いので、183 は7の倍数ではない(判定するまでもない)
  193 → 19 は7の倍数から遠いので、193 は7の倍数ではない(判定するまでもない)

「3で終わる7の倍数」は、次の例のように、末尾の 3 を消した「残り」が7の倍数に近い:
  63, 133, 203, 273, 343, 413
☆ 高速モード(オプション) 右端が3のときは、それを消して残りに1を足す。

末尾1の数末尾7の数も重要だが、後者はショートカット1のおかげで、1桁分、易しい。前者も「残り」から2を引くだけなので、判定法の計算は易しい。

とはいえ、計算自体を省略できれば、一番いい。

末尾3の数が7の倍数になるのは「その数プラス7が70の倍数になるとき」に限られる。同様に、末尾7の数が7の倍数になるのは「その数マイナス7が70の倍数になるとき」に限られる。つまり、末尾が3か7の数については、70の倍数のすぐそばでだけ、7で割り切れる可能性を気にすればいい(70の倍数±7)。例えば、210 は 70 の倍数なので 203 と 217 は7の倍数だが、223, 227, 233, 237, 243, 247 などは、判定するまでもなく、7の倍数ではない。

一方、末尾が1か9の数については、7の倍数の出現パターンが比較的分かりにくい(70の倍数±21)。けれど、70の倍数±20の範囲に、このタイプの7の倍数はない。例えば 210 近辺の 199, 201, 209, 211, 219, 221 などは、判定するまでもなく、7の倍数ではない。

【7】 基本モードは「7 × 7 = 49 が10の5倍(つまり50)に近い」という事実を利用したもの。与えられた自然数を n = 10A + B とする(B は右端、A は残り)。もし n が7で割り切れれば 5n も7で割り切れる; n が7で割り切れなければ 5n も7で割り切れない。要するに、n が7で割り切れるかどうかは…
  5n = 50A + 5B
…が7で割り切れるかどうかと一致。ある数が7で割り切れるかどうかという性質は、その数に7の倍数を加減しても変わらない。そこで上記 5n から、7の倍数…
  7(7A + B) = 49A + 7B
…を引き算すると:
  (50A + 5B) − (49A + 7B) = A − 2B
これは「右端」の2倍を「残り」から引いたもの。

この判定法で分かるのは「7で割り切れるかどうか」だけ。割り切れない場合、余りが何なのか、直接知ることはできない(内部的に 5n を7で割った余りを考えている。余りが 0 でないなら、n を7で割った余りとは異なる)。比較として、11の倍数の判定法では、もともとの数を11で割ったときの余りが計算される。

⁂

2021-12-13 7の倍数の形

【1】 前回、「右端の桁を2倍して、残りから引く」という判定法を紹介した:
  例 581 → 58 − 2 = 56 → 7の倍数

上の方法は、シンプルで汎用性が高く、覚えやすい。けれど、逆方向(左端)からの判定法を使った方が便利なことがある。この方法だと、前回の方法と違い、7で割った余りを正しく検出できる。参考までに…

例題1 今日が日曜なら、1000日後は何曜日?
  暗算 1000 → 20 ≡ 6 (mod 7) → 土曜日

例題2 1239 は 7 で割り切れるか?
  暗算 1239 → 239 + 20 = 259 → 59 + 4 = 63 → 7の倍数

やり方は、次の通り。3桁の数を “ABC” とする(A は 100の位、B は 10の位、C は 1の位)。最上位桁 A を 2 倍して “BC” に足す。結果が 7 で割り切れるなら、もともとの数も 7 で割り切れる。結果が 7 で割って r 余るなら、もともとの数もそうなる。

例 329 → 3 を 2 倍して 29 に足す → 29 + 6 = 35 → 7 の倍数

4桁の数を “ABCD” とする。この場合も、最上位桁 A を 2 倍して “BC” に足す。D は計算に関係しないが、結果的に A の 20 倍を “BCD” に足すことに当たる。上の「例題2」参照。

【2】 さて、7の倍数を感覚的に認識するため、よく使う小さい積について、「こんな数だな…」とイメージがあると役立つ。丸暗記する必要はないが、毎回、判定計算をするのも面倒なので…。
  7 × 10 = 70 ← これをベースに…
  7 × 11 = 70 + 7 = 77
  7 × 12 = 70 + 14 = 84
  7 × 13 = 70 + 21 = 91
  7 × 14 = 70 + 28 = 98
  7 × 15 = 70 + 35 = 105
  7 × 16 = 70 + 42 = 112
  7 × 17 = 70 + 49 = 119

91 と 119 は、素数と勘違いされることがある。

豆知識 1と9から成る2~3桁の数のうち、19, 191, 199, 919, 991 は全部素数だが、91 と 119 は合成数。

【3】 重要なのは、7の倍数のうち、末尾が 1, 3, 7, 9 のもの。

それ以外の末尾(偶数や5)、例えば 455 なら、先に2または5で割った方が考えやすい: 例えば 455 ÷ 5 は上記 91 に帰着。

4系統の7の倍数は、次のパターンを持つ。一番易しいのは末尾 7 のケース(70k + 7型)。これは70の倍数プラス7に当たり、筆算方式の暗算でも、7 で割り切れることがすぐ分かる:
  77 = 70 + 7 = 7 × 11
  147* = 140 + 7 = 7 × 21*
  217 = 210* + 7 = 7 × 31
  287 = 280 + 7 = 7 × 41
  357* = 350 + 7 = 7 × 51*
  etc. (*は3の倍数)

同様に、末尾 3 のケース(70k − 7型)は、70の倍数マイナス7に当たる:
  63* = 70 − 7 = 7 × 9*
  133 = 140 − 7 = 7 × 19  チェック 13 − 6 = 7
  203 = 210* − 7 = 7 × 29  チェック 20 − 6 = 14
  273* = 280 − 7 = 7 × 39*  チェック 27 − 6 = 21
  343 = 350 − 7 = 7 × 49 (= 73)  チェック 34 − 6 = 28
  etc.

70k + 7型70k − 7型については、70の倍数±7であることに気付けば、7の倍数であることは分かりやすい。7で割った商も、末尾が1または9に固定され、パターンが明確。

【4】 末尾 1 のケース(21型)は、少し分かりにくい。70の倍数プラス21に当たる:
  21* = 0 + 21* = 7 × 3
  91 = 70 + 21* = 7 × 13  チェック 9 − 2 = 7
  161 = 140 + 21* = 7 × 23  チェック 16 − 2 = 14
  231* = 210* + 21* = 7 × 33*  チェック 23 − 2 = 21
  301 = 280 + 21* = 7 × 43  チェック 30 − 2 = 28
  etc. 7で割った商は末尾3

末尾 9 のケース(49型)は、一番「見えにくい」。70の倍数プラス49(言い換えると、70の倍数マイナス21)に当たる:
  49 = 0 + 49 = 7 × 7
  119 = 70 + 49 = 7 × 17  チェック 11 − 18 = −7
  189* = 140 + 49 = 7 × 27*  チェック 18 − 18 = 0
  259 = 210* + 49 = 7 × 37  チェック 25 − 18 = 7
  329 = 280 + 49 = 7 × 47  チェック 32 − 18 = 14
  etc. 7で割った商は末尾7

3桁の7の倍数は100個以上あって、一つずつ丸暗記するのは実用的でない。でも、鍵となるのは、上記4系統。3の倍数を無視した場合、整数210個につき各2個、トータルでも整数210個につき8個。このくらいのレアさだったら、心の片隅にとどめておいても大した負担にならない。

能動的に記憶するわけではないけど、受動的に「見たら何となくレーダーに反応する」みたいな感じで…

⁂

2021-12-14 200以下の素数は46個 暗算で素数表

7の倍数11の倍数の判定法を使うと、220までの数については、だいたい暗算で素数判定できる。220以下の素数は47個(200以下の素数は46個)。

【0】 12, 14, 16, 18 のように、末尾が偶数の数は2の倍数。10, 15, 20, 25 のように、末尾が0 か 5の数は、5の倍数。だから、10以上の素数を探すとき、末尾が 1, 3, 7, 9 の数だけを考えればいい。

11   13   17   19
21*  23   27*  29
31   33*  37   39*

このうち、*を付けた 21, 27, 33, 39 は3の倍数なので、素数ではない。それらを除外すると:

11   13   17   19
     23        29
31        37      

このように、10~40 の幅30の範囲で、末尾 1, 3, 7, 9; 3, 9; 1, 7 の形の8個(語呂合わせ「意味なくサンキュー人質」)を考えれば、自動的に2の倍数・3の倍数・5の倍数はふるい落とされる。上記8個の数は3で割り切れないので、それらに30の倍数 30, 60, 90 などを足しても、依然として3で割り切れない。逆に、3の倍数に30の倍数を足しても、依然として3の倍数: 突然、素数になる可能性はない。

このことから、「意味なくサンキュー人質」のパターンは、素数候補(2, 3, 5 のどれでも割り切れない)を素早く抜き出すフィルターとして、30周期で繰り返し使える(「車輪」とも呼ばれる)。車輪は、10台(「意味なく」=11, 13, 17, 19)からスタートさせることもできるし、それに30の倍数を加えた任意の数(30の倍数+10: 例えば100 や 250)からスタートさせることもできる。

素数表を作るには、車輪の素数候補から、7の倍数・11の倍数・13の倍数…などの合成数を除外する必要がある。7の倍数といっても 21 = 3 × 7 は、3の倍数として既に除去されているし、35 = 5 × 7 は、5の倍数として既に除去されている。問題になるのは、7 が最小の素因数となる合成数: 49 = 7 × 7, 77 = 7 × 11, 91 = 7 × 13 など。同様に 121 = 11 × 11 以上では、11の倍数もふるう必要があり、169 = 13 × 13 以上では、13の倍数もふるう必要がある。

【1】 1桁の素数は、2, 3, 5, 7 の 4 個

10~40の幅30の領域にある素数は、次の8個:

11  13  17  19  意味なく
    23      29  サンキュー
31      37      人質

40~70の幅30の領域にある素数は、次の8個 −1個。49 = 72 は合成数なので除外される:

41  43  47  49@ 意味なく
    53      59  サンキュー
61      67      人質

70~100の幅30の領域にある素数は、次の8個 −2個。77 = 7 × 11 と 91 = 7 × 13 は除外される:

71  73  77@ 79  意味なく
    83      89  サンキュー
91@     97      人質

100以下の素数は、4 + 8 × 3 − 1 − 2 = 25個。

最下位桁「意味なくサンキュー人質」のパターンは、10以降の整数を30個ずつに区切って、各区間から8個の素数候補を選出するフィルター。このように周期的に使える「ふるい」は「車輪ふるい」と呼ばれる。この車輪ふるいは、偶数・3の倍数・5の倍数を自動的に予選落ちさせてくれる。だから3の倍数などについては一切考える必要なく、当面7の倍数だけに気を付ければいい(49, 77, 91)。

【2】 100~130の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

101  103  107  109  意味なく
     113       119  サンキュー
121       127       人質

121 = 112 は一目で分かるだろう(あるいは11の倍数の判別法=両端の2桁の和が真ん中の桁に等しい)。121 を超えると、最小因子11の合成数が含まれるので、7の倍数と11の倍数を手動でふるう必要がある。

7の倍数のうち、末尾3, 7のものは、70の倍数の近くにしかないし、21型も 70 + 21 = 91 の次は 140 + 21 = 161 なので、この範囲にはないが、49型が怪しい。果たして 70 + 49 = 119 = 7 × 17 は合成数!

覚え方 119番・週七日 (119は緊急用電話番号なので何曜日でも受け付け)

100~130の素数 101, 103, 107, 109; 113; 127

除外された数(2個) 119 = 70 + 49 と 121 = 112

さて、130~160の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

131  133  137  139  意味なく
     143       149  サンキュー
151       157       人質

140の近くなので、140 ± 7 = 133, 147 を警戒し、合成数 133 = 7 × 19 を除外。(147 は 3 の倍数: 予選落ちして候補に入ってない。)

覚え方 瞳さん(131)・週七日 (瞳つまり目には休みの曜日がない=働き者の瞳さんに感謝)

11の倍数は? 両端の和が真ん中の数に等しい 143 は、11の倍数(11 × 13)。これも除外。

130~160の素数 131, 137, 139; 149; 151, 157

除外された数(2個) 133 = 140 − 7 と 143 = 110 + 33

まとめると、100~160には(16候補中、計4個が除外されて)12個の素数がある!

【3】 160より先を考える場合、13の倍数が絡んでくる。とりあえず必要なのは、132 = 169 ということ:
  13 × 13 = 13 × 10 + 13 × 3 = 130 + 39 = 169

13 が最小因子となる次の合成数は 13 × 17 = 130 + 91 = 221 なので、220までの範囲では、169 だけに気を付ければいい。

では、160~190の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

161  163  167  169  意味なく
     173       179  サンキュー
181       187       人質

上述のように 169 = 132 は除外される。

7の倍数は? 70の倍数から遠い領域なので末尾3, 7の数はセーフだが、21型・49型は怪しい。果たして 140 + 21 = 161 = 7 × 23 が除外される。(140 + 49 = 189 は予選落ち。)

覚え方 イロい(161=エロい)人・週七日 (エロい人は毎日元気)

11の倍数は? 両端の和が真ん中の数に等しい 187 = 11 × 17 を除外。

160~190の素数 163, 167; 173, 179; 181

除外された数(3個) 161 = 140 + 21 と 169 = 132187 = 110 + 77

最後に、190~220の幅30の領域にある素数候補8個を考えてみたい。

191  193  197  199  意味なく
     203       209  サンキュー
211       217       人質

210 に近いので、210 − 7 = 203 = 7 × 29 と 210 + 7 = 217 = 7 × 31 を除外。

覚え方 はたちさん(203)・週七日(はたちの若者は毎日元気)
     二人でいな(217)・週七日(元気なカップルは毎日二人きりにしてあげよう)

両端の和マイナス真ん中(2 + 9 − 0)が11になる 209 も、11の倍数なので除外(209 = 11 × 19)。

200台は全滅、210台も一つしか残らない。

倍数の分布の形から(あるいは個別に直接判定法を適用すると)、190台の4候補は全員セーフ(7の倍数・11の倍数を含まない)。

190~220の素数 191, 193, 197, 199; 211

除外された数(3個) 203 = 210 − 7 と 217 = 210 + 7、そして 209 = 110 + 99

まとめると、160~220には(16候補中、計6個が除外されて)10個の素数がある。そのうち、200~220の範囲には1個の素数しかない。

【4】 素数の数。

1桁の素数、10台の素数は、それぞれ4個あるが、20より先では、10ずつ区切った範囲に素数が4個あるのは、珍しい(四つ子素数と呼ばれる)。可能性があるのは「意味なく」の行だけ(「サンキュー」行と「人質」行では、最大でも2個しか素数がない)。

10□型は「意味なく」が4個とも素数になる例(101, 103, 107, 109)。反動で、周辺の9□型、11□型、12□型の素数は、どれも1個ずつしかない。

19□型も「意味なく」が4個とも素数。反動で、20□型の素数は1個もない。

ともあれ、これで220までの素数表を暗算できた! せっかくなので、220で止まらず、もうちょっと範囲を広げてみたい…。

221 = 13 × 17 であり、220より先を扱うには、13の倍数が問題。13の倍数は、7の倍数と同様の方法で判定可能。右端と残りに分けて、右端の4倍を残りに足せばいい:
  例 221 → 右端は1、残りは22 → 22 + 4 = 26 → 13の倍数

けれど一つ一つの数に対して、この計算をそのままするのは面倒。何か工夫できないだろうか?

⁂

2021-12-17 日本にゆかりのある素数 渋谷素数109、ポケモン素数151…

100~160の範囲の素数12個は、どれも面白い。日本にゆかりのある数も多い。

           97
101  103  107  109
     113
          127
131       137  139
               149
151       157

まず 101 は記念すべき初の3桁素数だが、10□型の素数は4個もある(101, 103, 107, 109)。このようなパターンを四つ子素数という。四つ子はかなりレアな存在で、20以下の素数密集地域を除くと、1000以下に3種類しかない。

それだけでなく、この四つ子、直前・直後の素数候補 97 と 113 も素数なので、それらを含めると六つ子素数。素数の六つ子は、1万に一つといった超レアな存在!

「意味なくサンキュー人質」の車輪ふるいでは、出だしの部分を除いて、六つ子で打ち止め。七つ子は発生しない(七つ子素数の概念はあるが、定義は複雑)。つまり 97 の直前の候補 91 = 7 × 13 と、113 の直後の候補 119 = 7 × 17 は、合成数。このうち 91 は、1クールの日数に当たる(1クールが13話、1話=1週間と仮定)。

さて、113は、どのように桁を並び替えても素数になる極めて珍しい数であり(131 と 311 も素数)、絶対的素数と呼ばれることがある。
 ※ 詳しく知りたい方は → Absolute Primes https://arxiv.org/abs/1811.08613
113 が絶対的素数なので、当然 131 と 311 も絶対的素数。

そればかりか、113 という数の桁を「変形合体」させることで、多数の素数を作ることができる: 自分自身を含めて 3, 11, 13, 31, 113, 131, 311 の7個の素数を「内包」。その数未満のどの数よりも「内包」素数が多いような数を「変形合体ロボ」と呼ぶことにすると、113 は「変形合体ロボ素数」。

この記録はすぐに 137 によって破られる。137 は、自分自身も含めて、11個もの素数を「内包」している: 3, 7, 13, 17, 31, 37, 71, 73, 137, 173, 317。すごい変形合体ぶり。この記録は、3桁の範囲では破られない。137 は、記録的な11面相・変形合体素数

143 = 11 × 13 は素数でない(両端の桁の和が真ん中の桁に等しい3桁の数は、必ず11で割り切れる)。けれど下2桁の43は素数であり、ガンダム素数と呼ぶことができる(またはガンダム・ようこ素数)。ファースト・ガンダムは52話くらいの予定だったが、43話で打ち切られてしまった。

139 は、東京素数。東京は東経139°台にある。天文計算者にはおなじみの数字かも…。一方、四つ子素数の 109 は、渋谷のランドマーク。

151 は、ポケモン素数(またはミュウ素数)。

これは初代ポケモンの数に基づく。バグポケモン(けつばん、アネデパミ、ィゃゾ…)はカウントしない。

⁂

127 = 27 − 1 は、メルセンヌ素数。M127 = 2127 − 1 もメルセンヌ素数。コンピューター関係で 127 = 0x7F は、いろいろとなじみ深い数。

けれど139を東京素数と呼ぶなら、127はソウル素数だろう。韓国の首都は、ちょうど東経127°くらいにある。歴史的には…黒歴史かもしれないが…韓国は大日本帝国の一部だったので、日本と無縁ではない。今でも日本時間の正式名称は「中央標準時」。「中央」というのは、日本国内に複数のタイムゾーンがあった時代の名残だろう。この場合の「中央」は東京の139°台ではなく、明石の 135° を基準としている(日本時間が UTC+9 なのは、天球上では 15° が1時間に当たり、135 = 15 × 9 だから)。

さて、残ったのは 149 と 157。

157 といえば、食中毒の O(オー)157。O157 は、大腸菌の型の一つだが、赤痢菌の毒素 Shiga toxin と同じタイプの毒素を持つそうだ(ほとんどの大腸菌は無害だったりむしろ有益だったりするが、これはヤバイらしい)。Shiga toxin (志賀毒素)の名は、日本の細菌学者・志賀潔(きよし)にちなむ。志賀は批判される面もあり、本国の日本では知名度が低いかもしれないけど、赤痢菌を発見した世界的大学者。赤痢菌の属名は、志賀にちなんで Shigella となっている。志賀の没年1957は、くしくも(9を取り除くと)157を含む。これはもう、157を志賀素数と呼ぶしかあるまい。

注: 大腸菌は、赤痢菌と同じ科の別の属の種であり、Shigella ではない。大腸菌の血清型O157:H7が単離されたのは、志賀の死後。けれど、どちらの病原菌も毒素が同種。腸管出血性大腸菌の毒素は Stx (=Shiga toxin) Type 1 と Type 2 に分類されるらしい。

最後に、149。それは、メルセンヌ・ファンにとって特別な数。憧れ、畏怖、あるいは青春…。M199 以下で、唯一 M149 だけが、古典技(試行除算やP−1法)では分解困難: 2149 − 1 のどの素因数 P についても、P−1 が巨大な素因子を含んでいるから。どのくらい巨大かというと、14桁(ざっと40兆。P 自体は20桁で、それが45桁の M149 の最小素因数)。「頑張ればギリギリ何とかなるかも」というレベルの100倍を超える。「楕円曲線で因数分解」は、M149 を分解する冒険だった。

12個の素数たち
101  103  107  109  四つ子・公園通り
     113       119@ 絶対的素数
121#      127       ソウル
131  133@ 137  139  絶対的素数・変形合体ロボ・東京
     143#      149  メルセンヌ最初のボス 怒首領蜂(どどんぱち)のヒバチ的存在
151       157       ポケモン(光過敏性)・志賀潔(腸管出血性)

@ = 合成数(7の倍数) 119番と瞳さん
# = 合成数(11の倍数) 両端の桁の和、イコール、真ん中の桁

⁂

2022-02-22 「日本にゆかりの素数」追加 テネシー大学 長崎の諏訪神社

PrimePages は、素数マニアの間では有名なウェブサイトだが(UTM[テネシー大学マーティン校]にホストされている)、その中に「素数の珍品たち」というトリビアのコーナーがある。これまた一部のマニアの間では大人気のページ…。以前「日本にゆかりのある素数」というメモを書いたが、一部、上記の珍品コーナーも参考にした。さすがに「ガンダム素数」はないが「ポケモン素数」は、本当にテネシー大学の珍品コーナーに収録されている。他にもアニメの話数ネタが1個くらいはあったと思う…。半分遊びのコーナーで、誰でもネタを送れるので(送っても収録されるとは限らないが)、数学的に深いネタもあれば、ばかばかしいようなネタもある。

で、先日、コーナー担当者 Honaker, Jr. と別のことでメールのやり取りをした際、「日本の長崎の諏訪神社のネタを加えたよ!」みたいな連絡が、ちょっと得意そうに書かれていた。当初のネタは「諏訪神社には、277段の長い石の階段がある」というものだった。277 は素数なので、事実なら、素数ネタのトリビアということになる。けれど…ネタを振られたので調べてみると、「277段」というのは、どうも出典がハッキリしない。確かに少数のウェブページ(特に英語版ウィキペディア)にはそう書かれているのだが、長崎青年協会広報誌2020年2月号には、こうある。「諏訪神社の階段は1番下からてっぺんまでは、小さな階段もいれると194段あります」…地元で書かれた情報だし、ウォーキングの記事なので、正確にカウントされている可能性が高い。さらに obisan @tobisan50 という方も「諏訪神社の階段は194段だったんやな!」と書いている。
https://nitter.net/tobisan50/status/1455705715901751299
194説の方が有力で、277という数は(間違いとも言い切れないが)疑わしい。

そこで「諏訪神社のことを書きたいなら、73段の長坂の話の方が良いかと…。もっとも、たまたま73段ある階段なんて、いくらでもあるだろうから Curio と言えるのか疑問だが…」と返信。Honaker は、どうしても諏訪神社のことを書きたいらしく(訳の分からない人である。お互いさまだがw)、結局「諏訪神社の73段の長坂は、長崎くんち
https://ja.wikipedia.org/wiki/%E9%95%B7%E5%B4%8E%E3%81%8F%E3%82%93%E3%81%A1
の観覧席になる」みたいな Curio が追加された。マニアックというか、もはや素数ネタと言えるのか謎だが、73が素数であることには変わりない。

というわけで、くんちを誇りにしている長崎のお祭り好きの人々は、米国の大学でも紹介されたので喜んでください(?)。「長崎の文化を紹介してくれるのはありがたいけど、何で素数のページで紹介するの?」という疑問はもっともですが、妖精のやることは、ちょっと変てこなのです(笑)。

「長崎が米国に感謝? 何か忘れてませんか?」というご批判も、ごもっともですが、国としての米国とは関係なく、単にそこにある大学の「素数好き」のページ、ってことで。

どこまで本気なのか、このトリビアの内容については「今年の10月7日になったら、また考える」そうです(10月7日=くんちの日)。

話は変わって、自走する石! 自然には謎がいっぱいある。
 https://en.wikipedia.org/wiki/Sailing_stones

さらに話は変わって、このツール。実際に役立つか不明で、安全かどうかも分からないが、技術的には面白そう。
https://github.com/ValdikSS/GoodbyeDPI

Deep Packet Inspection(パケットレベルの通信盗聴・監視・ブロッキング)から、あの手この手で逃れることを目指している。もちろん通信の秘密が守られ、こんなツールが必要にならないことが理想なのだが…

国・地域によっては、Great Firewall に代表されるような、厳しいアクセス制限があるのは周知の事実。一番分かりやすいパターンは「権力者にとって不都合な情報へのアクセスを妨害して、隠す」という思想統制だが、実際にはもっと複雑で「安全な通信路を提供する」と称して、逆にその通信路がひそかに監視されているというパターンもある。「これをインストールすれば安全になる」と称して、変なものをインストールさせたり…

ともかく、ロシアあたりは、政府の検閲が厳しくて、ウェブも自由に見られないらしい。中国よりはましかもしれないが…。

⁂

2021-12-18 13の倍数の見分け方 104 = 13 × 8 と 105 = 15 × 7 の謎

【1】 13で割り切れるかどうかの判定法は、7で割り切れるかどうかの第一判定法と似ている。右端の数字を4倍して、残りに足せばいい:
  例 312 → 右端は2、残りは31 → 31 + 2 × 4 = 39 → 13 で割り切れる
  例 183 → 右端は3、残りは18 → 18 + 3 × 4 = 30 → 13 で割り切れない

原理は簡単だが、末尾の数が大きいとき、正直にやるとちょっと面倒。例えば末尾が 9 のとき、36 を足す代わりに 3 を引いた方が楽:
  例 689 → 右端は9、残りは68 → 正直にやると 68 + 36 = 104 → 13 で割り切れる
  例 689 → 右端は9、残りは68 → 代わりに 68 − 3 = 65 → 13 で割り切れる
+36 ≡ −3 (mod 13) なので、13で割り切れるかどうかに関する限り、どちらでも同じこと。

同様に、例えば末尾 3 なら、12 を足す代わりに 1 を引き、末尾 7 なら、28 を足す代わりに 2 を足せばいい。

もちろん、小さい 13 の倍数を認識できる必要がある。
  13 × 1 = 13
  13 × 2 = 26
  13 × 3 = 39
  13 × 4 = 52 = 26 × 2
  13 × 5 = 65 = 13 × 10 ÷ 2 = 130 / 2
…くらいは常識で分かるとして、
  13 × 6 = 78 = 13 × 3 × 2 = 39 × 2 = (40 − 1) × 2 = 80 − 2
  13 × 7 = 91 = 70 + 21
  13 × 8 = 104 = 13 × 4 × 2 = 52 × 2
…などが必要になることも。もっとも、104 が 13 で割り切れるかどうか迷ったら、その末尾の4倍(つまり16)と、残りの10の和(つまり26)で判定すればいい。

【2】 【1】の判定法の証明。10 × 4 = 40 は 13 × 3 = 39 より 1 大きいので:
  40 ≡ 1 (mod 13)  … ①  [40を13で割ると1余る]
与えられた数を n = 10A + B とすると、それが13で割り切れるかどうかは、次が13で割り切れるかどうかと同値:
  4n = 40A + 4B ≡ A + 4B (なぜなら①)

4倍するのは①を使うための便宜上の操作。13の倍数は4倍しても13の倍数だし、13の倍数でないものを4倍しても13の倍数にはならない。だから、n が13の倍数かどうか調べる代わりに 4n を調べても同じこと。4倍すると数がでかくなって判定が面倒になりそうだが、実際に4倍するのは右端の1桁だけ。結果的には、大抵もともとの数より簡単になる(1桁小さくなることが多い)。

【3】 いくつもの数について素数か合成数かだけ判断したい場合、一つ一つ13で割れるか試すのは効率が悪い。平方数 132 = 169 を別にすれば、221未満の数の分解において、13が最小素因子になることはない。「13で割り切れること」の判定が不可欠になる最小の整数は:
  13 × 17 = (15 − 2)(15 + 2) = 152 − 22 = 225 − 4 = 221

221 以上の数についても、130 の倍数(260, 390 など)の近辺でだけ、
  判定したい数が 130k ± 13 型または 130k ± 39 型ではないか?
ということを気にすれば十分。400程度までの範囲では、具体的に
  260 − 39 = 221 = 13 × 17
  260 − 13 = 247 = 13 × 19
  260 + 13 = 273* = 13 × 21* = 3 × 7 × 13
  260 + 39 = 299 = 13 × 23

  390 − 39 = 351* = 13 × 27* = 33 × 13
  390 − 13 = 377 = 13 × 29
  390 + 13 = 403 = 13 × 31
  390 + 39 = 429* = 13 × 33* = 3 × 11 × 13
…の5つを合成数と見誤らなければOK(*印は3の倍数なので、明らかに合成数)。

末尾を4倍して残りに足す方法も、ダブルチェック(検算)や確認に使うことができる。
  221 → 22 + 1 × 4 = 22 + 4 = 26
  247 → 24 + 28 = 52 または 24 + 28 ≡ 24 + 2 = 26
  299 → 29 + 36 = 65 または 29 + 36 ≡ 29 − 3 = 26
  377 → 37 + 28 = 65 または 37 + 28 ≡ 37 + 2 = 39
  403 → 40 + 12 = 52 または 40 + 12 ≡ 40 − 1 = 39

(参考) k = 1 の場合の 130k ± 13 と 130k ± 39:
  130 − 39 = 91 = 13 × 7 = 7 × 13
  130 − 13 = 117* = 13 × 9* = 32 × 13
  130 + 13 = 143 = 13 × 11 = 11 × 13
  130 + 39 = 169 = 13 × 13 = 132

【4】 素朴な疑問。気になる4個の数。
  (☆) 90 = 15 × 6 と 91 = 13 × 7 は 1 違い。
      104 = 13 × 8 と 105 = 15 × 7 も 1 違い。
なぜ 13 の倍数と 15 の倍数が、こんな形で接近するのだろうか?

上記の関係は、いわゆる Théorème de Bézout(ベズの定理)と関係ある。…本当は定理を最初に記述したのは、「余白が狭過ぎる本」の著者 Bachet(バシェ)。ベズが生まれる100年以上前のことだが、ベズには定理を拡張した功績がある。…ともあれ、バシェ/ベズの定理によると、整数 a, b が互いに素なら
  ax + by = 1  … ②
は、整数解 (x, y) を持つ。a = 15, b = 13 は互いに素なので、ユークリッドの互除法を使って ② の一つの解を求められる:
  15 = 1 × 13 + 2 (従って 2 = 15 − 1 × 13
  13 = 6 × 2 + 1
従って:
  1 = 13 − 6 × 2 = 13 − 6 × (15 − 1 × 13)
  整理すると −6 × 15 + 7 × 13 = −90 + 91 = 1  … ③
③左辺において、第1項に ab = 15 × 13 を足し、第2項から同じ ab を引いても、値は変わらず、引き続き等号成立:
  (−6 × 15 + 15 × 13) + (7 × 13 − 15 × 13) = 1
  分配法則から (−6 + 13) × 15 + (7 − 15) × 13 = 1
  整理すると 7 × 15 − 8 × 13 = 105 − 104 = 1  … ④

a と b が互いに素のとき、②に解があることは定理からの帰結だが、この例の場合、a, b がほぼ等しく、絶対値において最小の解 x, y がちょうど a, b の半分くらいなので、③④を眺めたとき(☆)のような「ちょっと面白い感じ?」がする。

【5】 b を b で割るともちろん(商は 1 で)余りは 0 なので、b ≡ 0 (mod b)。同様に by ≡ 0 (mod b) でもある。②の等号を、mod b の合同記号に置き換えると:
  ax + by ≡ ax + 0 ≡ 1 (mod b)  [なぜなら by ≡ 0]
…要するに「a が法 b と互いに素の場合、ax ≡ 1 (mod b) を満たす x が存在」。7 の倍数の判定法で「右端」の −2 倍、13の倍数の判定法で「右端」の 4 倍を考えることは、それぞれ、10x ≡ 1 (mod 7) の解 x ≡ −2 と、10x ≡ 1 (mod 13) の解 x ≡ 4 を利用したもの。「ax ≡ 1 が解を持つ」ということは、「a が逆数 a−1 = x を持つ」ことに他ならない。一般に、b で割り切れるかどうかの判定法では、法 b における 10 の逆数を利用できる。

例えば 10x ≡ 1 (mod 19) の解は x = 2 なので(なぜなら 10 の 2 倍を 19 で割ると 1 余る)、19 の倍数の判定法はシンプル: 右端の2倍を残りに足せばいい。

⁂

2021-12-21 17²は繰り上がりなしで暗算可能 どうやって?!

トリビア 172 と 182 は、繰り上がりなしの足し算で暗算できる!

えーっ、どうやって??? 

単純に考えれば (10 + 7)2 = 102 + 2 × 7 × 10 + 72 = 100 + 140 + 49 = 289 だが、いろいろ遊んでみよう!

182 は易しい:
  182 = (2 × 9)2 = 22 × 92 = 4 × 81 = 324
9 × 9 = 81, 4 × 8 = 32, 4 × 1 = 4 という掛け算の九九だけを使って、繰り上がりがどこにも生じていない。

一方、64 の2倍が 128、そのまた2倍が 256 ということは、よく知られている。つまり 64 × 4 = 256。これを使うと、182 と同様にして:
  162 = (2 × 8)2 = 22 × 82 = 4 × 64 = 256

172 は、上記 162 = 256 と 182 = 324 の間にあるので、だいたい300だろう。

トリビア2  112 = 121 だが、172 は、16進数の 112 = 121 に当たる(便宜上☆で16進数を表す):
  16 = 10, 17 = 10 + 1 なので
  172 = (10 + 1)2
  = 102 + 2 × 10 × 1 + 12
  = 100 + 20 + 1 = 121

トリビア2をもっと普通に書くと:
  172 = (16 + 1)2 = 162 + 2 × 16 × 1 + 12 = 256 + 32 + 1 = 289
  → 172 も繰り上がりなしの足し算になる!

ただし、162 = 256 と 16 × 2 = 32 を知ってれば…。そのような条件を付けず、「絶対に繰り上がりしない」という縛りプレーでやってみよう:
  122 = (10 + 2)2 = 102 + 2 × 10 × 2 + 22 = 100 + 40 + 4 = 144
1グロス=12ダース=144は常識かもしれないが、念のため計算した。さて:
  172 = (5 + 12)2 = 52 + 2 × 5 × 12 + 122
  = 25 + 10 × 12 + 144
  = 25 + 120 + 144
  = 145 + 144 = 289
…要するに、17の2乗は「2グロス1」に当たる!

PNG画像

⁂

2021-12-22 300以下の素数は62個 暗算で素数表(2)

200以下の素数は46個――「車輪」を7回転させ、10~220の範囲の素数表を得た。今回は、車輪をあと3回転させ、310まで素数表を広げる。

【1】 220からというのは実用上、中途半端なので、復習も兼ねて200くらいから。車輪の性質上、30の倍数プラス10の190からスタート。

191   193   197   199
      203@        209#
211         217@     

210 = 7 × 30 は7の倍数なので、それ ±7 も7の倍数:
  7 × 31 = 7 × (30 + 1) = 7 × 30 + 7 × 1 = 210 + 7 = 217
  7 × 29 = 7 × (30 − 1) = 7 × 30 − 7 × 1 = 210 − 7 = 203

209 のように、「両端の桁の和マイナス真ん中の桁」が 0 or 11 になる3桁の数は11の倍数――素数ではない:
  11 × 19 = 11 × (20 − 1) = 11 × 20 − 11 × 1 = 220 − 11 = 209
結局、20□型の素数はなく、200~220の範囲には、素数が1個しかない。その分、190台には素数がいっぱいあり、(191, 193, 197, 199) は四つ子素数。3桁の四つ子素数は3組しかないが、100~200は、四つ子に始まり、四つ子に終わる。

【2】 本題。220からの3回転は、次の9行4列:

221   223   227   229  意味なく
      233         239  サンキュー
241         247        人質

251   253   257   259  意味なく
      263         269  サンキュー
271         277        人質

281   283   287   289  意味なく
      293         299  サンキュー
301         307        人質

11の倍数は易しい。2□1の両端の数を足すと3。だから 2□1型の11の倍数は 231*(ここで*は「3の倍数」であることを強調)。つまり、左端の列に11の倍数はない。同様に、2□3の両端の和は5なので、253 は11の倍数。これが第2列から除外される。第3列に11の倍数はなく、第4列にもない(209が11の倍数だが、範囲外)。

上記候補内に、11の倍数は1個だけ。253 = 11 × 23 がふるわれた。

【3】 7の倍数。候補一つ一つに7の倍数の判定法を素直に適用するのは面倒。ここでは70の倍数(70, 140, 210, 280など)を基準に、それ ±7, ±21 をふるい落とそう。220~310の範囲では、次の3個が該当:
  [210 + 7 = 217 = (30 + 1) × 7 = 7 × 31] ←範囲外
  210 + 21 = 231* = (30 + 3) × 7 = 7 × 33*
  ① 280 − 21 = 259 = (40 − 3) × 7 = 7 × 37
  280 − 7 = 273* = (40 − 1) × 7 = 7 × 39*
  ② 280 + 7 = 287 = (40 + 1) × 7 = 7 × 41
  ③ 280 + 21 = 301 = (40 + 3) × 7 = 7 × 43

231* と 273* は、3の倍数なので予選落ち。それぞれ 33* 倍、39* 倍(つまり「3の倍数」倍)だから、当然そうなる。

この方法が成り立つ根拠。「7 × (7以上の素数)」の形の合成数をふるいたい: 7以上の素数は 11, 13, 17, 19, 23, etc. のように必ず1の位が 1, 3, 7, 9 だから、次の数を検討すれば十分:
  A群 7 × 11, 7 × 13, 7 × 21*, 7 × 23, 7 × 31, 7 × 33*, etc.
  B群 7 × 17, 7 × 19, 7 × 27*, 7 × 29, 7 × 37, 7 × 39*, etc.
このうちA群は 7 × [10の倍数 + (1 or 3)] なので、分配法則から
  70の倍数 + (7 or 21)
となる。B群は 7 × [10の倍数 − (1 or 3)] なので、分配法則から
  70の倍数 − (7 or 21)
となる。

実際上「70の倍数から 21 を引く」代わりに、「一つ小さい70の倍数に 49 を足す」方が楽になることがある。例えば①の 259 は 210 + 49 と見た方が分かりやすい。

この方法は13の倍数・17の倍数などにも応用が利く: 一般に、7以上の素数 p の倍数をふるうとき「10p の倍数 ± p」と「10p の倍数 ± 3p」だけをふるえば十分

11の倍数に関しては、桁パターンの感覚がつかめれば、そっちの方がいくらか楽だと思われるが、機械的に上記の方法を使う手もある。

付記 20p + p = 21p, 30p − 3p = 27p, 30p + 3p = 33p などは、どれも3の倍数。既に予選落ちしているので、それらをチェックするのは無駄。でも、無駄な計算を省略するには「省略できるかの判定」が必要。慣れてないと、かえってややこしくなる。最初は、無駄を承知で「10p の倍数 ±p, ±3p」を機械的に全部チェックする方が得策かもしれない。

【4】 220~310の範囲にある13の倍数。同様に考えると、260 ± 13 と 260 ± 39 は合成数:
  ① 260 − 39 = 221 = (20 − 3) × 13 = 13 × 17
  ② 260 − 13 = 247 = (20 − 1) × 13 = 13 × 19
  260 + 13 = 273* = (20 + 1) × 13 = 13 × 21*
  ③ 260 + 39 = 299 = (20 + 3) × 13 = 13 × 23

220~250の候補には、13の倍数が2個も含まれていた!

221†  223   227   229
      233         239
241         247†      

251   253#  257   259@
      263         269
271         277      

281   283   287@  289
      293         299†
301@        307      

@ = 7の倍数 【3】参照
# = 11の倍数 【2】参照
† = 13の倍数

【5】 これで、220~310の範囲の7の倍数・11の倍数・13の倍数は全部ふるい落とされた。けれど、あと一つだけ、合成数が残っている。それは
  172 = 17 × 17 = 289
という平方数。

300 までの素数表の暗算で、一つの鍵となるのは、172 がその範囲に含まれるのでは?と気付くこと(一般に、N までの素数表を作るためには √N 以下の素数でふるう必要がある)。√3 = 1.732… を使うと:
  √300 = √3 × √100 = 1.732… × 10 = 17.32…
  つまり、(17.32…)2 = 300 だから、172 は 300 より小さい。

トリビア」で紹介したように、172 = 289 は、2グロス(=288)プラス1に当たる(グロスは12ダース)。

他方、
  17 × 19 = (18 − 1)(18 + 1) = 182 − 12 = 324 − 1 = 323
なので、17 × 17 = 289 の次の「ふるう必要がある17の倍数」は320台、今回の範囲外。

【6】 結局、220~310の幅90では、24個の素数候補のうち8個がふるい落とされ、16個の素数が残る。ふるい落とされた内訳は、7の倍数3個(259, 287, 301)、11の倍数1個(253)、13の倍数3個(221, 247, 299)、17の倍数1個(289)。

220以下の素数は47個だったので、310以下の素数はそれプラス16で63個。300~310の素数は1個だけ(307)なので、300以下の素数は62個となる:
  pi(100) = 25, pi(200) = 46, pi(300) = 62
  ここで pi(N) は、N以下の素数の数。

次の事実に注目し、心の片隅にとどめておくと、記憶の整理に役立つ: 220~310の幅90を、幅30ずつ三つのエリアに分けて考える(車輪の3回転に当たる)。最初と中間の幅30には、それぞれ素数が半ダース(6個)ずつ含まれるが、最後の幅30には素数が4個しか含まれていない。言い換えると、車輪の素数候補から、合成数が順に2個・2個・4個ふるわれる。最初の2個は、どちらも13の倍数(221 = 13 × 17; 247 = 13 × 19)。残りの6個のうち、7の倍数・11の倍数(計4個)は、慣れればまず見落とさない。289 = 172 と 299 = 260 + 39 だけ軽く意識しておこう。ティーンの平方数 289 はピンポイントで覚えておくべきなのだが、意外と盲点になって、素数と勘違いすることがある。91 は素数と間違われやすいことで有名だが、289 も要注意。

190台の後は、820台まで四つ子素数はない。200~800の範囲では「意味なく」の4候補中、最低1個は非素数。それを見抜いて、ふるう必要がある。

  1. 220までの素数47個を確実に分かるようにする。100までの素数25個は常識として、100~220の素数22個を追加しよう。100~160の前半1ダースと、それ以降の後半10個に分けて覚えると楽。「100台は四つ子に始まり、四つ子に終わる」ということから、実質8個と6個。
  2. 220~310の素数16個を「心の素数表」に追加。63番素数307に到達(今回)。
  3. 310~430の素数19個にチャレンジ。82番素数421に到達。気持ちの上では100番素数541に手が届きそうになるので、100個覚えることを第一目標とする。
  4. 430~520の素数15個にチャレンジ。97番素数509に到達。100番まであと一歩に思えるが、その区間は結構険しい(だから面白い)。500くらいまでの数なら、何でも暗算で素早く素因数分解できるようになる。
  5. 100個覚えられたら、今度は1000以下の素数168個を目指そう! 3桁までの数なら何でも暗算で素早く分解できるようになる。

素数表それ自体を丸暗記しても大して役立たないが、7の倍数・13の倍数・17の倍数などを識別するアルゴリズムや、299のような数の素因数分解に慣れておくと「底力」になるし、何の役に立つかと無関係に、それ自体が面白い。人生、遊びだぜ。

【7】 (参考) 10~220の候補中、7の倍数に特別な印を付けておき(下記では@)、以下210単位で、同じ位置をマークすると、7の倍数は機械的に除去される(「2, 3, 5で割り切れない7の倍数」プラス210は、再び「2, 3, 5で割り切れない7の倍数」なので)。

 11   13   17   19        221† 223  227  229
      23        29             233       239
 31        37             241       247†    

 41   43   47   49@       251  253# 257  259@
      53        59             263       269
 61        67             271       277     

 71   73   77@  79        281  283  287@ 289ṡ
      83        89             293       299†
 91@       97             301@      307     

合成数の最小素因数  @=7 / #=11 / †=13 / ṡ=17

10~100の範囲では 49, 77, 91 の3個が該当。従って、それらに210を足した 259, 287, 301 の3個が220~310から除外される。この考え方で7の倍数をふるうと【3】の方法より速い。30周期の車輪を7個束ねた「大車輪ふるい」(210周期)。このテクニックを使うには、7が最小因子となる220未満の合成数 49, 77, 91, 119, 133, 161, 203, 217 を熟知している必要がある(119番・瞳さん・イロい・はたちさん・二人でいな)。周期が210なので、300や400くらいでは、あまりありがたみが感じられないが、それより上では結構役に立つ。

【8】 200~300の素数16個について

200~300の幅100を考えても、220~310の幅90を考えても、素数が16個ある! 前者の方が幅が広いが、上述のように200~220には素数が1個しかない(211)。そして300~310にも素数が1個しかないので(307)、カウントが一致する。

⁂

2022-02-03 400以下の素数は78個 暗算で素数表(3)

200以下に素数は46個あり、日本にゆかりのある素数も多い。300以下の素数は62個。実際には、310までの素数63個を探索した。

引き続き310以降の素数を考え、トリビアや、17の倍数の判定法・19の倍数の判定法を紹介したい。7の倍数・11の倍数・13の倍数についての詳細や、車輪の原理については、過去のメモ参照。ミスタイプや計算ミスがあったら、適宜、修正して読んでください。

【1】 310~340の幅30。次の8個の数の中には、合成数が3個ある。どれか?

311  313  317  319
     323       329
331       337

① 3桁の数は「両端の桁の和 = 真ん中の桁」の場合、または「両端の桁の和 = 真ん中の桁 + 11」の場合に、11で割り切れる。319 は、このパターンなので、11の倍数。

百の位を下2桁に足してもいい: 3 + 19 = 22 は 11 の倍数なので、319 は11の倍数。

別の発想: 319 = 400 − 81 = 202 − 92 = (20 + 9)(20 − 9) = 29 × 11。

② 7の倍数については、最寄りの70の倍数 350 からアプローチ。±7 と ±21 を考えると、350 − 21 = 329 = 7 × 50 − 7 × 3 = 7 × 47 が見える(357*, 343, 371 が7の倍数であることも同時に検出される)。検算として、右端の2倍を残りから引く: 32 − 9 × 2 = 14 は 7 の倍数なのでOK。

「329 = 280+49 = 7の倍数」と考えてもいい。

検算については、百の位の2倍を下2桁に足してもいい: 3 × 2 + 29 = 35 は 7 の倍数なので、329 は7の倍数。

③ これで2個見つかったが、3個目が少し難しい。11と7が駄目なら、順序としてはまず13の倍数を疑うが、最寄りの130の倍数 260 or 390 は ±13 でも ±39 でも遠過ぎる。つまり、上記の範囲に「13が最小因子の数」はない。172 = 289 以上には「17が最小因子の数」があるので、17の倍数を検討しよう。最寄りの170の倍数 340 = 17 × 20 を基点に ±17 を考えると、果たして 323 = 17 × 19 が見つかる(357* = 17 × 21* も見つかる)。192 = 361 未満には「19以上が最小因子の数」はないので、残った5個は素数!

182 (= 81 × 4) = 324 が平方数と分かれば、ほぼ一瞬(下記【3】参照)。

【2】 この 323 = 17 × 19 を例に、17の倍数・19の倍数の判定法を導入する。7の倍数の判定法は「右端の2倍を残りから引く」だった。19の倍数は、逆に「右端の2倍を残りに足す」ことで、判定可能:
  323 → 右端は3、残りは32 → 32 + 3 × 2 = 38
  → 38 は 19の倍数だから、もともとの 323 も 19 の倍数

この判定法は、実際に19で割り算するよりいくらか速いので、検算などで活用できる(素数表を暗算生成するとき、一つ一つの素数候補にそのまま適用するのは、効率が悪い)。

さて、13の倍数の判定法は「右端の4倍を残りに足す」だった。例えば 91 は 13 の倍数(なぜなら 9 + 1 × 4 = 13 は 13の倍数)。

一方、17の倍数の判定法は「右端の5倍を残りから引く」。例えば 323 は 17 の倍数(なぜなら 32 − 3 × 5 = 17 は 17の倍数)。7の倍数と19の倍数については、判定法が正反対なのでペアにして覚えやすいが、13の倍数と17の倍数については、判定法の符号が逆で倍率も違う。4種類のことをまとめて丸暗記しようとすると必ずごちゃごちゃになるので、じっくり一つずつ覚えよう…。

17の倍数の判定法は、あまり効率が良くないが(下手すると、普通に筆算方式で割り算した方が速い)、検算に利用できる。

【3】 もう一つの注目点として、323 は平方数 182 = 324 より 1 小さい。まず平方数自体は:
  182 = (9 × 2)2 = 92 × 22 = 81 × 4 = 324
…と繰り上がりなしに計算できる。そして、
  n2 − 1 = (n + 1)(n − 1)
なので、「平方数から1を引いた数」は、必ず「差が2の2数」の積になる。324 が 182 であることと、その1個手前の 323 が 17 × 19 であることは、そういう関係。例えば、
  18 × 20 = 360
は、それだけだと「当たり前の計算」かもしれないが、上記の性質を逆向きに使うと:
  192 = 361
…ちょっとした数の遊び?

19 の平方 361 は、1年の日数に近い(9 × 9 = 81 なので末尾は1)。
それは 360 = 18 × 20 とも関係ある。
歴史的に円周が360°なのは1年の日数と関係あるらしいから、192 が1年の日数に近いのは必然?

10台の平方:
  102 = 100, 112 = 121, 122 = 144
  132 = 169, 142 = 196 ← どちらも桁は「1, 6, 9」
  152 = 225, 162 = 256
  172 = 289 ← 2グロス1
  182 = 324 ← 81の4倍
  192 = 361 ← 1年の日数に近い

【4】 続いて340~370の幅30。次の8個の中にも合成数が3個。どれでしょ?

341  343  347  349
     353       359
361       367

① 341 は、両端の和が真ん中なので、11の倍数。

百の位を下2桁に足してもいい: 3 + 41 = 44 は 11 の倍数。

② 343 = 350 − 7 = 7 × 50 − 7 × 1 = 7 × 49 は【1】でチェック済み。= 7 × 72 = 73 と立方数。一桁の数の立方数のうち、
  1, 8, 27, 64, 125 までは、それなりに日常的な数だが、
  216, 343, 512, 729 の中には、ちょっとエキゾチックな数も…

立方数 343 = 73 は知っていて損はないが、7 の倍数であることの検算としては、百の位の 3 の2倍を下二桁(43)に足すと49(これは 7 の倍数)。

③ 361 = 192 は【3】の通り。残りの5個は、素数!

検算: 36 + 1 × 2 = 38 は19の倍数。

351* = 390 − 39 = 13 × 27* は13の倍数だが、3の倍数なので予選落ち。357* = 340 + 17 = 17 × 21* は17の倍数だが、予選落ち。

【5】 さらに、370~400の幅30。次の8個の中にも合成数が3個。どれ?

371  373  377  379
     383       389
391       397

① 11の倍数はない。7の倍数として、371 = 350 + 21 = 7 × 50 + 7 × 3 = 7 × 53 が見つかる。

検算: 37 − 1 × 2 = 35 は7の倍数。百の位 7 の2倍を下二桁に足してもいい(71 + 6 = 77)。

② 390 = 13 × 30 前後には 13 の倍数 390 ± 13 がある: 377 = 13 × 29 と 403 = 13 × 31 だが、前者が上の範囲内。

③ 17の倍数。17 × 3 = 51 を心に刻みつつ、17 × 20 = 340 を基点とすると:
  17 × (20 − 3) = 172 = 340 − 51 = 289 ← 2グロス1(平方数)
  17 × (20 + 3) = 17 × 23 = 340 + 51 = 391
後者が範囲内。【2】による検算: 39 − 1 × 5 = 34 は 17 の倍数なのでOK。

別の発想: 391 = 400 − 9 = 202 − 32 = (20 + 3)(20 − 3) = 23 × 17。

192 = 361 の次の「19が最小因子の数」は 19 × 23 = 437 なので、430くらいまでの範囲では、19の倍数を積極的にふるう必要はない。361 を例外として、後は17の倍数までをふるえば素数が残る。

【6】 今回は、幅30の範囲を連続3個調べた(310~400)。それぞれ素数候補を8個含むが、どれも3個が合成数としてふるい落とされたので、結局、各範囲から5個ずつ、計 5 × 3 = 15 個の素数が残った。310までの素数は63個なので、400までの素数は合計78個

ちょうど400で切りがいいので、今回はここまで。本当は400で止まらず430まで一気に進めた方がいいのだが、続きはまたいつか…。


ジョジョの奇妙な素数表。383が抜けてるのは、プッチ神父の内心の動転を暗示する描写だろうか?
192=361 を正しくふるえているのだから、7, 11, 13, 17 の倍数だけ気にすればいい。
390 が13の倍数、340+51=391が17の倍数であることから、383 は13でも17でも割れない。
普通にやれば、7の倍数と11の倍数は易しいはずだが… 素数409が抜けてるのは、コマが変わるので時間経過が省略されたと解釈できないこともない。

⁂

2022-02-27 82番素数421 暗算で素数表 (4)

400以下の素数は78個だが、アルゴリズムとしては、そこで止まらず「430以下の素数は82個」まで進めた方がいい。

【1】 ほとんどの人は、2の倍数(=偶数)、5の倍数(=末尾が0か5)を一目で認識できるだろう。3の倍数も「桁の和が3の倍数か?」で判別でき、3桁程度の数ならほぼ瞬時に分かる。

「2の倍数、3の倍数、5の倍数」に対する感覚は、日常的にも数学的にも、役に立つ。さらに進めて「7の倍数、11の倍数」などは、どうだろうか…。7が最小素因数となる整数は、210単位の一定パターンで分布。10を起点にすると、10~220が1周目、220~430が2周目となる。

その2周目末尾の幅30の区間には、次の8個の素数候補(5以下の約数を持たない)がある。

401    403    407    409
       413           419
421           427

407 は一目で11の倍数(下2桁 07 に百の位の 4 を足した 11 が11の倍数だから)。「30の倍数プラス10」を起点とする幅30の8候補内に、11の倍数はあっても1個なので、1個見つかったら、それ以上11の倍数を探す必要はない。

対照的に、13の倍数については、ごくまれに8個中に2個含まれる場合がある。最初の1個が13の倍数の場合、それプラス26が末尾の1個なので、末尾も13の倍数。2周目冒頭の220~250で起きた

420 = 7 × 60 なので、それ ±7 の 427, 413 はそれぞれ 7 × 61, 7 × 59 であり、7の倍数。このように、7の倍数は、8個中に2個含まれることが普通にある。この場合で言えば、「210の倍数 ± 7」は、どちらも「7が最小素因数の合成数」。

427 はそもそも一目で7の倍数(末尾も、上二桁も7で割り切れる)。幅30に、このような7で終わる7の倍数があるとき、その幅30にはもう一つ7の倍数(7を最小因数とする)がある。413 の検算法の一つ: 百の位4の2倍を下二桁に足して21(これは7の倍数)。

【2】 11の倍数が1個、7の倍数が2個、ふるわれた。考えている数の範囲400~430は、192 = 361 を超えているが、232 = 529 より下なので、13の倍数・17の倍数・19の倍数の3種類も(もしあるなら)ふるう必要があり、そこまでふるえば十分。

13の倍数 最寄りの130の倍数 390 = 13 × 30 からアプローチ。可能性として ±13 と ±39 があるが、390 + 13 = 403 = 13 × 31 に気付くことは難しくない。

検算 403 の末尾桁 3 の4倍を上位2桁に足すと52。このチェックサムは13の倍数なので、もともとの数403も13の倍数。

17の倍数 最寄りの170の倍数は 340 と 510 だが、それらを基準にすると、±17 でも ±51 でも、400~430 には届かない。つまり、この範囲に17の倍数はない。

510 ± 51 は、計算するまでもなく 3 で割り切れることが見え見え(510 + 51 = 561 は、11でも割り切れる)。こういう数については、暗算素数表では、最初から無視して構わない。これを「スナイパー方式」という(合成数だと分かり切った数については、ふるい自体を省略)。

19の倍数 最寄りの190の倍数は 380 = 19 × 20。それを基準に ±19 と ±57 を考えると、437 = 380 + 57 = 19 × 23 が見つかるが、400~430の範囲より少し上。この範囲の8候補の中に、19の倍数はない。

380 + 19 = 19 × 21 = 399 も上記範囲にギリギリ届かない(21倍という時点で3の倍数と分かるので、スナイパー方式では最初から無視される)。437 は、今回の範囲外だが、ふるう必要のあるターゲットには変わりない。「次の幅30には、19が最小素因数の合成数437がある…」ということを心の片隅にキャッシュしておこう。

【3】 まとめると、次のように4個ふるわれ、4個残る。

401    403†   407#   409
       413@          419
421           427@

合成数の最小素因数 @=7, #=11, †=13

400までの素数が78個なので、401 が79番素数、この区間の最後の素数421 は、82番素数

421 は、桁が上位から下位へ次々と半分になっていく特徴的な数であり、大車輪2周目の最終素数。82番という番号(語呂合わせ「ハニー」)も覚えやすいため、暗算素数表では「過不足なく素数をカウントできているか」のチェックポイントとして使える。「95番素数499」の方が印象的に思えるが、アルゴリズム的には「ハニー」も重要な目印。ちなみに「ハニイ」の 821 も素数で、珍しい「四つ子素数」の先頭に当たる(こちらは素数番号ではなく、素数そのもの)。

たまたまというか何というか、421 という数は「一桁の素数は4個、二桁の素数は21個」という 4 & 21 というカウントとも対応している:
https://primes.utm.edu/curios/page.php?curio_id=31722

【4】 話の便宜上、ここでは「7を最小素因数とする合成数」を単に「7の倍数」と呼ぶことにする。10~220について、幅30ずつの七つの区間に区切って、順に日曜・月曜・火曜…と呼ぶことにすると、日曜には「7の倍数」が全くなく、火曜と土曜には「7の倍数」が2個あり、それ以外の曜日には「7の倍数」が1個だけある。

「7の倍数」の表(1周目)
日曜 (10~40) なし
月曜 (40~70) 49
火曜 (70~100) 77と91の二個
水曜 (100~130) 119
木曜 (130~160) 133
金曜 (160~190) 161
土曜 (190~220) 203と217の二個

このうち、49 = 72 と 77 = 7 × 11 は、一目瞭然。91 = 7 × 13 も、素数表を考えるとき、最初に認識することの一つだろう(これを認識できないと、100以下の25個の素数さえあやふやになり、13の倍数の判定でも困る)。

残りの5個は、意識して覚える必要がある。語呂合わせは、119番、瞳さん、イロい、はたちさん、二人でいな。

2周目の220~430における「7の倍数」は、上記の8個に単に 210 を足したもの。

「7の倍数」の表(2周目)
日曜 (220~250) なし
月曜 (250~280) 259
火曜 (280~310) 287と301の二個
水曜 (310~340) 329
木曜 (340~370) 343
金曜 (370~400) 371
土曜 (400~430) 413と427の二個

この表を丸暗記する必要はなく、必ずしも、この方法でふるうのが最適とも限らない。火曜日の287は、28と7が7の倍数なので一目で7の倍数と分かり、210 + 77 と考えるまでもないし、木曜の 343 = 73 なども、直接認識できる方が役立つ。細部についてはケースバイケースで、自分にとって分かりやすい方法を使えばいい。けれど、210を周期とするこのパターンの存在を知っていると、全体の見通しが良くなる。例えば日曜日の幅30をふるうとき、そこに「7の倍数」がないことは分かり切っているので、「7の倍数」をふるう手間が省ける。

「末尾が7、残りの部分が7の倍数」(7の倍数だと分かりやすい)がふるわれるゾーンでは、必ず『もう一つの7の倍数』がふるわれる。1周目火曜下段の「77」に対して『91』、2周目火曜下段の「287」に対して『301』――それぞれ210の倍数+77 or 91、言い換えると (7×11, 7×13), (7×41, 7×43) に当たる。1周目末尾の「217」に対して『203』、2周目末尾の「427」に対して『413』――それぞれ210の倍数±7、つまり (7×31, 7×29), (7×61, 7×59) に当たる。

素数はある意味ランダムに分布しているようだけど、実際には、日曜ゾーンは素数の密度が高くなり、火曜・土曜は素数の密度が薄くなる傾向がある! 前者では「7の倍数」が一個もふるわれないが、後者では「7の倍数」が二個ふるわれ、8候補が直ちに6候補に減るから。この「7の倍数」のパターンは、3周目以降でも全く同様。

【5】 このパターン性のため、全体像を把握するには、中途半端な400で止まらずに、430までをまとめて考える必要がある。のみならず、400までの素数は78個だが、430までの素数は82個(ハニー)。82番まで来ると、気持ちの上では100番素数に手が届きそう。もうちょっとで95番素数499に到達でき、そうなると、100番素数まであとひと息。「最初の100個の素数」は、自然な第一目標だろう(その次の目標は、1000以下の素数168個)。

⁂


メールアドレス(画像)