階乗進法，素数階乗進法，e進法

更新 2023/07/11

2進法，10進法はなじみ深いと思います。この記事では，その仲間である「階乗進法」「素数階乗進法」「 $e$ 進法」について紹介します。

10進法の復習

10進法とは $a_3\times 10^3+a_2\times 10^2+a_1\times 10^1+a_0\times 10^0$ のことを $a_3a_2a_1a_0$ と表す方法でした。ただし，各 $a_i$ は $0\leqq a\leqq 9$ なる整数です。→二進法と十進法の変換方法と計算例

階乗進法

階乗進法とは， $a_3\times3!+a_2\times 2!+a_1\times 1!+a_0\times 0!$ のことを $a_3a_2a_1a_0$ と表す方法です。ただし，各 $a_i$ は $0\leqq a_i\leqq i$ なる整数です（そのため $a_0=0$ です）。

例

$13=2\times 3!+1\times 1!$ なので $13$ を階乗進法で表すと $2010$

性質

定理

任意の正の整数は1通りの階乗進数として表される。

証明の概要

$a_n$ までで表せる階乗進数の最大は $\displaystyle\sum_{k=1}^nk\cdot k!$ であるが，これがちょうど $(n+1)!-1$ と一致する(※)。そこから $1$ 増えると $(n+1)!$ になり， $a_{n+1}$ に繰り上がることからわかる（厳密には帰納法で定理1を証明できる）。

以下，※（つまり以下の等式）を証明する： $\displaystyle\sum_{k=1}^nk\cdot k!=(n+1)!-1$

数学的帰納法で示す。 $n=1$ のときは両辺 $1$ となり成立。

$n=t$ のとき成立すると仮定して， $n=t+1$ のときの左辺を計算すると，

$\displaystyle\sum_{k=1}^{t+1}k\cdot k!\\ =(t+1)\cdot(t+1)!+\displaystyle\sum_{k=1}^{t}k\cdot k!\\ =(t+1)\cdot(t+1)!+(t+1)!-1\\ =(t+2)!-1$

となり $n=t+1$ の場合の右辺と一致する。

素数階乗進法

正の整数 $n$ に対して， $n$ 以下の素数すべての積を $n\#$ と書き，素数階乗と呼びます。例えば， $7\#=7\times 5\times 3\times 2=210$ です。

素数階乗進法とは，階乗進法における「階乗」を「素数階乗」におきかえて係数 $a_i$ の範囲を調整したものです。つまり， $a_3\times(p_3\#)+a_2\times (p_2\#)+a_1\times (p_1\#)+a_0\times (p_0\#)$ のことを $a_3a_2a_1a_0$ と表す方法です。ただし，

$p_i$ は $i$ 番目の素数（かつ $p_0=1,p_0\#=1$ ）
各 $a_i$ は $0\leqq a_i< p_{i+1}$ なる整数です。

例

$55=1\times 30+4\times 6+0\times 2+1\times 1$ なので， $55$ を素数階乗進数で表すと $1401$

$a_i$ の範囲をうまいこと調整したおかげで以下の定理が成立します。

定理

任意の正の整数は1通りの素数階乗進数として表される。

証明

階乗進法の場合とほぼ同じ。 $a_n$ までで表せる素数階乗進数の最大は $\displaystyle\sum_{k=0}^n(p_{k+1}-1)\cdot (p_k\#)$ であるが，これがちょうど $(p_{n+1}\#)-1$ と一致する(※)。そこから $1$ 増えると $(p_{n+1}\#)$ になり， $a_{n+1}$ に繰り上がることからわかる。

以下，※（つまり以下の等式）を証明する： $\displaystyle\sum_{k=0}^n(p_{k+1}-1)\cdot (p_k\#)=(p_{n+1}\#)-1$

左辺のシグマの中身は $p_{k+1}\#-p_k\#$ である。よって，和を取ると途中の項が打ち消し合って $p_{n+1}\#-p_0\#=(p_{n+1}\#)-1$ が残る。

e進法

2進法，3進法，10進法などありますが，何進法が一番「効率が良い」か考えてみましょう。
NNN 進法で kkk ケタの数を表す場合を考えます。
0,1,2,...,N−10,1,2,...,N-10,1,2,...,N−1 を表す NNN 個の記憶素子が kkk ケタぶんで合計 NkNkNk 個必要です。
表現できる状態数は NkN^kNk です。情報量にすると I=log⁡2NkI=\log_2N^kI=log2​Nk です。→情報量の意味と対数関数を使う理由
よって，情報量 III を表現するのに必要な記憶素子の数は，
Nk=N×Ilog⁡2NNk=N\times\dfrac{I}{\log_2N}Nk=N×log2​NI​
これを最小にする NNN を求めると，
正の整数の範囲では N=3N=3N=3
実数の範囲では N=eN=eN=e
となります。つまり，ある意味で3進法は2進法よりも「効率が良い」といえます。さらに，整数でない進法を認めれば「eee 進法が効率が良い」ということもできます（上記の議論は NNN が整数であることを前提としているので，この主張は無理がありますが）。
参考：e進法（Wikipedia）
他にも黄金進法というものもあります。→黄金進法の意味とおもしろい定理
何に使うのかよくわかりませんが、おもしろい話題です。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！