床関数の調和数列の総和:C++コード

最初に

C++で書かれた、床関数の調和数列の総和のサンプル。

表記

\sum _{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor =2 \sum _{k=1}^{\left\lfloor \sqrt{n}\right\rfloor } \left\lfloor \frac{n}{k}\right\rfloor -\left\lfloor \sqrt{n}\right\rfloor ^2

情報

オンライン整数列大辞典より、A006218

C++コード

#include 
#include 

/**
* 床関数の調和数列の総和
* 
*   k
* 2 Σ Floor(n/k)
*  k=1
*--------------------------------------
* r = Floor(√n)
*
*   r
* 2 Σ Floor(n/k) - r^2
*  k=1
* 
* @ref http://oeis.org/A006218
* @param [in] n 数
* @return 数
*/
template
inline TypeInt FloorHarmonic(const TypeInt x)
{
    TypeInt n = 0;
    TypeInt r = sdt::sqrt(x);
    
    if (r != 0) {
        for (TypeInt k = 1; k <= r; ++k) {
            n += x / k;
        }
        n = 2 * n - (r*r);
    }
    return n;
}

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください