8 : 26 10^nの階乗: 桁数と末尾の0の個数

← 8 - 25 p↑ もくじ i 8 - 27 n →

10nの階乗の末尾の0の個数

2004年 1月20日
記事ID d40120

パズル(Treebeard's Stumper Answer): 1×2×3×…×1000を計算すると、40238726から始まる2568桁の数になり、 その数の末尾には0が249個並びます(実際に試す)。 また、10000までかけると、末尾に0が2499個並ぶ数になります。以下、末尾のゼロの数は
10万までで: 24999
100万までで: 249998
1000万までで: 2499999
1億までで: 24999999
となるのですが、100万までかけたときだけ、 なぜか249999個でなく1つ少ない249998個になっています。 なぜ100万のときは、1つずれるのでしょう。

リンク先では、この現象が指摘され「不思議だ」と書いてある。 以下では、理由を解明する。 パズルを楽しみたいかたは、読まないようにしてください。

最初のメモ (2004-01-19)

Treebeard's Stumper Answerにおもしろい話が出ている。 10!は末尾に0が2個つく。 100!は24個、 1000!は249個、 10000!は2499個、 100000!は24999個。24999…というパターンが見て取れる。 ところが百万の階乗の末尾の0は、なぜか249998個なのである。 そして千万!では、ふたたび2499999個に戻る。 本当だとしたら、まさに What is that 8 doing in 1,000,000!? だ。 これは解明せねばなるまい。いかにもふしぎで、ちょっと考えれば分かりそうな適度な難しさがいい感じ。 理由を知りたいのではなく解明を楽しみたいので、答えを知っていてもネタバレしないでね★

手元でも実験してみました
Bigint.getFactorialTrailingZeros
DEBUG: 1000 : 249
DEBUG: 10000 : 2499
DEBUG: 100000 : 24999
DEBUG: 1000000 : 249998
DEBUG: 10000000 : 2499999
DEBUG: 100000000 : 24999999
DEBUG: 1000000000 : 249999998
DEBUG: 10000000000 : 2499999997
DEBUG: 100000000000 : 24999999997
DEBUG: 1000000000000 : 249999999997
DEBUG: 10000000000000 : 2499999999997

先に行くほど全般的には25***との差が増える
DEBUG: 2  (1-digit)
DEBUG: 24  (2-digit)
DEBUG: 249  (3-digit)
DEBUG: 2499  (4-digit)
DEBUG: 24999  (5-digit)
DEBUG: 249998  (6-digit)
DEBUG: 2499999  (7-digit)
DEBUG: 24999999  (8-digit)
DEBUG: 249999998  (9-digit)
DEBUG: 2499999997  (10-digit)
DEBUG: 2 4999999997  (11-digit)
DEBUG: 24 9999999997  (12-digit)
DEBUG: 249 9999999997  (13-digit)
DEBUG: 2499 9999999998  (14-digit)
DEBUG: 24999 9999999997  (15-digit)
DEBUG: 249999 9999999996  (16-digit)
DEBUG: 2499999 9999999995  (17-digit)
DEBUG: 24999999 9999999995  (18-digit)
DEBUG: 249999999 9999999995  (19-digit)
DEBUG: 2499999999 9999999996  (20-digit)
DEBUG: 2 4999999999 9999999997  (21-digit)
DEBUG: 24 9999999999 9999999995  (22-digit)
DEBUG: 249 9999999999 9999999994  (23-digit)
DEBUG: 2499 9999999999 9999999993  (24-digit)
DEBUG: 24999 9999999999 9999999995  (25-digit)
DEBUG: 249999 9999999999 9999999992  (26-digit)
DEBUG: 2499999 9999999999 9999999992  (27-digit)
DEBUG: 24999999 9999999999 9999999994  (28-digit)
DEBUG: 249999999 9999999999 9999999992  (29-digit)
DEBUG: 2499999999 9999999999 9999999990  (30-digit)
DEBUG: 2 4999999999 9999999999 9999999990  (31-digit)
DEBUG: 24 9999999999 9999999999 9999999992  (32-digit)
DEBUG: 249 9999999999 9999999999 9999999994  (33-digit)
DEBUG: 2499 9999999999 9999999999 9999999993  (34-digit)
DEBUG: 24999 9999999999 9999999999 9999999992  (35-digit)
DEBUG: 249999 9999999999 9999999999 9999999992  (36-digit)
DEBUG: 2499999 9999999999 9999999999 9999999990  (37-digit)
DEBUG: 24999999 9999999999 9999999999 9999999993  (38-digit)
DEBUG: 249999999 9999999999 9999999999 9999999991  (39-digit)
DEBUG: 2499999999 9999999999 9999999999 9999999991  (40-digit)
DEBUG: 2 4999999999 9999999999 9999999999 9999999990  (41-digit)
DEBUG: 24 9999999999 9999999999 9999999999 9999999989  (42-digit)
DEBUG: 249 9999999999 9999999999 9999999999 9999999990  (43-digit)

答え (2004-01-20)

問題(再掲)

n=3, 4, …, 7 に対して 10n! の末尾の0の個数は 249, 2499, 24999, 249998, 2499999 である。なぜ106のときは 249999 にならないか。

10n! の末尾の0の個数と 10n/4 との差は、 無限級数和:
10n/4 = Σ( 2k・10n-k ), for k=1→∞
について、右辺各項の小数部分を切り捨てたときの誤差に等しい。
この誤差 SF を評価せよ。
SF = 1 for n = 3, 4, 5, 7
SF = 2 for n = 6
である。(終わり)

説明

末尾の0の数とはその数が10で何回割り切れるかだが、 階乗を因数分解すると、因子2は十分にたくさんあるから、 10で何回割れるかは、因子5の数に等しい。例えば、もし因子5がちょうど100個あれば、10で100回割り切れ、末尾に0が100個つく。

因子5の発生原因は、5の倍数で、階乗のかけ算のなかに5の倍数が出たら1個、 ただし25の倍数が出たら2個、 ただし125の倍数が出たら3個…ずつ因子が増える。したがって、
Int[ (10^n) / (5^s) ], for s=1, 2,...
という形の項の整数部分を、その整数部分が初めて0になる直前まで足すわけである。 5^s は 5, 25, 125, 625, ... という形の数であり、 10^n 型の数をそれらで割ると、2, 4, 8, 16, ... と2のべきになることに注意すれば、 具体的には次のような計算となる。ただし各項は小数点以下切り捨てる。

2*1 = 2
2*10 + 4*1 = 24
2*100 + 4*10 + 8*1 + 16*0.1 = 249
2*1000 + 4*100 + 8*10 + 16*1 + 32*0.1 = 2499
2*10000 + 4*1000 + 8*100 + 16*10 + 32*1 + 64*0.1 + 128*0.01 = 24999
2*100000 + 4*10000 + 8*1000 + 16*100 + 32*10 + 64*1 + 128*0.1 + 256*0.01 = 249998
2*1000000 + 4*100000 + 8*10000 + 16*1000 + 32*100 + 64*10 + 128*1
 + 256 * 0.1 + 512*0.01 + 1024*0.001 = 2499999

この時点で、すでに
249, 2499, 24999, 24998, 2499999
という数列が確認される。 もし小数点以下切り捨てを行わず、したがって項が1未満になっても無限に足し算をすれば、 250... になるに違いない。 この数列の末尾が8になったり9になったり揺れるのは、 「切り捨てなしで無限に足した場合」と比べての誤差の問題なのである。 具体的には、次のような、収束する無限級数和と関係ある。

1/4 = Σ( 2^i / 10^i ) , for i = 1→∞

もう少し問題に即して言うと、次の級数和である。

(1/4)*(10^n) = Σ( ( 2^i ) * ( 10^(n-i) ) ), for i=1→∞

この無限級数の和を、上記のように近似した場合の、誤差の評価が、この問題の本質だ。 どのような近似を行っているか分析してみよう。 われわれは、この式の右辺各項
( ( 2^i ) * ( 10^(n-i) ) )
について、次の規約で近似計算を行っているのである。
規約1: この項が整数ならば誤差はなく、
規約2: この項が小数部分を含み、整数部分が1以上なら、小数部分を切り捨て、
規約3: この項が小数部分を含み、整数部分が0になったら、その項以降は打ち切る。
規約3は規約2から出ることだが、無限ループから抜ける重要ポイントなので、このように書いておく。 すると、打ち切り誤差と丸め(実際には常に切り捨て)誤差の両方が誤差評価に寄与することになる。

しかしながら、規約1は誤差を増加させないし、規約3は誤差を減少させないから、 誤差側に落ちるか主値側に落ちるかの鍵を握るのは、真ん中の規約2である。 規約2の適用が始まってから、規約3による打ち切りが実行されるまでの「最後のあがき」のあいだに、 どれだけ整数部分をかき集められるかが、最終結果に響く。

nを3以上とする。この項が小数部分を含むようになる最初の場所以降だけを考えると、次のような具合になっている。

n=3
DEBUG: Thrown Away from 1.6 : 0.6
DEBUG: Thrown Away from 0.32 : 0.32
DEBUG: Thrown Away from 0.064 : 0.064
DEBUG: Thrown Away from 0.0256 : 0.0256
...

これらの項を無限に足せば総和は明らかに2であるが、規約2によって、1.6の1は誤差にならない。 つまり「上記の範囲とそれ以降の総和」2のうち、整数部分に現れた1だけが救われて、 残りの1は「どさくさの摩擦熱」で散逸してしまう。もう一つ例をみよう。

n=4
DEBUG: Thrown Away from 3.2 : 0.2
DEBUG: Thrown Away from 0.64 : 0.64
DEBUG: Thrown Away from 0.128 : 0.128
DEBUG: Thrown Away from 0.0256 : 0.0256
...

この範囲とそれ以降の総和4のうち、3だけが整数部分として救われ、残りの1が摩擦熱で逃げる。 この摩擦熱のため、理想値2500にはわずかに及ばず、最終結果が2499となる。

n=5
DEBUG: Thrown Away from 6.4 : 0.4
DEBUG: Thrown Away from 1.28 : 0.28
DEBUG: Thrown Away from 0.256 : 0.256
DEBUG: Thrown Away from 0.0512 : 0.0512
...
総和: 8
整数部分: 7
残差: 1
結果: 24999

n=6
DEBUG: Thrown Away from 12.8 : 0.8
DEBUG: Thrown Away from 2.56 : 0.56
DEBUG: Thrown Away from 0.512 : 0.512
DEBUG: Thrown Away from 0.1024 : 0.1024
...
総和: 16
整数部分: 14
残差: 2
結果: 249998

n=7
DEBUG: Thrown Away from 25.6 : 0.6
DEBUG: Thrown Away from 5.12 : 0.12
DEBUG: Thrown Away from 1.024 : 0.024
DEBUG: Thrown Away from 0.2048 : 0.2048
...
総和: 32
整数部分: 31
残差: 1
結果: 2499999

n=8
DEBUG: Thrown Away from 51.2 : 0.2
DEBUG: Thrown Away from 10.24 : 0.24
DEBUG: Thrown Away from 2.048 : 0.048
DEBUG: Thrown Away from 0.4096 : 0.4096
...
総和: 64
整数部分: 62
残差: 2
結果: 24999998

(1/4)*(10^n) との差が1だったり2だったりあるいはそれ以上だったりするのは、 項に小数部分が現れてから、整数部分が0になるまでの整数と小数が摩擦を起こす期間における、 整数部分として回収できる反応熱と、 小数部分として逃げてしまう摩擦熱との、バランスであることが分かる。 小数点の向こうに落ちてしまったエネルギーは、すべて摩擦熱として失われてしまう。 移行期が長引けば長引くほど摩擦が起こる場所が増えるので、 桁数が伸びれば伸びるほど、 欠損は全般的には大きくなる。

摩擦熱による損失の第0近似を得るために、次のように書いてみよう。

n=3
DEBUG: Thrown Away from 200 : 0
DEBUG: Thrown Away from 40 : 0
DEBUG: Thrown Away from 8 : 0
DEBUG: Thrown Away from 1.6 : 0.6

n=4
DEBUG: Thrown Away from 2000 : 0
DEBUG: Thrown Away from 400 : 0
DEBUG: Thrown Away from 80 : 0
DEBUG: Thrown Away from 16 : 0
DEBUG: Thrown Away from 3.2 : 0.2

n=5
DEBUG: Thrown Away from 20000 : 0
DEBUG: Thrown Away from 4000 : 0
DEBUG: Thrown Away from 800 : 0
DEBUG: Thrown Away from 160 : 0
DEBUG: Thrown Away from 32 : 0
DEBUG: Thrown Away from 6.4 : 0.4

n=6
DEBUG: Thrown Away from 200000 : 0
DEBUG: Thrown Away from 40000 : 0
DEBUG: Thrown Away from 8000 : 0
DEBUG: Thrown Away from 1600 : 0
DEBUG: Thrown Away from 320 : 0
DEBUG: Thrown Away from 64 : 0
DEBUG: Thrown Away from 12.8 : 0.8

n=7
DEBUG: Thrown Away from 2000000 : 0
DEBUG: Thrown Away from 400000 : 0
DEBUG: Thrown Away from 80000 : 0
DEBUG: Thrown Away from 16000 : 0
DEBUG: Thrown Away from 3200 : 0
DEBUG: Thrown Away from 640 : 0
DEBUG: Thrown Away from 128 : 0
DEBUG: Thrown Away from 25.6 : 0.6

これで明らかなように、初めて摩擦が起き、規約2が適用される「どさくさ期間」の入り口は、
2**(n+1) / 10
という項である。この項の小数部分を、摩擦熱による損失の第0近似とすることができる。 つまり、Frac() で負でない実数の小数部分を表すとして、
Frac( 2**(n+1) / 10 )
が大きいと、摩擦熱の小さい「高効率反応」の望みは絶たれる。 n が大きい場合、この項が小さくても残りの摩擦期間で損がいくらでも積もるから少しも安心できないが、 それでも、この項が大きければ、失われる摩擦熱がそれだけ大きくなることは確実だ。 摩擦すればするほど損害は増える一方なので、とにかく入り口で大損してしまうと、もう回復の見込みはない。 n=6の場合、いきなり12.8でここで0.8失われる。 よって、第0近似の段階では、温度が周囲より低くなる。 そしてこのような小さい n では、摩擦熱による損失は1か2なので、 1になるか2になるか占ううえで0.8の寄与は重大であり、 結果として、最初の項だけでみる第0近似でも、ある程度の判断が可能なのである。 n=6のときの特異性だけを取り立てていうなら、要するに
2**(6+1)=128の1の位が周囲より大きい
ということだ。

n     exp  last digit          Loss       Total
3:     16: 6                      1:       249
4:     32: 2                      1:      2499
5:     64: 4                      1:     24999
6:    128:[8] <-- Bigger --->    [2]:   249998 <-- Lost more
7:    256: 6                      1:   2499999

質問: なぜ 1000000! の末尾の0の数は249999でなく249998か?
答え: 16, 32, 64, 128, 256の1の位: 6, 2, 4, 8, 6 の8は周囲より大きいから。

もっと正確に言えば、128/10 = 12.8 の小数部分で 0.8 もロスし、さらに次の 256/100 = 2.56 の小数部分として 0.56 を失うので、 このダブルパンチの結果、ロスのトータルが1を超えてしまうのである。 0の個数は整数だから、ロスが1を超えると、結局2が失われる(ロスの合計が2は超えないとして)。 このようにして、100万の階乗は、「周囲のみんな」と比べて末尾の0が1個少なくなってしまう。

以上をまとめると、失われる危険性のある「微妙なエネルギー量」の総和は
S = Σ 2**(n+i) / (10**i)
であり、そのうち、失われる手前で何とか回収できるのは
SI = Σ Int( 2**(n+i) / (10**i) )
であり、反応の摩擦熱として永遠に失われてしまう部分は
SF = Σ Frac( 2**(n+i) / (10**i) )
である。ここで i は 1 から∞を走るが、整数部分が0になったら、もう SI は増えようがないから、 そこで打ち切って SF = S - SI としても同じことである。 なお、上記の第0近似とは、SFを初項だけ直接計算したものである。 S 自身は「初項より大きく、その2倍よりは小さい範囲の2のべき」として計算できる。 n=3 のとき S=2 であり、n が1大きくなると初項は2倍になるので、結局、もっと直接的に、

S = 2^(n-2)

以上によって、「末尾の0の個数が(1/4)*(10^n)よりどれだけ小さくなるか」を具体的に計算してみよう。

n = 3
S = 2
si = Int( 1.6 ) + Int( 0.32 ) + ... = 1
sf = 2 - 1 = 1

n = 4
S = 4
si = Int( 3.2 ) + Int( 0.64 ) + ... = 3
sf = 4- 3 = 1

n = 5
S = 8
si = Int( 6.4 ) + Int( 1.28 ) + Int( 0.256 ) + ... = 7
sf = 8 - 7 = 1

n = 6
S = 16
si = Int( 12.8 ) + Int( 2.56 ) + Int( 0.512 ) + ... = 14
sf = 16 - 14 = 2 <--- 大きくなる
なぜ大きくなるかというと、12.8の丸め誤差0.8と2.56の丸め誤差0.56の和が1を超えるから

n = 7
S = 32
si = Int( 25.6 ) + Int( 5.12 ) + Int( 1.024 ) + Int( 0.2048 ) + ... = 31
sf = 32 - 31 = 1

SIはとても小さい整数であるから、 このアルゴリズムなら、bigint.js を使うまでもなく、 通常の浮動小数点演算で、n=52程度まで、(10**n)!の末尾の0の個数を直接決定することができる。

Number of the Trailing Zeros in Factorial(10^n)
Calculated by JavaScript
# The number is equal to (1/4)*(10^n) - loss

n =  3: loss =  1: 249
n =  4: loss =  1: 2499
n =  5: loss =  1: 24999
n =  6: loss =  2: 249998
n =  7: loss =  1: 2499999
n =  8: loss =  1: 24999999
n =  9: loss =  2: 249999998
n = 10: loss =  3: 2499999997
n = 11: loss =  3: 24999999997
n = 12: loss =  3: 249999999997
n = 13: loss =  3: 2499999999997
n = 14: loss =  2: 24999999999998
n = 15: loss =  3: 249999999999997
n = 16: loss =  4: 2499999999999996
n = 17: loss =  5: 24999999999999995
n = 18: loss =  5: 249999999999999995
n = 19: loss =  5: 2499999999999999995
n = 20: loss =  4: 24999999999999999996
n = 21: loss =  3: 249999999999999999997
n = 22: loss =  5: 2499999999999999999995
n = 23: loss =  6: 24999999999999999999994
n = 24: loss =  7: 249999999999999999999993
n = 25: loss =  5: 2499999999999999999999995
n = 26: loss =  8: 24999999999999999999999992
n = 27: loss =  8: 249999999999999999999999992
n = 28: loss =  6: 2499999999999999999999999994
n = 29: loss =  8: 24999999999999999999999999992
n = 30: loss = 10: 249999999999999999999999999990
n = 31: loss = 10: 2499999999999999999999999999990
n = 32: loss =  8: 24999999999999999999999999999992
n = 33: loss =  6: 249999999999999999999999999999994
n = 34: loss =  7: 2499999999999999999999999999999993
n = 35: loss =  8: 24999999999999999999999999999999992
n = 36: loss =  8: 249999999999999999999999999999999992
n = 37: loss = 10: 2499999999999999999999999999999999990
n = 38: loss =  7: 24999999999999999999999999999999999993
n = 39: loss =  9: 249999999999999999999999999999999999991
n = 40: loss =  9: 2499999999999999999999999999999999999991
n = 41: loss = 10: 24999999999999999999999999999999999999990
n = 42: loss = 11: 249999999999999999999999999999999999999989
n = 43: loss = 10: 2499999999999999999999999999999999999999990
n = 44: loss =  9: 24999999999999999999999999999999999999999991
n = 45: loss = 10: 249999999999999999999999999999999999999999990
n = 46: loss =  9: 2499999999999999999999999999999999999999999991
n = 47: loss = 11: 24999999999999999999999999999999999999999999989
n = 48: loss = 11: 249999999999999999999999999999999999999999999989
n = 49: loss = 11: 2499999999999999999999999999999999999999999999989
n = 50: loss = 11: 24999999999999999999999999999999999999999999999989
n = 51: loss = 12: 249999999999999999999999999999999999999999999999988
n = 52: loss = 13: 2499999999999999999999999999999999999999999999999987

上の表を見れば、 (1/4)*(10^n) に対する誤差 loss の評価が本質的であることが分かる。 ここで、例えば、
n = 10: loss = 3: 2499999997
というのは、
1×2×3×4×…×10000000000
を計算すると、末尾に0が24億9999万9997個つく整数になることを意味する。 ロスが3というのは、25億きっかりより3小さいという意味。 スターリンの近似式によると、この数自身は、およそ 2.3257e+95657055186 であり、 956億桁である。計算に間違いがないとすると、末尾約2.5%は全部ゼロということになる。

問題: 956億桁の数を計算できたとして、結果をテキストファイルに書き出したとする。数字1文字が1バイトとした場合、 あなたのマシンのHDにこのファイルを格納できるかどうか調べよ。 次にこのファイルをエディタでオープンできたとして、毎秒10個ずつ数字に目を走らせたとする。 残りの人生のすべてをかけて不眠不休でやったとして、この方法で956億桁の数字を読み終わる可能性はどのくらいあるか。 もし最後までが無理なら、だいたい何パーセントくらい読んだあたりで死ぬことになるか。 ただし、マシンはあなたの身体より長持ちすると仮定する。

追記 (2004-01-22)

54ビット浮動小数点演算で上記 loss を正確に決定できるのは、 n = 53 までである。

n = 54 に対する SI の第一項は、浮動小数点演算では
Math.floor( Math.pow( 2, 54 + 1 ) / 10 ) = 3602879701896397
であるが、正確な値は、
Bigint.div( Bigint.pow( 2, 54 + 1 ), 10 ) = 3602879701896396
である。この結果、浮動小数点演算では、正しい答えと1ずれる。
255 = 3602879 7018963968
の精度が失われ、36028797018963970 に丸められてしまうためである。 JavaScript は 253 までは整数解像度があるから、 n=52 までは精度が保証される。n = 53 の場合の
254 = 18014398509481984
については「たまたま」精度が失われない。

bigint.js v0.5 を使えば、さらに大きい n について正確な答えを得ることができる。

--- Number of the Trailing Zeros in Factorial(10^n) ---
bigint.js v0.5 beta 21-pre

n = 50 : 2499999999 9999999999 9999999999 9999999999 9999999989  (50-digit)
n = 51 : 2 4999999999 9999999999 9999999999 9999999999 9999999988  (51-digit)
n = 52 : 24 9999999999 9999999999 9999999999 9999999999 9999999987  (52-digit)
n = 53 : 249 9999999999 9999999999 9999999999 9999999999 9999999987  (53-digit)
n = 54 : 2499 9999999999 9999999999 9999999999 9999999999 9999999988  (54-digit)
n = 55 : 24999 9999999999 9999999999 9999999999 9999999999 9999999986  (55-digit)
n = 56 : 249999 9999999999 9999999999 9999999999 9999999999 9999999990  (56-digit)
n = 57 : 2499999 9999999999 9999999999 9999999999 9999999999 9999999986  (57-digit)
n = 58 : 24999999 9999999999 9999999999 9999999999 9999999999 9999999983  (58-digit)
n = 59 : 249999999 9999999999 9999999999 9999999999 9999999999 9999999985  (59-digit)
n = 60 : 2499999999 9999999999 9999999999 9999999999 9999999999 9999999987  (60-digit)
...

この記事のURL

テキスト版省パケ版XML版


10nの階乗の桁数

2004年 1月21日
記事ID d40121

1010! は 95657055187桁ある。この桁数の頭の9をとった5657055187は、 1 - log10 e = 0.565705518...と数字の並び方がそっくりだ。なぜだろうか?

初めに

10nの階乗の末尾の0の個数に関連して、 10nの階乗の桁数 d を考えてみよう。 例えば、n = 2 として、
102! = 100! = 93326215 4439441526 8169923885 6266700490 7159682643 8162146859 2963895217 5999932299 1560894146 3976156518 2862536979 2082722375 8251185210 9168640000 0000000000 0000000000
これは158桁ある。だから、n = 2 のとき d = 158 だ。

n を少しずつ大きくすると何が起こるだろう。

例えば n = 10 のとき d = 95657055187 となるのだが、この d の数字の並び方をよく見ると、上から2桁目以降が、
1 - log10 e = 0.565705518...
と似ていることに気付く。これは偶然だろうか。

メモ1

2003年1月21日 さらなる美しいパターン: あるいは数秘術: 1から1000までの整数を全部かけ合わせると、 2568桁になる。この「2568」という桁数の568という部分は、
1 - log10 e = 0.5657055...
に近い数字の並び方だ。 1から1万までかけると35660桁になる。この「35660」という数の5660という部分も、上記の超越数に近い。 この確信は、1から10万までかけた数の桁数「456574」の56574をみるとさらに深まる。 これはスターリンの定理の系だ。

--- Number of Digits d in Factorial(10^n) ---
bigint.js v0.5 beta 21-pre

n =  1 : d =   7
n =  2 : d =  158
n =  3 : d =  2568
n =  4 : d =  35660
n =  5 : d =  456574
n =  6 : d =  5565709
n =  7 : d =  65657060
n =  8 : d =  756570557
n =  9 : d =  8565705523
n = 10 : d =  95657055187
n = 11 : d = 1056570551816
n = 12 : d = 11565705518104
n = 13 : d = 125657055180975
n = 14 : d = 1356570551809683
n = 15 : d = 14565705518096757
n = 16 : d = 155657055180967491
n = 17 : d = 1656570551809674827
n = 18 : d = 17565705518096748182
n = 19 : d = 185657055180967481734
n = 20 : d = 1956570551809674817246
n = 21 : d = 20565705518096748172360
n = 22 : d = 215657055180967481723501
n = 23 : d = 2256570551809674817234900
n = 24 : d = 23565705518096748172348884
n = 25 : d = 245657055180967481723488724
n = 26 : d = 2556570551809674817234887122
n = 27 : d = 26565705518096748172348871095
n = 28 : d = 275657055180967481723488710826
n = 29 : d = 2856570551809674817234887108124
n = 30 : d = 29565705518096748172348871081099
n = 31 : d = 305657055180967481723488710810850
n = 32 : d = 3156570551809674817234887108108356
n = 33 : d = 32565705518096748172348871081083412
n = 34 : d = 335657055180967481723488710810833967
n = 35 : d = 3456570551809674817234887108108339510
n = 36 : d = 35565705518096748172348871081083394937
n = 37 : d = 365657055180967481723488710810833949196
n = 38 : d = 3756570551809674817234887108108339491790
n = 39 : d = 38565705518096748172348871081083394917726
n = 40 : d = 395657055180967481723488710810833949177077
n = 41 : d = 4056570551809674817234887108108339491770582
n = 42 : d = 41565705518096748172348871081083394917705625
n = 43 : d = 425657055180967481723488710810833949177056052
n = 44 : d = 4356570551809674817234887108108339491770560322
n = 45 : d = 44565705518096748172348871081083394917705603018
n = 46 : d = 455657055180967481723488710810833949177056029966
n = 47 : d = 4656570551809674817234887108108339491770560299444
n = 48 : d = 47565705518096748172348871081083394917705602994221
n = 49 : d = 485657055180967481723488710810833949177056029941989
n = 50 : d = 4956570551809674817234887108108339491770560299419659

表の見方: 例えば、
n = 20 : d = 1956570551809674817246
というのは、1020! が 19垓5657京0551兆8096億7481万7246桁あることを意味する。 (答えが19垓ということではなく、答えが19垓個の数字からなるという意味。) とても美しく神秘的なパターンが見える。つまり桁数の最上位には n - 1 が現れる。 n = 20 なら 19... と始まる。 そして、数字の並びは、5657055180... となるのだが、 これは、
1 - log10 e = 0.565705518096748...
と関係ある。このパターンにおいても、数字の末尾のほうは、さざ波だってキラキラと揺らいでいる。 上位桁は単なる引き算、真ん中に神秘的にも超越数の並びが現れ、末尾は不規則に揺らぐ。 数の奥深さを感じさせる。

参考資料(PDF)Shouting Factorials!, Pai in the Sky, September 2003

メモ2 (2004-02-03)

どうして上のようになるのだろうか。スターリンの公式から、x! の近似値は
(2πx)1/2 ( x / e )x
である。x = 10n として、この数の桁数を調べるために、10を底とする対数をとると
log10 ( (2π 10n)1/2 ( 10n / e )10n ) =
log10 ( (2π)1/2 10n/2 ( 10n / e )10n ) =
log10 ( (2π)1/2 ) + log10( 10n/2 ) + log10 ( 10n / e )10n =
log10 ( (2π)1/2 ) + n/2 + 10n( log10 ( 10n / e ) ) =
log10 ( (2π)1/2 ) + n/2 + 10n( n - log10 e ) … (*)

第一項 log10 ( (2π)1/2 ) は小さい。 第二項 n/2 は n=100 でも 50 にすぎず、これも小さい。

よって 10n! の桁数は、おおざっぱに第三項
10n( n - log10 e )
による。

すなわち、10n! の桁数は、おおざっぱに 10n × n 程度である。

より正確には、10n × ( n - log10 e ) 程度である。

少し変形すると、10n × ( ( n - 1 ) + ( 1 - log10 e ) )

( 1 - log10 e ) は 0 と 1 の間の数であるから、 スケールファクターを 10n とすると、求める桁数は、
整数部分 ( n - 1 )
小数部分 ( 1 - log10 e )
と分かった。 この数と実際の桁数とのわずかな差は、だいたいにおいて (*) の第一項と第二項による。

この記事のURL

テキスト版省パケ版XML版



webmaster@faireal.net