自然数の約数の個数を
で表します。
は次の公式で求めることができます:
公式
と
が素因数分解されているとき、
が成り立つ。
cf.)
mathtrain.jp
以前の記事でを用いた例としてサブライム数 - INTEGERSがあります。
の上からの評価として、自明な評価
がありますが、この記事では次の便利な評価を与えます:
定理
において、
が成り立つ。
証明*1. は
のときに
なる関数であり、後で指定する。
の公式より、
と素因数分解されていれば
が成立する。素因子の大きさによって場合分けを行う。
のとき:
なので、 である。
のとき:
より、
が成り立つ(ビッグの定数は
に依らないことに注意)。従って、①より
を得る。これより、
となるが、十分大きいに対して
とおけば、②の第一項は第二項にで吸収される(
ならば、
であることに注意)。
故に
が示された。 Q.E.D.