PHPで特定の数「k」の累乗ではない最初のn個の自然数の合計を求めるプログラム

特定の数「k」の累乗ではない最初の n 個の自然数の合計を求める PHP プログラムを紹介します。この問題は、等差数列の和の公式を活用することで、無駄なループを省いた効率的な実装が可能です。

アルゴリズムの考え方

手順はシンプルで、次の2ステップで構成されています。

1. 公式「n × (n + 1) ÷ 2」を使って、1 から n までの自然数の合計を求める。
2. k の累乗に該当する数（k, k², k³, …）のうち n 以下のものをすべて合計から引く。

サンプルコード

<?php
function sum_of_nums($n_val, $k_val)
{
    $tot_sum = ($n_val * ($n_val + 1)) / 2;
    $pow_val = $k_val;
    while ($pow_val <= $n_val)
    {
        $tot_sum -= $pow_val;
        $pow_val *= $k_val;
    }
    return $tot_sum;
}
$n_val = 20; $k_val = 3;
print_r("The sum of fist 20 natural numbers that are not powers of 3 is ");
echo sum_of_nums($n_val, $k_val);
?>

実行結果

The sum of fist 20 natural numbers that are not powers of 3 is 198

コードの解説

「sum_of_nums」という名前の関数を定義し、特定の値の累乗ではない自然数の合計を計算しています。この関数には、自然数の個数「n」と基数「k」がパラメータとして渡されます。

まず、変数 $tot_sum に和の公式を使って 1 から n までの総和を代入します。次に、$pow_val を k で初期化し、while ループの中で累乗値を合計から減算しながら k 倍していきます。累乗値が n を超えた時点でループは終了し、計算結果が呼び出し元に返されます。

関数の外側では n = 20、k = 3 という値を定義し、それらを引数として関数を呼び出します。最終的な結果はコンソール（画面）に出力されます。

結果の検証

1 から 20 までの自然数の合計は「20 × 21 ÷ 2 = 210」です。20 以下の 3 の累乗は「3」と「9」の2つなので、210 − 3 − 9 = 198 となり、実行結果と一致していることが確認できます。

まとめ

このように、全体の合計から不要な累乗値を差し引くアプローチを取れば、1 から n までの各数を一つずつ判定する場合に比べて、はるかに簡潔で高速なコードになります。累乗値の判定にかかる計算量は O(log k n) 程度ときわめて効率的です。