10^nの階乗の末尾につく0の数

http://www.faireal.net/

こんなスクリプトを書いてみた*1

#!/bin/perl

for $n (1..10) {
  undef @d;
  print "$n: ";
  $i=$n;
  while (1) {
    $d=(10**$n)/(5**$i);
    last if $d<1;
    push(@d,int($d));
    $i++;
  }
  $_=join(" + ",@d);
  print $_," = ",eval($_),"\n";
}

結果:

1: 2 = 2
2: 4 = 4
3: 8 + 1 = 9
4: 16 + 3 = 19
5: 32 + 6 + 1 = 39
6: 64 + 12 + 2 = 78
7: 128 + 25 + 5 + 1 = 159
8: 256 + 51 + 10 + 2 = 319
9: 512 + 102 + 20 + 4 = 638
10: 1024 + 204 + 40 + 8 + 1 = 1277

たしかにn=6のときは1の位が8になって、n=7でまた9になってる。面白いな。

【解説というか思考メモ】
ええと、これは何をしているかというと、10^n以下で5^iの倍数が何個あるかを数えている。10以下では5の倍数は5と10の2つ。だから10!には末尾に0が2個つく。因子として2は5より沢山あるので、素因数分解したときの5の数が、末尾の0の数と等しくなるため。同様に100以下では5の倍数が5,10,15,...100の20個と、5^2の倍数が25,50,75,100の4つ。5^2には5が2つ含まれているけど、5^2の倍数は5の倍数とかぶるので、その分差し引きして単純に足せばいいことになる。だから末尾の0の数は24個。これを一般化すると、
sum[ceil(10^n/5^i)] for i = 1,2,...
という式が導き出された。

sumの中はi=nだけを考えればいい。スクリプトの$i=$nとなっているところを$i=1に変えれば、末尾の0の数そのものになる。

おまけ：ワンライナー版

perl -e'for$n(1..10){print"$n: ";@d=();$i=$n;while*2>=1){push(@d,int($d));$i++}$_=join(" + ",@d);print$_, \
" = ",eval($_),"\n"}'

長いので適当なところで改行しているが実際は1行。

*1:本当はワンライナーで書いたんだけど、さすがにそれだとあまりにも読みにくいので、ここに書き写すときに直した。なので、間違いがあるかも

*2:$d=(10**$n)/ \ (5**$i