Project Euler #1 in PHP

Question

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.

<?php
/* 
** 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.
*/
$numberOne = 3;
$numberTwo = 5;
$endingIndex = 1000;
$multiplesOfNumbers = array();  

for ($index = 1; $index < $endingIndex; $index++) {
    if ($index % $numberOne == 0 || $index % $numberTwo == 0) {
        array_push($multiplesOfNumbers, $index);
    }
}
$sumOfMultiples = array_sum($multiplesOfNumbers);

print "The solution to Euler Project is <b>$sumOfMultiples</b> and the individual numbers are:<br><br>";
print "<pre>";
print_r($multiplesOfNumbers);
print "</pre>";
?>

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] => 174
    [81] => 175
    [82] => 177
    [83] => 180
    [84] => 183
    [85] => 185
    [86] => 186
    [87] => 189
    [88] => 190
    [89] => 192
    [90] => 195
    [91] => 198
    [92] => 200
    [93] => 201
    [94] => 204
    [95] => 205
    [96] => 207
    [97] => 210
    [98] => 213
    [99] => 215
    [100] => 216
    [101] => 219
    [102] => 220
    [103] => 222
    [104] => 225
    [105] => 228
    [106] => 230
    [107] => 231
    [108] => 234
    [109] => 235
    [110] => 237
    [111] => 240
    [112] => 243
    [113] => 245
    [114] => 246
    [115] => 249
    [116] => 250
    [117] => 252
    [118] => 255
    [119] => 258
    [120] => 260
    [121] => 261
    [122] => 264
    [123] => 265
    [124] => 267
    [125] => 270
    [126] => 273
    [127] => 275
    [128] => 276
    [129] => 279
    [130] => 280
    [131] => 282
    [132] => 285
    [133] => 288
    [134] => 290
    [135] => 291
    [136] => 294
    [137] => 295
    [138] => 297
    [139] => 300
    [140] => 303
    [141] => 305
    [142] => 306
    [143] => 309
    [144] => 310
    [145] => 312
    [146] => 315
    [147] => 318
    [148] => 320
    [149] => 321
    [150] => 324
    [151] => 325
    [152] => 327
    [153] => 330
    [154] => 333
    [155] => 335
    [156] => 336
    [157] => 339
    [158] => 340
    [159] => 342
    [160] => 345
    [161] => 348
    [162] => 350
    [163] => 351
    [164] => 354
    [165] => 355
    [166] => 357
    [167] => 360
    [168] => 363
    [169] => 365
    [170] => 366
    [171] => 369
    [172] => 370
    [173] => 372
    [174] => 375
    [175] => 378
    [176] => 380
    [177] => 381
    [178] => 384
    [179] => 385
    [180] => 387
    [181] => 390
    [182] => 393
    [183] => 395
    [184] => 396
    [185] => 399
    [186] => 400
    [187] => 402
    [188] => 405
    [189] => 408
    [190] => 410
    [191] => 411
    [192] => 414
    [193] => 415
    [194] => 417
    [195] => 420
    [196] => 423
    [197] => 425
    [198] => 426
    [199] => 429
    [200] => 430
    [201] => 432
    [202] => 435
    [203] => 438
    [204] => 440
    [205] => 441
    [206] => 444
    [207] => 445
    [208] => 447
    [209] => 450
    [210] => 453
    [211] => 455
    [212] => 456
    [213] => 459
    [214] => 460
    [215] => 462
    [216] => 465
    [217] => 468
    [218] => 470
    [219] => 471
    [220] => 474
    [221] => 475
    [222] => 477
    [223] => 480
    [224] => 483
    [225] => 485
    [226] => 486
    [227] => 489
    [228] => 490
    [229] => 492
    [230] => 495
    [231] => 498
    [232] => 500
    [233] => 501
    [234] => 504
    [235] => 505
    [236] => 507
    [237] => 510
    [238] => 513
    [239] => 515
    [240] => 516
    [241] => 519
    [242] => 520
    [243] => 522
    [244] => 525
    [245] => 528
    [246] => 530
    [247] => 531
    [248] => 534
    [249] => 535
    [250] => 537
    [251] => 540
    [252] => 543
    [253] => 545
    [254] => 546
    [255] => 549
    [256] => 550
    [257] => 552
    [258] => 555
    [259] => 558
    [260] => 560
    [261] => 561
    [262] => 564
    [263] => 565
    [264] => 567
    [265] => 570
    [266] => 573
    [267] => 575
    [268] => 576
    [269] => 579
    [270] => 580
    [271] => 582
    [272] => 585
    [273] => 588
    [274] => 590
    [275] => 591
    [276] => 594
    [277] => 595
    [278] => 597
    [279] => 600
    [280] => 603
    [281] => 605
    [282] => 606
    [283] => 609
    [284] => 610
    [285] => 612
    [286] => 615
    [287] => 618
    [288] => 620
    [289] => 621
    [290] => 624
    [291] => 625
    [292] => 627
    [293] => 630
    [294] => 633
    [295] => 635
    [296] => 636
    [297] => 639
    [298] => 640
    [299] => 642
    [300] => 645
    [301] => 648
    [302] => 650
    [303] => 651
    [304] => 654
    [305] => 655
    [306] => 657
    [307] => 660
    [308] => 663
    [309] => 665
    [310] => 666
    [311] => 669
    [312] => 670
    [313] => 672
    [314] => 675
    [315] => 678
    [316] => 680
    [317] => 681
    [318] => 684
    [319] => 685
    [320] => 687
    [321] => 690
    [322] => 693
    [323] => 695
    [324] => 696
    [325] => 699
    [326] => 700
    [327] => 702
    [328] => 705
    [329] => 708
    [330] => 710
    [331] => 711
    [332] => 714
    [333] => 715
    [334] => 717
    [335] => 720
    [336] => 723
    [337] => 725
    [338] => 726
    [339] => 729
    [340] => 730
    [341] => 732
    [342] => 735
    [343] => 738
    [344] => 740
    [345] => 741
    [346] => 744
    [347] => 745
    [348] => 747
    [349] => 750
    [350] => 753
    [351] => 755
    [352] => 756
    [353] => 759
    [354] => 760
    [355] => 762
    [356] => 765
    [357] => 768
    [358] => 770
    [359] => 771
    [360] => 774
    [361] => 775
    [362] => 777
    [363] => 780
    [364] => 783
    [365] => 785
    [366] => 786
    [367] => 789
    [368] => 790
    [369] => 792
    [370] => 795
    [371] => 798
    [372] => 800
    [373] => 801
    [374] => 804
    [375] => 805
    [376] => 807
    [377] => 810
    [378] => 813
    [379] => 815
    [380] => 816
    [381] => 819
    [382] => 820
    [383] => 822
    [384] => 825
    [385] => 828
    [386] => 830
    [387] => 831
    [388] => 834
    [389] => 835
    [390] => 837
    [391] => 840
    [392] => 843
    [393] => 845
    [394] => 846
    [395] => 849
    [396] => 850
    [397] => 852
    [398] => 855
    [399] => 858
    [400] => 860
    [401] => 861
    [402] => 864
    [403] => 865
    [404] => 867
    [405] => 870
    [406] => 873
    [407] => 875
    [408] => 876
    [409] => 879
    [410] => 880
    [411] => 882
    [412] => 885
    [413] => 888
    [414] => 890
    [415] => 891
    [416] => 894
    [417] => 895
    [418] => 897
    [419] => 900
    [420] => 903
    [421] => 905
    [422] => 906
    [423] => 909
    [424] => 910
    [425] => 912
    [426] => 915
    [427] => 918
    [428] => 920
    [429] => 921
    [430] => 924
    [431] => 925
    [432] => 927
    [433] => 930
    [434] => 933
    [435] => 935
    [436] => 936
    [437] => 939
    [438] => 940
    [439] => 942
    [440] => 945
    [441] => 948
    [442] => 950
    [443] => 951
    [444] => 954
    [445] => 955
    [446] => 957
    [447] => 960
    [448] => 963
    [449] => 965
    [450] => 966
    [451] => 969
    [452] => 970
    [453] => 972
    [454] => 975
    [455] => 978
    [456] => 980
    [457] => 981
    [458] => 984
    [459] => 985
    [460] => 987
    [461] => 990
    [462] => 993
    [463] => 995
    [464] => 996
    [465] => 999
)

Answer 1

The other answers have concentrated on an algorithmic alternative. I'm going to just take the algorithm as given and concentrate on the code. This is how I'd write it:

<?php
/* 
** 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.
*/

$divisors = array( 3, 5 );
$multiples_of_divisors = array();

// since we want only the multiples strictly below the upper bound, we use < rather than <=
for ( $i = 1, $n = 1000; $i < $n; $i++ ) {
    foreach ( $divisors as $divisor ) {
        if ( 0 == $i % $divisor ) {
            $multiples_of_divisors[] = $i;
            // break out of the foreach so that we only add a given number once for a list of divisors
            break;
        }
    }
}

$sum_of_multiples = array_sum($multiples_of_divisors);

print "The solution to Euler Project is <strong>$sum_of_multiples</strong> and the individual numbers are:<br /><br />";
print "<pre>";
print_r($multiples_of_divisors);
print "</pre>";
?>

Reasons:

If code immediately follows a comment, the presumption is that the comment explains that section of code. If the comment is a more general headline (e.g. the description of what the entire code is supposed to accomplish), then it helps if you separate the comment from the code with whitespace.

CamelCase does not generalize well to other languages. Consider using underscore_delimited variable names instead. These are more easily recognized by non-native speakers. This helps if you are working in a global context, like a multinational company or an open source project.

As others mentioned, an array is more general than $numberOne and $numberTwo. $divisors is also a more descriptive name than $numbers.

If you do something incorrectly at first and then fix it, consider adding a comment to highlight the fix (and possibly the mistake). Thus you'd want to explain why you used < rather than <= here.

Replacing $i with $index makes sense if the variable is used to index an array. Here though, that's not what it's doing. Either use the more standard $i or come up with a truly descriptive name. In my opinion, $i is more than enough here.

Define the start and end boundaries at the same point in the code. I did so in the for statement here. You could also have moved both out of the loop and had something like

$lower_bound = 1;
$upper_bound = 1000;
for ( $i = $lower_bound; $i < $upper_bound; $i++ ) {

In C style languages like PHP, it's easy to do an assignment (=) when you meant to do an equality check (==). To guard against this, some people put the value side first ( 0 == $i ) rather than the variable side ( $i == 0 ). This causes the compiler to throw an error rather than silently doing the assignment and then checking if the assigned value evaluates as false.

In PHP, if you are dealing with a single value, []= is faster than array_push. If adding a list of values, stick with array_push.

If your code is doing something clever (or something that fixes a previous mistake), comment it. That saves the next person to edit the code from having to be even more clever to figure out what is happening.

Note that to modify the parameters of the question, you have to modify the code. It's often better to allow the code to take input. That allows people who are not programmers to use your code. A program that handles user input would thus be better. For PHP, you'd often do this with GET arguments and could offer an HTML form to enter them.

This program produces invalid HTML. This generally isn't a problem, as the browser will add the missing tags. However, it is a bad practice to rely on this.

Some of my changes are purely stylistic. Code that doesn't use them is perfectly valid. I encourage you to think about how you want your code to look.

Answer 2

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)

Answer 3

Let's solve a simpler problem: Find the sum of all multiples of 3 below 1000.

We have

\begin{align} 3 + 6 + 9 + 12 + \cdots + 999 &= 3 (1 + 2 + 3 + 4 + \cdots + 333) \\ &= 3 \times \frac{333 \times (333 + 1)}{2}, \end{align}

where the second line comes from the identity

\begin{align} 1 + 2 + 3 + \cdots + n = \sum_{k = 1}^n k = \frac{n(n + 1)}{2}. \end{align}

(See also Triangular number on Wikipedia.)

Now we can use the above process to find the sum of all multiples of 5 below 1000. This gets us pretty close to the solution.

The problem is, we're counting the numbers \$15, 30, 45, \ldots\$ in our count of multiples of 3, and our count of multiples of 5. So the final step would be subtracting the number of multiples of 15 from our count, giving a solution to the original question.