Improving the efficiency of my FizzBuzz algorithm I worked on an exercise from codewars, which is a variation of the popular fizzbuzz game.  (If the link doesn't work, you may need to reload the page.)

In this variation, I'm supposed to find the sum of all the multiples of 3 and 5 that are less than the passed in number.

My code works, but it's horribly inefficient. It only works for smaller numbers and can't work for really large numbers

def fizz_buzz_sum(number)
  (1..number).to_a.select{|x| x % 3 == 0 &amp;&amp; x % 5 == 0}.reduce(:+)
end


I think my problem is that I'm iterating over all the numbers in a large array and I might not have to.

Can anyone help reduce the complexity of my algorithm?
Your problem is not really a fizz-buzz problem at all, it is a sum-of-sequence problems, and is commonly based/equivalent to the first "Project Euler" challenge

Note: your code has a bug, you are supposed to sum values that are a multiple of either 3, or 5, but you are summing only the multiples of both 3 and 5 (i.e. 15) that are less than the number...

There is an algorithmic/mathematical solution to this which completely removes the need for the iteration at all.

Consider the sum of all the multiples of 3 less than n....:

3 + 6 + 9 + .... + t


where t &lt; n.

The sum of that sequence is called the sum of the Arithmetic Progression. 

if you change the sequence to be:

(1 x 3) + (2 x 3) + (3 x 3) + .... + (m * 3)


then you can factor out the 3's, and have:

3 * (1 + 2 + 3 + .... + m)


Now, the '1 + 2 + 3 + .... + m` sequence is what's called a triangular number:

*
* *
* * *
....

* * * .... *


which you can visualize as being half the area of a rectangle, where one side of the rectangle is m, and the other side is m + 1

What is the size of m, well, it is the number of 3 multiples there are:

m = (n - 1) / 3


And, your arithmetic progression sum becomes:

count3s = (n - 1) / 3
sum3s = 3 * count3s * (count3s + 1) / 2


Similarly, the sum of 5's less than n are:

count5s = (n - 1) / 5
sum5s = 5 * count5s * (count5s + 1) / 2


So, the sum of all 3 and 5 multiples less than n is easy, but there's a probem.... if we add the two sums together, it will count the multiples of 15 twice.....

so, the sum of one 15's series is:

count15s = (n - 1) / 15
sum15s = 15 * count15s * (count15s + 1) / 2


if we subtract that, you get the actual sum....

In ruby terms, this can all be reduced to a simple function, and then simple arithmetic... (see ideone ):

def sum_series(base, limit)
    count = (limit - 1) / base
    sum = base * (count * (count + 1)) / 2
end

def fizz_buzz_sum(number)
  sum_series(3, number) + sum_series(5, number) - sum_series(15, number)
end