ｅ進数

人力検索はてなのhttp://q.hatena.ne.jp/1137045651の質問に関して。

以下は２ＣＨの書き込みです。
「1桁あたりの複雑度と、ある数値を表現するのに必要な桁数とを考えると、自然対数の底e=2.7進数が一番効率が良いことは数学的に証明されてる。 」
どのように証明されているか、わかりやすく説明しているＨＰがあれば教えてください

http://pc8.2ch.net/test/read.cgi/tech/1016362068/

回答はe進数についてではなく、ｅそのものについてのようでした。
ｅ進数の効率が高いことについては、その２ｃｈの書き込みの中ほどに書いてありました。以下に引用します。

661 ：デフォルトの名無しさん ：03/04/20 12:42
> 660 こんな証明だったと思うけど、
N 進数で 数値 x を表のに必要な桁数は以下の d のようになる。
d = logN(x)
ここで、N 進数における x の表現効率 y を、
y = N * d = N * LogN(X)
と定義する。y が小さいほど効率が良いとする。

# y の妥当性の由来は N 進数 d 桁の計算回路の規模は y にほぼ比例すると考えてる
# ためだ。 もちろん、「少なくとも N レベルを瞬時に扱えるの非線形性を持つ素子を
# 使わない」というお約束はある。どうしても納得できなけりゃ回路を作って見る事だ。

x に対し y を最小にする N を考える。N で微分するので底を変換する。
y = N * LogN(x)
= N * Loge(x) / Loge(N) = Loge(X) * N / Loge(N)
N で微分すると、
y' = Loge(X) * ((1 * Loge(N) - N * (1/N)) / ((Loge(N))^2))
= Loge(X) * (Loge(N) - 1)( / ))*1(^2)
微分係数 y'=0 になる N を見つける。N=e の時に y'=0 は成立する。e ≒ 2.7182。
以上の議論により e 進数において x の表現効率は y は最も小さくなる。現実的な
選択として、N=2 または N=3 を選ぶことになる。


これでいいのだと思いますが、もう少し直感的にわかりやすく説明してみようと思います。

まず、数を表すための物を考えます。例えば、おはじきや小石のように同じものが幾つもあれば、それを使って数を表せます。ここでは◆で表して、ユニットと呼びます。ユニットはその個数で数を表すことができます。◆なら１で、◆◆なら２のようにです。
しかし、この方法だと表す数だけユニットが必要になります。１００を表すにはユニットが１００個必要になります。
これを効率的にするのに、ユニットを分けて表すことを考えます。◆◆と◆◆◆で２３を表すという具合です。
ただし、この方法を使うには０を表記する必要があります。そこで、◆を０、◆◆を１のようにユニットの個数と数の対応をずらします。各桁に１０個のユニットを割り当てれば０から９までの数を表せます。
この方法だと２０個のユニットで、０から９９まで１００通りの数が表せます。単にユニットの数で表す場合は、１００通りの数を表すのに１００個のユニットが必要なので、２０個のユニットで１００通りの数が表せるのはずいぶん効率のいい方法です。

◆　◆　＝０
◆　◆◆　＝１
◆　◆◆◆　＝２
◆◆　◆　＝１０
◆◆◆　◆　＝２０
◆◆◆◆◆　◆◆◆◆◆◆◆◆◆　＝４８
◆◆◆◆◆◆◆　◆◆◆◆◆◆◆◆　＝６７
◆◆◆◆◆◆◆◆◆◆　◆◆◆◆◆◆◆◆◆◆　＝９９

ユニットを分ける場合に１０個づつではなく、他の個数で分ける事もできます。例えば２０個のユニットを１桁に２個づつ分けて１０桁にした場合の数の表記を書いてみます。２個のユニットが２通りの数を表すわけで、２進数と考えられます。カッコの中の数字は２進数で表記した数です。

◆　◆　◆　◆　◆　◆　◆　◆　◆　◆　＝０　（０）
◆　◆　◆　◆　◆　◆　◆　◆　◆　◆◆　＝２　（１）
◆　◆　◆　◆　◆　◆　◆　◆　◆◆　◆◆　＝３　（１１）
◆　◆　◆　◆　◆　◆　◆◆　◆　◆◆　◆　＝１０　（１０１０）
◆　◆　◆　◆　◆　◆◆　◆　◆◆　◆　◆　＝２０　（１０１００）
◆　◆　◆　◆　◆◆　◆◆　◆　◆　◆　◆　＝４８　（１１００００）
◆　◆　◆　◆◆　◆　◆　◆　◆　◆◆　◆◆　＝６７　（１００００１１）
◆　◆　◆　◆◆　◆◆　◆　◆　◆　◆◆　◆◆　＝９９　（１１０００１１）


もっと大きな数も表せます。

◆　◆　◆◆　◆　◆　◆　◆　◆◆　◆◆　◆　＝１３４　（１００００１１０）
◆◆　◆　◆　◆◆　◆◆　◆◆　◆　◆◆　◆　◆　＝６２８　（１００１１１０１００）
◆◆　◆◆　◆◆　◆◆　◆◆　◆　◆◆　◆　◆　◆　＝１０００　（１１１１１０１０００）

各桁が２なので、２を桁数だけつまり１０回かけた１０２４通りの数を表すことができます。各桁に１０個を割り当てて２桁にした場合は１００通りなので、それよりも効率の良い方法だと考えられます。
それではもっと効率の良い方法はあるでしょうか。

１桁にｎ個のユニットを使うｎ進数を使うと、桁数は（ユニットの数）÷ｎになります。表せる数はｎを桁数回かけたものになります。ｎ回かけるということはｎ乗するということなので、ユニットの数をxとするとこうなります。
\large n^{\frac{x}{n}}通り
ユニットが２０個で計算すると
１０進数だと
\large 10^{\frac{20}{10}}=10^2=100通り
２進数だと
\large 2^{\frac{20}{2}}=2^{10}=1024通り
になります。
ユニットの数がｎで割り切れないと無駄になってしまうのですが、ユニットの数が多い場合は無駄になる割合も減ります。また
\large n^{\frac{x}{n}}=\left(n^{\frac{1}{n}}\right)^x
なのでユニットの数xに関係なく、ｎだけで効率を考えることができます。ｎに２から１０の数字を入れて\large n^{\frac{1}{n}}を計算してみます。

\large 2^{\frac{1}{2}}=1.4142\cdots
\large 3^{\frac{1}{3}}=1.4422\cdots
\large 4^{\frac{1}{4}}=1.4142\cdots
\large 5^{\frac{1}{5}}=1.3797\cdots
\large 6^{\frac{1}{6}}=1.3480\cdots
\large 7^{\frac{1}{7}}=1.3204\cdots
\large 8^{\frac{1}{8}}=1.2968\cdots
\large 9^{\frac{1}{9}}=1.2765\cdots
\large 10^{\frac{1}{10}}=1.2589\cdots


３の場合がもっとも大きくなるのがわかります。その次が２と４で、同じ大きさです。ユニットの数を含めた場合も計算してみます。ユニットの数が割り切れない場合は除いています。


３０個のユニットを使った場合
\large 2^{\frac{30}{2}}=2^{15}=32768
\large 3^{{\frac{30}{3}}=3^{10}=59049
\large 5^{\frac{30}{5}}=5^6=15625
\large 6^{\frac{30}{6}}=6^5=7776
\large 10^{\frac{30}{10}}=10^3=1000


２４個のユニットを使った場合
\large 2^{\frac{24}{2}}=2^{12}=4096
\large 3^{\frac{24}{3}}=3^8=6561
\large 4^{\frac{24}{4}}=4^6=4096
\large 6^{\frac{24}{6}}=6^4=1292
\large 8^{\frac{24}{8}}=8^3=512


ｎが整数でない場合にも効率を求める式\large n^{\frac{1}{n}}を計算することはできます。
自然対数の底ｅの場合に効率を求める式の計算結果が最大になることから、ｅ進数が一番効率が高いというこもできます。
\large e^{\frac{1}{e}}=1.4446\cdots
ただし、ユニットは自然数でしか分けることが出来ないので、自然数以外の進数にすることは出来ません。

また、自然数でなら自由に分けられるとも限らなくて、２つ１組でしか分けることの出来ないユニットの場合は奇数の進数を選択できません。無理に使おうとすれば、余計なユニットの為に効率が悪くなってしまいます。

*1:Loge(N