1から2007までかけたとき、一の位から0が何個連続するか、捕捉

数学

ん、番組で紹介された解き方の、意味は理解できたけど、言葉で証明するのはめんどくさいかな。


　まあ前提の確認
\prod_{k=1}^{n} kの一の位から連続する0の数は、

  1. かけた10の数に依存する*1
  2. 10をかけるという事は、2と5をかける事と同じ意味である
  3. 10をかけた数は、\prod_{k=1}^{n} kを素因数分解したときの2^a \times 3^b \times 5^c \cdotsのaとcに依存する
  4. a > cつまり、2の素数の指数の方が多いのは自明なので、10をかけると言うのは5の素数の指数の値と同値である


って証明になる。


で、結局は\prod_{k=1}^{n} kに含まれる5の素数の数を出す方法を考えるって事になるんだけど


やっぱり解き方としては、番組で紹介された「2007を5で割っていって、商が0になったらそれまでの商を足す」て方法しか思いつかない。


    
倍数で思考

    ある1から自然数nまでの総積Nに含まれる素数pの数は、ちょっと捻って倍数から考えてみる。


最初に素数pの倍数は各倍数が最低1個の素数pを含んでいることは自明である。


p,  2p, 3p, \cdots, a \cdot p, (a+1)\cdot p , \cdotsで、
 a \cdots p < n < (a+1) \cdot p
の場合Nは素数pをa個は含んでいる。


次に、p^2の倍数は各倍数が最低2個の素数pを含んでいることは自明である。


p^2,  2p^2, 3p^2, \cdots, b \cdot p^2, (b+1)\cdot p^2 , \cdotsで、
 b \cdots p^2 < n < (b+1) \cdot p^2
の場合Nは素数pを2b個は含んでいる。
が、p^2の倍数は、素数pの倍数と重複するので、
そのことを検討の結果Nは素数pを新たにa+b個は含んでいる。


って感じでやっていくとあるp^mで
 n < m \cdot p
になる。


でこのときまでに、導出した数a+b+c+\cdotsが総積Nが含む素数pの個数となるんだが、
やっぱり言葉で書くとメンドクサイ*2






    
商で検討

    上でごちゃごちゃ書いているけど結局は自然数nと素数pがある場合


 n = pa + r, 0 \le r < p


の、aがpの倍数の含まれる個数。


 a = pb + s, 0 \le s < p


の、bがp^2の倍数の含まれる個数。



 b = pc + t, 0 \le t < p


の、cがp^3の倍数の含まれる個数。

って、具合にやるのと同じやん（´・ω・｀）

*1:下の位が0になるのは10を乗算したときだけ

*2:図で書くと一発なんですけどね|ω・`）