◆東京都 かえる さんからの解答
pk≦n＜pk+1となる整数をkと置く。
nをp進法で表せば、
| n=[ | n pk |
]p | k | +([ | n pk-1 |
]-[ | n pk |
]p)p | k-1 | +・・・+([ | n p |
]-[ | n p2 |
]p)p+(n-[ | n p |
]p) |
nをp進法で表したときに各位の数字の和がb
⇔
| [ | n pk |
]+([ | n pk-1 |
]-[ | n pk |
]p)+・・・+([ | n p |
]-[ | n p2 |
]p)+(n-[ | n p |
]p)=b |
| (1-p)([ | n pk |
]+[ | n pk-1 |
]+・・・+[ | n p |
])=b-n |
| [ | n pk |
]+[ | n pk-1 |
]+・・・+[ | n p |
]= | n - b p - 1 |
ところで、n!を素因数分解したときの素数pの指数は、
1〜nまでの数のうち、
素数pでk回割り切れる個数、(k-1)回割り切れる個数、・・・1回割り切れる個数、を足しあげればよく、
| [ | n pk |
]+[ | n pk-1 |
]+・・・+[ | n p |
]なので、 |
| n - b p - 1 |
であることが示された。 |
【証明了】
◆出題者のコメント
かえるさんの解答，正統的で簡潔な証明で，見事だと思います。
かくもあっさりと証明されてしまったのですが，この問題の結果が意外なもの同士（と私には思えるのですが）を結び付けていて面白いと思ったので出題した次第です。
しばらく待っても他の証明法が出てこないようなので，私のものをご紹介します：
n! に含まれる 2 の最大指数が（実際には有限項で終わりますが）
| 無限和 | ∞ Σ k＝1 |
[ | n 2k |
] |
この和を，ガウス記号を外した和
| ∞ Σ k＝1 |
n 2k |
＝ n | ∞ Σ k＝1 |
1 2k |
＝ n |
両者の差は各項の小数部分です。
いま，n を2進法で表したときの一つの数字（たとえば x）に注目すれば，それは（2進法の）小数部分を
0.x, 0.0x, 0.00x, 0.000x, …
と動きますから，その和は
x × 0.1111… ＝ x
となり，全部の数字の和を取れば b に等しくなるというわけです。
ちょっとした Aha! だと思いませんか？
2 を素数 p に一般化した場合も同様にできますね。