2,5で割り切れる回数のお話 - 素数大富豪が8121013倍強くなりたい

この記事は「合成数大富豪 Advent Calendar 2024 - Adventar」の16日目の記事になります。

こんにちは、アドベントカレンダーを入れ過ぎたことに早くも後悔しているOTTYです。
今日は割り切れる回数のお話です。主に、2,5で割り切れる回数の話になります。
合成数を探索するにあたって、2,5で割れる回数を調整したいことが多々あります。そのようなシーンで使える小技を紹介します。
また、実践上で2,5で割り切れる回数をド忘れしたときにその場で計算するテクニックにも活用できるはずです。特に後半で紹介する5Qチェックについてはそこそこ使えるはずです。

なお、この記事でnQ5のように書いたとき、nを1枚以上のトランプの札として1000*n+Q5を表しているものとします。

割り切れる回数の記号

$N$ が $p$ で割り切れる回数を $v_{p}(N)$ と表します。*1また、約束として $v_p(0)=\infty$ とします。

要するに、 $N$ は素因数分解したときのpの指数部分です。

例えば
$v_5(65)=1$
$v_2(128)=7$
$v_3(1213)=0$

$a,b$ を自然数とします。このとき以下が成り立ちます。

$v_{p}(a+b)\geq min\{v_{p}(a),v_{p}(b)\}$

$v_{p}(a\cdot b)=v_{p}(a)+v_{p}(b)$

特に $v_{p}(a)\neq v_{p}(b)$ のとき、

$v_{p}(a+b)=min\{v_{p}(a),v_{p}(b)\}$

が成り立ちます。この性質が今回のキモです。

これら性質は
$a=p^{v_{p}(a)}\cdot a'$
$b=p^{v_{p}(b)}\cdot b'$

として $a+b$ や $a\cdot b$ を考えることですぐに分かります。
かっこよく書いているだけですが、考えてみると当たり前ですね。
しかしこれは2,5で割り切れる回数を知りたいときに強力な性質です。

5の倍数

まず、簡単な5の倍数の方からいきます。

自然数 $C$ について

$C$ の末尾 $m$ 桁が $5^m$ で割れる $\iff$ $v_5(C)\geq m$

という分かりやすい性質があります。

例えば、 $v_5(nQ5)\geq 4$ となるようなnQ5を考えたいと思ったら、 $v_5(10^4)=4$ なので、末尾4桁を5^4で割れるようにしないといけません。
3Q5=5^5、8Q5=5^4*Kの頭に何つけても $v_5(nQ5)\geq 4$ とできます。

例:
93Q5=5^4*A49
68Q5=5^4*T9
Q8Q5=5^5*4A

別に末尾Q5にこだわりがないなら、6875=5^4*Jなどを末尾にすることも考えられますね。

合成数探索的には、上の命題を

$C$ の末尾 $m$ 桁が $5^m$ で割れない $\iff$ $v_5(C)< m$

と言い換えた方がわかりやすいかもしれません。

例えば末尾JQ5について考えましょう。

nJQ5=10^5*n+5^3*89より、

$v_{5}(nJQ5)=v_{5}(10000*n+5^3*89)=v_5(5^3*89)=3$

となります。どんなにnを大きくしても3回しか割れないのです。

｢nJQ5は5で3回しか割れない｣という事実は合成数大富豪的に使えます。

具体例を沢山挙げるのは後日しますが、6JQ5=5^3*4889のように、JQ5,5^3の部分を固定して派生させることができます。(さらに89が固定できるケースもある)

同様にnKQ5=5^5*2^5*n+5^4*3*7なので、 $v_5(nKQ5)=4$ です。*2

例:
9KQ5=5^4*3*487
QKQ5=5^4*3*647

札の組を結構固定できているため、nJQ5,nKQ5を探索してたくさん覚えるのは良さそうですね。

2の倍数

2で割り切れる回数については、すぐ"見える"こともあります。
ここでは\を入れたところで数を区切ることにします。

68\Q8

$v_{2}(68Q8)=v_{2}(68000+Q8)=v_{2}(68000)=v_{2}(68)+v_{2}(1000)=5$

T\448

$v_{2}(T448)=v_{2}(10000+448)=v_{2}(10000)=4$

64\88

$v_{2}(6488)=v_{2}(6400+88)=v_{2}(88)=3$

このように、2で割れる回数が異なるように区切ることのできる数は、容易に2で割る回数がわかります。
もちろん、\を入れる場所は例なので、6\8Q8、T4\48とか他の分け方はいくらでもあります。また、2で割り切れる回数が異なる二数の和として考えることで6488=6360+128などとしても良いです。

5の倍数と同じように、自然数 $C$ について

$C$ の末尾 $m$ 桁が $2^m$ で割れる $\iff$ $v_2(C)\geq m$

という性質があります。

2でたくさん割れる数を探したいときは、末尾 $m$ 桁を $2^m$ で割れるように固定して、その頭をうまいこと調整していくことでいい感じにできます。

例えば、末尾6桁をTKQで固定したら(TKQ=2^6*A583)、

nを奇数にすることで、nTKQが
$v_{2}(1000000*n)=6$ なので、 $v_{2}(nTKQ)\geq 6$ です。
さらに割る数が2のとき特有の性質として次が成り立ちます。

$a,b$ を自然数とします。 $v_{2}(a)= v_{2}(b)$ のとき、

$v_{2}(a+b)\geq v_{2}(a)+1$

これを適用することで、nが奇数の時、nTKQは最低7回は割れることになります。

例:
7TKQ=2^7*3A8493
9TKQ=2^K*J*TA

全く本題とは関係ないですが、9TKQ=2^K*J*TA強くてマジでおススメです。

nを偶数にすると、
$v_{2}(1000000*n)\geq 7$ となるため、 $v_{2}(nTKQ)=6$ が固定できます。

例:
8TKQ=2^6*Q6583
46TKQ=2^6*3^4*8893

おもろいですね。今はnTKQで探索していますが他にも色々と応用できそうです。nQ8、n888、nT88などなど各々が気に入ったものについて探索してみると発見がありそうです。(例は結構適当です。)

5Qチェック

末尾Qの数についてかなり重要だと思われるテクニックを紹介しておきます。
上で説明したことを用いただけなのですが、計算が単純かつそこそこ強力です。

末尾Qで2で割れる回数が9回以下の数に対して、5Qを引くことで2で割り切れる回数を判定できるテクニックとなります。

$nQ=100*(n-5)+512$ と考えることで、

$v_2(100*(n-5)) \neq v_2(512)$ ならば、

$v_2(nQ) = min(v_2(100*(n-5)),v_2(512))$

より、

$v_2(100*(n-5)) < 9$ ならば、

$v_2(nQ)=v_2(100*(n-5))=v_2(n-5)+2$

$v_2(100*(n-5))\geq 10$ ならば、

$v_2(nQ)=v_2(512)=9$

となります。

また、 $v_2(100*(n-5)) = v_2(512)$ ならば、

$v_2(nQ)\geq 10$

となります。

例:

T4Q=9900+512より、
$v_2(T4Q)=2$

J7Q=11200+512より、
$v_2(J7Q)=6$

3845Q=384000+512より、(384=128*3)
$v_2(384000)=v_2(384)+3=10$ より、
$v_2(3845Q)=v_2(512)=9$

このようなことが一瞬で分かります。これならド忘れしてもどうにかなりそうですし、合成数を覚えるにあたって使えそうです。

ただし、
$v_2(100*(n-5))= 9$ のときは、注意です。

389Q=2^J*A9などを考えると、

$v_2(38400)=9$ より、

$v_2(389Q)\geq 10$ しか保証しないです。(計算早ければ暗算で1024で割れたりする？)

しかし、3枚出しにおいてはK3Qを除くと、2^10で割れる合成数は存在しないので $v_2(100*(n-5))$ が元の数を2で割り切れる回数になります。
因みに明日のアドベントカレンダーでは末尾Qの合成数の性質について考えていきますが、5Qチェックと組み合わせることで高速な素因数分解を試みます。