【PHP】「x」または「y」で割り切れる1〜nの自然数の合計を求めるプログラム

「x」または「y」で割り切れる、1からnまでの自然数の合計を求めたい場合、単純にループで一つずつ判定する方法もありますが、等差数列の和の公式と包除原理を組み合わせれば、ループなしで効率的に計算できます。ここではその実装例を紹介します。

サンプルコード

<?php
function sum_of_nums($n_val, $x_val, $y_val)
{
    $val_1 = floor($n_val / $x_val) * ((2 * $x_val) + (floor($n_val / $x_val) - 1) * $x_val) / 2;
    $val_2 = floor($n_val / $y_val) * ((2 * $y_val) + (floor($n_val / $y_val) - 1) * $y_val) / 2;
    $val_3 = floor($n_val / ($x_val * $y_val)) * ((2 * ($x_val * $y_val)) + (floor($n_val / ($x_val * $y_val)) - 1) * ($x_val * $y_val)) / 2;
    return $val_1 + $val_2 - $val_3;
}
$n_val = 11;
$x_val = 2;
$y_val = 5;
print_r("2または5で割り切れる11以下の自然数の合計は ");
echo sum_of_nums($n_val, $x_val, $y_val);
?>

出力結果

2または5で割り切れる11以下の自然数の合計は 35

コードの解説

このプログラムでは、sum_of_numsという関数を定義し、その中で次の3つの値を計算しています。

• $val_1: n以下の「xの倍数」の合計。この例では2の倍数(2, 4, 6, 8, 10)の合計である30になります。
• $val_2: n以下の「yの倍数」の合計。この例では5の倍数(5, 10)の合計である15になります。
• $val_3: n以下の「x × yの倍数」の合計。前述の2つの計算で二重に数えられた重複分に相当し、この例では10の倍数(10)の合計である10になります。

最終的な答えは「$val_1 + $val_2 − $val_3」として求められます。これは集合の重複を取り除く包除原理に基づいた考え方です。さらに、各倍数の合計は、項数k = floor(n ÷ その数)、初項・公差ともにaである等差数列の和の公式「k × (2a + (k−1) × a) ÷ 2」を利用することで、ループ処理を一切使わずに定数時間(O(1))で算出できます。そのため、nが非常に大きい場合でも高速に動作するのが大きな利点です。

実行の流れ

関数の外側では、上限となる数($n_val = 11)と、判定に使用する2つの数($x_val = 2、$y_val = 5)を定義し、これらを引数として関数を呼び出します。計算結果はprint_rおよびechoによってコンソールに出力されます。なお、1から11までの自然数のうち、2または5で割り切れる数は2, 4, 5, 6, 8, 10の6個であり、その合計は2 + 4 + 5 + 6 + 8 + 10 = 35となり、プログラムの出力と一致します。