Constant-time Approach

As $n$ gets bigger, the time spent iterating through the multiples of three and five increases as well. Do we have to look at every multiple, even if we're only examining known multiples?

Realigning the previous solution will reveal a pattern that emerges:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

The components of the above are the arithmetic sum, in steps of $3$ and in steps of $5$, with the combined steps of $3\times 5=15$ being counted twice, so it should be subtracted from the total. For the above example of n=99,

$$\sum _{i=1}^{\lfloor n/3\rfloor }3i+\sum _{i=1}^{\lfloor n/5\rfloor }5i-\sum _{i=1}^{\lfloor n/15\rfloor }15i=\frac{3\ast 1122}{2}+\frac{5\ast 380}{2}-\frac{15\ast 42}{2}$$

Another way to look at this is to separate out the common parts of each column and row in the above grid, resulting in one part that increases vertically and another part that is the same for every row.

$15\times \sum _0^{k}1$ for

0

0

0

0

0

0

0

15

15

15

15

15

15

15

30

30

30

30

30

30

30

45

45

45

45

45

45

45

60

60

60

60

60

60

60

75

75

75

75

75

75

75

$k\times \sum _0^{k}x$ for

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

This is in terms of $k$, the number of rows (or, $n÷15$ rounded down, where $n$ is the final counted value).

n := limit - 1
k := n / 15 // number of rows (except partial final row)
rowcount := 5 /*3s*/ + 3 /*5s*/ - 1 /*common*/
rowsum := 0 + 3 + 5 + 6 + 9 + 10 + 12

sum := rowcount * 15 * k * (k - 1) / 2
sum += k * rowsum

The last row may be partial, a few values remaining between $15\times k$ and $n$. We can sum those up in a couple of small for loops, adding them to the main result. Or, since we know the row size consists of non-shared multiples of $3$ and $5$, we can use some number theory to arrive at the result without even having to loop through the numbers in the last row.

90

90

90

90

90

0

3

5

6

9

// Add remaining multiples of 3 and 5 (excluding n).
delta := n - k*15
div3, div5 := delta/3, delta/5
sum += k*15*(div3+div5+1) +
  div3*(div3+1)*3/2 +
  div5*(div5+1)*5/2

To understand the last three lines, it helps to think of the last (partial) row as its own

arithmetic series for the threes and fives separately, offset by the $k$th row as with all of the previous rows. The div3 and div5 are the limits on these smaller series, arrived at by counting the numbers between $n$ and the last $k\times 15$ value. You can see the sequence this creates for the full row by looking at the definition of rowsum, and this can be generalized as well.