これは面白い！ 素因数分解が動き出す？

これは高校レベルの素因数分解のちょっとしたトリックみたいなもんだけどさ、手で多項式の因数分解やるのがすごく楽になったんだ。100以下の合成数は全部2、3、5、7のどれかで割れるって気づいてからね。どれでも割れなかったらそれは素数だから、そこで因数分解を止められるわけ。このルールで“パッと見分からない”合成数は713=91だけで、他のは普通のルールですぐ試せるんだ。49は7²だからこれもすぐわかる。他の素数判定も簡単だよ。いくつか例を挙げるとさ：
・31？2、3、5では割れないし、7²以下だから7で割れる心配もない。素数だね。31=31¹。
・69？3で割れるね。69 = 323。23は？2、3、5で割れないから、そこでストップ。69=3¹23¹。
・92？2で割って2*46。また2で割って2²23。23は2、3、5で割れないから、92 = 2²23¹。
・68 = 2¹34 = 2²17。17は2、3、5で割れないから、そこでストップ。2²17¹。高校の教科書は普通100より大きい数を使わないから（電卓持ってない生徒のために）、このトリックは何度も役に立ったな。それに、低い数では素数が驚くほど多いけど、高くなるにつれて急速に減っていくっていう考え方にも通じるんだよね。

3の倍数判定法で、各位の数を足していくトリックも知ってるでしょ：387なら3+8+7で18、さらに1+8で9になるやつ。あれって10を3で割ると1余るから、100=99+1（など）で、各桁がまるで一の位みたいに数えられるからできるんだよね。同じトリックを7の倍数に応用しようとすると、10を7で割ると3余るから十の位は3の価値があって、91だと93 + 1 = 28 になる。おっと、計算間違えた。えっと、91 -＞ 93 + 11 = 28、7で割れるね。でも次の位は100を7で割ると2余るから、値が変わっちゃうんだ（100 = 147 + 2）。このトリックは全然役に立たないんだけど、個人的には好きなんだよね。（間違ったところを全部直したよ）

うーん…14だと =＞ 1 (3¹) + 4 (3⁰) =＞ 3 + 4 = 7 =＞ 7で割れるね。21だと =＞ 2 (3¹) + 1 (3⁰) =＞ 6 + 1 = 7 =＞ これも7で割れる！7 * 53 = 371 =＞ 3 (3²) + 7 (3¹) + 1 (3⁰) =＞ 27 + 21 + 1 =＞ 49 =＞ これも7で割れるじゃないか！すごいな！基数の仕組みを勉強してから、こういう直感はできるんじゃないかってずっと思ってたけど、自分でちゃんと調べたことなかったんだ。マジかよ！

うーん、いや、それは擬陽性の危険があるんだ（だから前にミスを直さなきゃいけなかったんだよね）。全部が3に関係してるわけじゃないし、桁の数を3²、3¹、3⁰って掛けちゃダメなの。その代わりに、チェックしたい数（7とかね）で割った時の、（10をその桁数乗した数）の余りを使いたいんだよ。それは繰り返しのパターンになるんだ。3の場合はパターン長が1で、（1, 1, 1, …）って続く。7の場合はパターン長が6で、一の位から（1, 3, 2, 6, 4, 5）って続くんだ。ちょっと擬似乱数っぽい感じに見えるなら、それにはちゃんとした理由があるんだ。昔のPRNGに漠然と似てるんだよ。（百万の位からまた1が始まるんだ。だって142857 * 7 = 999999だからね。だから200万を7で割った余りは2、300万を7で割った余りは3、って感じ。）だから371は 32 + 73 + 11 って考えるべきで、これは28になる。別の例だと、6993 =＞ 66 + 92 + 93 + 3*1 で、これは84になるよ。

いやちょっと待ってよ。10をn乗して7で割った余りの結果と、3をn乗して7で割った余りの結果って同じじゃないか。だから前のコメントの方法も、正確に機能してるんだよ。差が7だからなんだよね。

3のべき乗の図がSierpinski triangleになるんだね。見たら超納得だけど、今日まで知らなかったよ！

うんうん。この可視化がくれたユニークな洞察、超気に入ったよ。Sierpinski triangleについて、頭の中でどう考えるべきか、何か解放された感じ。もし誰か興味あったら、アニメーションで見られる最大の純粋なSierpinskiは6561（3^8）だよ。10Kでキャップされてるからね。

これすごい！このやり方で表現された数字をドラッグ＆ドロップで掛けたりまとめたりできるおもちゃ（to build）を作りたいな。素因数が（boidsみたいに）どう動くか見たいんだ。この可視化アルゴリズムって何か名前があるのかな？前のHNポストにあった説明リンク、壊れてるみたいだね：
http://mathlesstraveled.com/2012/10/05/factorization-diagram…

2（ペア）、3（三角形）、4（正方形）、5（五角形）以外の7以上の素数にも、丸じゃなくて一目で認識できる形があったらいいのになあ。素因数を一目でわかるのが一番好きなところなんだけど、7以上の素数だとつい左上を見てカンニングしちゃうんだよね。7とか11とかに使う、もっとハッキリ見分けられる非正多角形とかないのかな？

ここでドットの位置のアルゴリズムについてどこかで質問して回答もらったんだけど（投稿に直接リンクできるかな？）、下の方にあるよ。円の上に配置するのは良い方法だと思うけど、特定の数字を特別に配置するには向かないかもね。それができないってわけじゃないけど、アルゴリズムはどうなるんだろう？編集：アニメーションをもうちょっと見てみたら、もしかしたら考え違いしてるかもしれない。まあ、作ってみようかな。

偶然じゃないだろうけど、2012年はStack ExchangeでMathematicaでこういうキレイな図を作る方法について質問が出てたんだって。https://mathematica.stackexchange.com/questions/11657/factor… そこに僕が少ないコードで図を作る回答を書いたんだ。質問で言及されてるリンクは記事と同じで今はもう見れないから、元々どこから来たのかは不明だよ。

4は素数じゃないよ。たぶん点をグループ化するのに二進数展開を使えるかも？
So, 1 is •
2 is ••
3 is
•
••5 is_•
••
••7 is
•
•_____•
••••11 is
•
•_____•
••••
••_••And so on.(つまり、2nはnをnの隣に置いて表現するけど、nが2の場合はnの上にnを置いて、2n+1は2nの上に1を置くって感じ)
代わりに、n角形の代わりに星を使うのも分かりやすいかも？

2（ペア）、3（三角形）、4（四角）、5（五角形）も、解像度が低い”円”みたいなもんじゃないの？
視覚化はただ一貫してるだけだよ。

うん、異論はないし今のままでもエレガントだよ、でも僕らの目とか脳の働きだと、七角形とか九角形とか三十角形とかはパッと見で識別するのすごく難しいんだよね。目的のためには非正規の形の方が向いてると思うな。

合計を使って分かりやすい描き方ができないかな？
7 = 23+1
11 = (22+1)*2+1
とかさ…

同意。しばらく大きな素数が出てくるの見てたけど、ちょっとがっかりしたよ。塗りつぶした多角形なら、もっと色んな形になるかもね。塗りつぶした六角形＝7とかさ…

これは素因数分解って呼ばれてると思うよ。それぞれの数は数のグループ（またはグループのグループとか…）に配置されるんだ。
例えば、24 -＞ 2 * 3 * 4 = 2つのグループの（3つのグループの（4つのアイテム））
あと、壊れたリンクのアーカイブ版はこれで試してみてね -＞ https://web.archive.org/web/20130206023100/http://mathlesstr…

4は素数じゃないことに注意してね。

百万年と百万とちょっと前のスレッド（いくつか解説リンク付き）だよ。
https://news.ycombinator.com/item?id=10776019
https://news.ycombinator.com/item?id=4788224

ありがとう！いくつか関連リンクだよ。
Factorizer - https://news.ycombinator.com/item?id=10776019 - Dec 2015 (30 comments)
Animated Factorisation Diagrams - https://news.ycombinator.com/item?id=4788224 - Nov 2012 (72 comments)
Animated Factorization Diagrams - https://news.ycombinator.com/item?id=4713048 - Oct 2012 (2 comments)

これ見てたら、特に高速でauditory synesthesiaって感覚になったよ。もし君もそうなら、このリンクの現象かもね: https://www.newscientist.com/article/dn14459-screensaver-rev…
古いコメントだけど、これに賛成！

8じゃランダム性には勝てないね！残念！
追記：昨日 https://news.ycombinator.com/submitted?id=imurray で再投稿ネタ探してたら、https://news.ycombinator.com/item?id=7984992 が面白そうだったから、もしよかったら再投稿をお願いするメール送るね :)

アニメーションがゆっくり再生されたら、グループや円の数を数えられていいな。新しい円が端から来て、追加が分かりやすく配置されるともっといい。それ以外は素晴らしいビジュアライゼーション！

すごくいいね。もし遅くできたり、数値をステップ実行できたりしたら嬉しいな。

隣り合う数へのジャンプが時々すごく劇的だよね—僕たちの数、ちゃんと正しい順序になってるのかな？

世界の加法的・乗法的な見方の違いだよ。数論はそのギャップを埋めようとしてる。シンプルな数の見方でもすぐ未知の世界に行ける。「一番簡単な難しい問題」Collatz conjectureもこの考え方から。乗法空間や加法空間でのステップがどこへ行くかって単純な問いが未解決問題につながるんだ。隣り合う数へのジャンプが劇的っていう観察だけで一生費やせる。まだ複素数や指数も出してないのにね！

一般の人が数の「乗法的な見方」にどうアプローチして、正しい直感を養えるんだろう？ practical（実用的）なのかな？

数字を乗法的に見る一番良い方法は、乗算を加算に変えることだよ。一般的なのはLogarithmで、log(a*b) = log(a) + log(b) だね。整数にはもっと強力な変換があって、Prime factorizationだ。Prime factorsに分けて、同じPrimeの指数を足せば乗算になる。手間だけど、Prime factorsはその整数のdivisibilityについて色々教えてくれるから価値はあるよ。乗算と加算の相互作用について深く知りたいなら、純粋数学の学位取って、数論をいっぱい学んで、その美しくなさに泣くといいよ。信じて、昔やったんだ。

僕は素人だけど…九九表とか足し算表を書き出してみて、パターンや違いを見つけると良いかもね（見つかるよ）。Sieve of Eratosthenesは良いよ。ChatGPTに高校代数は数学のどの分野か聞いたらfield theory of real numbersって言われて、それ以来groups and fieldsを見るのが楽しいんだ。前にUlam’s Spiralをいじったビデオ作ったんだ、Primeじゃなくて x mod n ≡ 0 の点をマークしたやつ。ちょっと変かな。リンクは[1][2][3]だよ。

何を言ってるかは分からないけど、例を挙げると16は2＾4だからグリッドみたいに並べられるけど、17はPrimeだから、代わりに円の上に17個の点を並べるしかないんだよ。