新訳・3の倍数を見つける方法

もう接頭辞が苦しくなってきた「約数見つけてみるヤツ」です。4回目。
・「3の倍数を見つける方法」
・「続・3の倍数を見つける方法」
・「新・3の倍数を見つける方法」
とやってきましたが、剰余使えばもっと早く桁を小さくできるやん…
と思いついたので、説明しまーす。

「あまり」を使うと…

基本的には今までの内容をちょっと拡張したいだけなので、新しいことは言わないです。

で、「あまり」。剰余ですな。

あまりの計算は整数を扱うときはめちゃくちゃ重要なんですよね。

んで、今回は

\[ある自然数nである自然数aを割った時のあまりをr_a、\\nである自然数bを割った時のあまりをr_bとしたとき、\\「(a+b)÷nのあまりは(r_a+r_b)になる」。\]

という性質を使ってやろうという魂胆。
この性質、合同式の性質で出てきますね。(俺は整数論やってないので、さっき知りました←)

性質使ってみる。

まぁつまりは、

\[n桁の整数N,任意の整数xについて、\\Nを10^k進法で\left\lceil\frac{n}{k}\right\rceil桁の整数と考えられるとき、\\m桁目に\frac{(x-l)^{m-1}}{(\frac{x}{10^k})^{n-m}}を掛け、\\その各桁の数の総和がlの倍数なら、Nはlの倍数\]

という演算をやった時、3行目で出せる多項式で総和を取る前に、
「各項を\(x\)で割って剰余をそれぞれ出し、その剰余の総和を取った時、『多項式の総和』と『剰余の総和』同士が法\(x\)で合同なんだから、『剰余の総和』の方使えば「判定するための値」の桁数減らせるやん！」
ということです。

前回、具体的な数字で試してたので、それを使って説明します！

こんな感じ。

「123456789」という整数は「9で割れんの？」って話だったんですが、
とりあえず、「1,23,45,67,89」と区切って、\(k=2\)としてやれば…

\[100-9=91\]

なので、各桁に\(91^{m-1}\)を掛けて多項式を作ると、

\[1×91^4+23×91^3+45×91^2+67×91^1+89×91^0=86285925\]

…まで出したのが前回の話。今回は、

\[1×91^4+23×91^3+45×91^2+67×91^1+89×91^0 \]

の各項を9で割って剰余を出して足す、という作業。

作業量は増えるけど、数字が小さいうちに作業できる点がメリット。
たぶんメモリの空間が狭くても行けんじゃね？的な。計算はしないよ！

では計算開始。
ここらへんも、合同式の性質をうまく使ってやると楽なんですよね。

ここで、プログラミング言語でよく見る「二項演算子”%”をつかった剰余演算」の表記法を借りてやると(「あまり」を一発で出せる演算、として使ってやると)、

$$91\%9=1$$

ということが正直パッと見で分かります。
そして合同式の性質から、

\[(91^2)\%9=1^2=1\\(91^3)\%9=1^3=1\\(91^n)\%9=1^n=1\]

という、超絶ラクチンな数字が出てくることが分かりました。
もう\(91^n\)の所はガン無視できそうです。

ということで、

\[1×91^4+23×91^3+45×91^2+67×91^1+89×91^0 \]

が

\[1+5+0+4+8=18\]

となり、18は9で割り切れるので、「123456789」は9で割り切れるということが分かりましたよ。

劇的に桁数が減ったよ！

単純に総和取るパターンでもそうですが、「9で割り切れる(かどうか)」以外の情報は切り捨ててしまっているので、
「18は2も約数である」ことは意味がないことに注意です。
「86285925は5も約数である」ことも意味がないです。よろしく。

とりあえず、判定が簡単になりました。

(簡単になるとは言っていない)

まぁ、資源が少なくても判定できそうじゃね？と思っての追記です。

アルゴリズムがこんな感じなのを組んで、超絶デカい整数を素因数分解できたりするんかな…とかいう夢を見ました。白昼夢です。

今回はそんな感じ！
整数って奥が深いね…
これで、中学受験で謎のデカい整数(デカい素数とデカい素数2つの積)を割らせる問題が出ても大丈夫だぞ！

という感じで〆ます。またこのあたりで思いついたら書きます。
ばーい👋