階乗進法の整数問題への応用
目次
- はじめに
- 階乗進法の定義と性質
- 整数問題への応用
- 整数問題への応用#2
- おわりに
1.はじめに
本記事は,階乗進法という概念を用いて整数問題の見通しをよくすることを目的としています.
2.階乗進法の定義と性質
階乗進法とは$n$桁目の重みが$ n!$で,仮数が$n$以下となるような位取り記数法である.
$n$桁目の重みを$(n-1)!$,仮数を$(n-1)$以下とする場合もあるが、これは結局一桁目が必ず$0$になってしまうため今回は省略する.
具体例を交えて確認していきましょう.
例えば,$2022=2 \cdot6!+4 \cdot5!+4 \cdot4!+1 \cdot3!+0 \cdot2!+0 \cdot1!$ であるから,${2022_{(10)}=244100_{(!)}}$ となる.
ここで、以下の命題を考えてみましょう.
整数をできるだけ少ない階乗数の和で表した時の階乗数の個数は,その整数を階乗進数に変換した時の各桁の総和に等しい.
整数$x$をできるだけ少ない階乗数の和で表した時に,$i!$を$i+1$回以上用いる場合よりも$(i+1)!$の階乗を用いたほうが用いる階乗数の和は少ない.したがって,整数$x$は$a_{k}\le k$なる正整数$a_{k}$を用いて以下のように表すことができる.
$$x=\sum_{k=1}^{n}a_{k}\cdot k!$$
これは、階乗進数の定義そのものであるので題意は示された.
任意の正整数を階乗進数に変換する方法は一意である.
階乗進数が一意に表せることは,
$$\sum_{k=1}^{n}k\cdot k!+1=\left(n+1\right)!$$
が成り立つことと同値である.したがって,上記の式を示せばよい.
数学的帰納法で示す.$n=1$の時、明らかに成立する.$n=l$とし、$n=l+1$での成立を示す.
$$
\begin{align*}
\sum_{k=1}^{l+1}k!\cdot k+1 & =\sum_{k=1}^{l}k\cdot k!+1+\left(l+1\right)\cdot\left(l+1\right)!\\
& = \left(l+1\right)!+\left(l+1\right)\cdot\left(l+1\right)! \\
& = \left(l+1\right)!\cdot\left(l+2\right) \\
& = (l+2)!
\end{align*}
$$
したがって,題意は示された.
事前準備は以上です.整数問題へ応用していきます.
3.整数問題への応用
$x!+y!+z!=2^n$ を満たすような正整数$x,y,z,n$の組を全て求めよ.
解説
$n \leq 2$の場合,$(x,y,z,n)=(1,1,2,2)$とその並び替えが解になることは容易にわかります.したがって,以下では$3 \leq n$の場合を考えていきます.
条件式を満たすような正整数の組を求めることは,階乗進数に変換した時に各桁の総和が3以下であるような$2^n$を求めることと同値です.
$2^n$を階乗進数に変換して何か法則性がないか実験してみましょう.
| $n=$ | $2^n_{(!)}$ |各桁の総和|下四桁|
| --- | --- |||
| 3 | 110 |2|0110|
| 4 | 220 |4|0220|
| 5 | 1110 |3|1110|
| 6 | 2220 |6|2220|
| 7 | 10110 |3|0110|
| 8 | 20220 |6|0220|
| 9 | 41110 |7|1110|
| 10 | 122220 |9|2220|
実験より,下四桁がループしていることがわかると思います.ループを構成する要素には,$0110,0220,1110,2220$の四つがあり,それぞれ各桁の和は$2,4,3,6$となります.ループしていることが事実であれば,下四桁が$0220,2220$の場合は解にならないということがわかります.では,ループしていることを示していきます.
階乗進数の下四桁を10進数に変換したものは120で割った余りと等しい.したがって、$n \geq3$の範囲で$2^n$が$mod120$でループすることを示せば良い.
$$
\begin{align*}
2^{3}\equiv 2^{7}\ \left(\operatorname{mod}\ 120\right)
\end{align*}
$$
となって、周期4のループを構成する.
したがって,ここでは階乗進数表記での下四桁が$0110,1110$の二パターンを考えれば良いです.順に(A),(B)と名付けましょう.
(A). 下四桁が$1110$のとき,$n \equiv 1 (mod4)$となります.さらに,下四桁が$1110$で各桁の総和が$3$以下であるためには桁数が$4$以下でないといけません.したがって,(A)においての$n$の存在範囲は$n \leq 6$となります.$n \leq 6$かつ,$n \equiv 1 (mod4)$となるような$n$は$5$のみであり,$n=5$を代入して計算すると,$(x,y,z,n)=(2,3,4,5)$とその並び替えが解となることがわかります.
(B). 次に,下四桁が$0110$のパターンです.このパターンのとき,$n \equiv 3 (mod4)$となります.ここで,解の存在範囲が有限であることを示していきます.下五桁目が$0$でなく桁数が$6$以上だとしたら,必ず二桁目と三桁目以外に$0$でないような桁が二つ存在するので各桁の総和は$4$以上となります.今回はこの方針で示していきます.
(B)において,$n \equiv 3 (mod4)$なので,正整数$k$を用いて$n=4k+3$と置くことができる.また,(B)における下五桁目が$0$となることは,$2^{4k+3}\equiv2!+3!=8\ \left(\operatorname{mod}720\right)$の解が存在することと同値である.ここで,そのような解が存在しないことを示す.
$$
\begin{align*}
2^{4k+3}\equiv 8\ \left(\operatorname{mod}720\right)\\
8 \cdot16^k \equiv8 (mod 720) \\
16^k \equiv1 (mod 90)
\end{align*}
$$
$16^k\equiv 1 (mod90)$となるような正整数kは存在しないことから題意は示された.
(B)における下五桁目が$0$でないことが示せたので,$2^n_{(!)}$が$6$桁となるような$n$の範囲を求めてあげれば良いです.先ほどの表より,$n \geq10$のときに$6$桁となるので,(B)においての$n$の存在範囲は$n < 10$かつ,$n \equiv 3 (mod4)$となります.これを満たすような$n$は$3,7$のみであり,実際に代入して調べると,$(x,y,z,n)=(1,1,3,3),(2,3,5,7)$とその並び替えが解になっていることがわかります.
したがって,求める$x,y,z,n$の組は$(x,y,z,n)=(1,1,2,2),(1,1,3,3),(2,3,4,5),(2,3,5,7)$とその並び替えとなります.
4.整数問題への応用#2
$n,k$は任意の$3$以上の整数とする.この時,$n^{k!}-1$は少なくとも$k$個の約数を持つことを示せ.
解説
約数の個数はその素因数がわかる必要があります.しかし,$n,k$は不定であり愚直に素因数分解をすることはできません.さらに余りを取ったり不等式を考えることもできませんね.そこで初心に帰って,今回の方針は「強引に因数分解する」でいきましょう.とりあえず,$x^n-y^n$型の因数分解の公式を適用してみましょう.
$$ n^{k!}-1^{k!}=\left(n-1\right)\left(n^{k!-1}+n^{k!-2}+\cdots+n^{2}+n+1\right) $$
つまり,$n^{k!-1}+n^{k!-2}+\cdots+n^{2}+n+1$が$k-1$個の因数に分解されることを示せばゴールですね.この式を因数分解するのは難しそうですね.しかし,指数が$k!-1$というところがポイントです.ここで,以下の補題を示します.
$n,k$を正整数とする.この時,以下の式が成立する.
$$\sum_{k=0}^{n!-1}x^{k}=\prod_{i=1}^{n-1}\sum_{j=0}^{i}x^{j\cdot i!}$$
$(右辺)=(1+x^{1!})(1+x^{2!}+x^{2\cdot 2!})\cdots(1+x^{(n-1)!}+x^{2(n-1)!}+\cdots+x^{(n-1)(n-1)!})$
であり,任意の非負整数$m$に対して$x^{m}$の係数は階乗進法の一意性より,$1$であるので題意は示された.
この補題より,$$\sum_{h=0}^{k!-1}n^{k}=\prod_{i=1}^{k-1}\sum_{j=0}^{i}n^{j\cdot i!}$$
であるから,与式は$k$個の因数を持つ.さらに,$k$個の因数は明らかに全て値が異なるから題意は示された.
5.おわりに
本記事では階乗進数という考え方を導入して整数問題最後を解いていきました.階乗進数という考え方がなくても合同式を使えば解ける問題でしたが,見通しはかなり悪くなると思います.
この記事は私,Metachick の初めての記事でもあるので一応,最後に簡単に自己紹介をして終わりたいと思います.私はMathlogにいるみなさんのように数学つよつよerではないただの一般人で、趣味で競技数学をメインに記事を書きたいと思っています.競技数学の経験は浅く,OMCも水色ですが競技数学の魅力を伝えられたらなと思います.
ミスなどがあれば指摘していただけるとありがたいです.最後まで見ていただいてありがとうございました!