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