Project Euler #1 in PHP

The code below works & as far as I can tell the result is correct. Would you please review and let me know what I could have done better?

I tried to use variables as much as possible, that way it could easily be adapted to using other numbers instead of 3 & 5.

I learned quite a bit just writing it, and I hope I can learn more from your input!


Project Euler Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

$sumOfMultiples and the individual numbers are:";
print "";
print_r($multiplesOfNumbers);
print "";
?>

Output:

For sanity check:

The answer is correct, and the individual numbers are:

`Array
(
[0] => 3
[1] => 5
[2] => 6
[3] => 9
[4] => 10
[5] => 12
[6] => 15
[7] => 18
[8] => 20
[9] => 21
[10] => 24
[11] => 25
[12] => 27
[13] => 30
[14] => 33
[15] => 35
[16] => 36
[17] => 39
[18] => 40
[19] => 42
[20] => 45
[21] => 48
[22] => 50
[23] => 51
[24] => 54
[25] => 55
[26] => 57
[27] => 60
[28] => 63
[29] => 65
[30] => 66
[31] => 69
[32] => 70
[33] => 72
[34] => 75
[35] => 78
[36] => 80
[37] => 81
[38] => 84
[39] => 85
[40] => 87
[41] => 90
[42] => 93
[43] => 95
[44] => 96
[45] => 99
[46] => 100
[47] => 102
[48] => 105
[49] => 108
[50] => 110
[51] => 111
[52] => 114
[53] => 115
[54] => 117
[55] => 120
[56] => 123
[57] => 125
[58] => 126
[59] => 129
[60] => 130
[61] => 132
[62] => 135
[63] => 138
[64] => 140
[65] => 141
[66] => 144
[67] => 145
[68] => 147
[69] => 150
[70] => 153
[71] => 155
[72] => 156
[73] => 159
[74] => 160
[75] => 162
[76] => 165
[77] => 168
[78] => 170
[79] => 171
[80

You're using a brute force approach with a linear time complexity in the range and linear in the number of factors i.e. \$\mathcal{O}(nk)\$ where \$n\$ is the range of numbers (1000) and \$k\$ is the number of factors to check for (2 in this problem).

Consider the sum of all numbers that are a multiples of \$k_i\$ and less than \$n\$ and let \$c_i=\lfloor\frac{n-1}{k_i}\rfloor\$ then:

\$S_i=\sum_{m=1}^{c_i}{m\cdot k_i} = k_i\cdot c_i\frac{c_i+1}{2}\$

Now the first step to the solution to the problem is:

\$\sum_{\forall i} S_i =\sum_{\forall i}{k_i\cdot c_i\frac{c_i+1}{2}} \$

But this counts numbers divisible by both \$k_i\$ and \$k_j\$ twice so we need to subtract the double counted numbers. Let \$K_\ell\$ be all pairwise products of \$k_i\$ and \$k_j\$ (in other words, \$K_\ell=k_j\cdot k_i\$) for \$i\ne j\$, then the solution is:

\$S=\sum_{\forall i}{k_i\cdot c_i\frac{c_i+1}{2}} - \sum_{\forall \ell}{K_\ell\cdot C_\ell\frac{C_\ell+1}{2}} \$ where \$C_\ell=\lfloor\frac{n-1}{K_\ell}\rfloor\$.

The time complexity is \$\mathcal{O}(k^2)\$ and as \$k\ll n\$ it is significantly faster.

As for your implementation I would use an array for all the numbers to sum the multiples of and then iterate over that in the inner loop as that avoids an explosion of the expression in the if statement. Other than that I think it looks good.

(note: Euler problem 1 is easily solvable with pen and paper)

StackExchange Code Review Q#63909, answer score: 20