nの階乗のb進数表記末尾のゼロの個数の数え上げ関数を実装した

階乗の末尾連続ゼロ数は基数のbによって決まる.bの素因数分解に含まれる素数をpとするとき,N=n!に含まれる最小のp^eの個数が連続ゼロ数となるので,最小のp^eの個数を決定する必要がある.一般にはpが大きいほどこの値は小さくなるが,pが小さくてもeが大きければ逆転する可能性がある.

まず,一般的にnとbを指定したときの連続ゼロ数を与える関数を作ってみよう.このためには,nを素因数分解するところから始めなくてはならない.julia には factor という関数がある.以下のダンプは b=2^2・3 を表している.

b=12 f =Primes.Factorization(2 => 2, 3 => 1)

Factorization というのは連想配列で,とりあえず,

for (p, e) in f
 @printf(“%d %d \n”, p, e)
end

の形で取り出すことができる.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA