「高斯」與老師七個 0 的故事求解？

12-06

據說高斯上小學的時候，老師一次上課為了偷懶，對同學們說：」誰能告訴我1+1/2+1/3+...+1/100000化成最簡分數分母末尾有多少個零我就讓你們出去玩。「之後老師拿了本書正坐下準備看，年輕的小高斯馬上舉起手說：「老師，我知道了！」老師不相信，於是問他。高斯很自豪的說：「七個！」老師大驚失色，拿出準備好的答案查看發現果然是七個，他震驚的問小高斯：「我算了一晚上的題目，你怎麼一下子就做出來了？」高斯說：「五的七次方不是78125么，而五的八次方就超過十萬了啊！」老師恍然大悟，覺得小高斯是個可造之材，好好的誇獎了他一番。

老師算的答案：A/B72181004058917381923192886446360746670894080000000

哇！末尾真的有七個零！

故事純屬虛構，老師算出的數字太長所以就沒貼。（雖然能一夜算出答案的老師水平更高）

然後我的問題就是為什麼是7個0

我相信 Gauss 的思路沒樓上想的那麼糾結... (以下通分均指按最小公倍數通分)

其實...因為 5^7&<10萬&<2*5^7&<5^8, 所以對每一個求和因子而言, 通分後只有 1/5^7 的分子不被 5 整除, 所以全部求和後的分子也不被 5 整除...所以最後不管咋樣約化, 分母中 5 的指數一定是 7...所以...

不出意外的話，這個故事是假的。
不然，花了一晚上就能算出具體結果數字，那位老師絕對完爆高斯十條街……
以下是答案：

首先，1+1/2+1/3+...+1/100000化成最簡分數後，它的分母就是1、2、3…100000的最小公倍數，即能同時被1、2、3…100000整除的最小自然數。我們令它為X。
其次，要計算X末尾有多少個0，可以將X分解為 X=Y×(10^n) （註：10^n表示10的n次方）。其中Y末尾不是0，即Y不被10整除。而n就是要計算的X末尾0的個數。由於10=2×5，所以上式也可以表示為 X=Y×(2^n)×(5^n) 。其中Y要麼只能被2整除，要麼只能被5整除。我們可以計算X的質因數分解里，2和5的冪（次方）分別是多少，兩個結果中較小的那個就是n。
於是，我們來看X的質因數分解里，2和5的冪（次方）分別是多少。5的7次方等於78125，而78125&<100000（即78125位於1、2、3…100000里），所以X能被78125整除，即能被5^7整除；另一方面，5的8次方大於100000，而X是能同時被1、2、3…100000整除的最小自然數，所以X不被5^8整除。所以，X的質因數分解里，5的冪為7。看到這裡，也許有人會說，哦，原來這麼簡單啊，於是馬上動手計算X的質因數分解里2的冪是多少。其實不用這麼麻煩。為什麼呢？因為嘛，2的冪肯定比5的冪大。5的8次方就已經大於100000了，而2的8次方才等於256，遠遠小於100000呢，所以2的冪肯定比7大。
最後，根據上面的計算結果可以得到，X=Y×(2^7)×(5^7)=Y×(10^7) ，其中Y能被2整除，但不能被5整除。所以，1+1/2+1/3+...+1/100000化成最簡分數後分母末尾有7個0。

========================================================
好吧……本人的上述分析不夠全面，詳細過程見他山之石（by 王贇^_^Maigo）：
http://blog.renren.com/blog/228343133/862901181

問題：
Sn = 1/1 + 1/2 + ... + 1/n 的最簡形式中分母末尾有幾個0？

結論：
若5^p &<= n &< 4*5^p，則分母中含p個0；
若4.2*5^p &<= n &< 4.8 * 5^p，則分母中含p-1個0；
若4*5^p &<= n &< 4.2*5^p，或4.8*5^p &<= n &< 5*5^p，則分母中含p-2個0。

大致想法：
一般情況下，若5^p &<= n &< 5^(p+1)，則末尾有p個0；但不能保證通分加起來後的分子不能再跟分母約分。比如當n=20時，通分後分母為232792560（末尾有1個零），而通分後各項分子之和為837527025，可以跟分母約去一個15。約分後Sn = 55835135/15519504，分母上的0就不存在了。
所以，必須考慮通分後的各項分子之和能否跟分母約分，尤其需要關注分子中是否含有因子5。

搞那麼複雜幹嗎，10分解成2和5，出現了x個5之前肯定出現過大於等於x個2，所以只要求100000一下5的最高次冪就好了。0的個數就是最高次冪的冪值

轉個現成的

http://page.renren.com/601087941/note/862928118?ref=minifeedsfet=2012fin=7ff_id=601087941feed=page_blogtagid=862928118statID=page_601087941_2level=1

上一篇日誌http://page.renren.com/601087941/note/862883978
當然學術帝總是有的，所以就有了證明：
http://blog.renren.com/blog/402703355/862893804
還有一篇更一般的討論
http://blog.renren.com/blog/228343133/862901181
主頁菌將前者搬運至此：
問題：
1/1+1/2+1/3+……1/n化成最簡分數後，分母末尾0的個數
證明：
==================
1.上限：
通分後化為
(n!/1+n!/2+......n!/n)/n!
設n!中因子5的個數為m，那麼n!/k因子5的個數為，m-(k中因子5的個數)。
而連續的自然數1到n，因子5個數最多的那一個數為：5^p。其中p滿足5^p &<= n! &< 5^(p+1)。
換句說分子中，因子個數5最小的那一項為 n!/5^p，對應的因子5的個數為m-p。
分母分子同時除以5^(m-p)這樣分母因子5的個數為p
注意到0來自於2*5=10，換句話說，分母末尾0的個數不會超過p
======================
2.下限
注意到凡是含有因子5的數，其個位數只能為0或者5.
通過1的化簡，不含有因子5的項只有一個，這一項的個位數必定不是0或者5，這個與任意多個0或者5相加後所得結果的個位數必定不會是0或者5.也就是說分子所有項之和不會再含有因子5。這樣分母中因子5的個數已經確定是p了。
下面我們再分析分母中因子2的個數，如果2的個數大於等於p，那麼就可以確定分母中有p個0
必然存在非負的q，滿足2^q &<= n &< 2^(q+1)，顯然q不小於p
同上分析，分母2的個數上限為q，所有含有因子2的項的個位數為0，2，4，6，8中的一個。我們知道經過第一步化簡後分子中只有一項不含因子2，這一項個位數為奇數。而一個奇數與任意多個偶數相加，結果仍然為奇數，換句說，分子中所有項之和不會再含有因子2.
這樣分母中因子2的個數為q，因子5的個數為p，q≥p。
從而分母中0的個數為p
=========================
事實上對於大於1的因子f，如果n滿足f^u &<= n &< f^(u+1)
那麼分母中最終含有因子f的個數就是u
=============================

因為前6個孩子都猜錯了。