[Python] Project Euler #1 without looping over 1000 numbers

3    04 May 2019 02:08 by u/Satirical

Project Euler is a series of programming challenges (https://projecteuler.net) This is problem #1 in the series.

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.

This problem can be easily solved in a single python line, but that involves looping over all numbers from 0-1000 and checking if they're a multiple of 3 or 5 via modulo.

Here is an example of solving the problem without looping over every possible number, only performing 466 cycles instead of 1000

# 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.
def euler_1():
    # vars to track our multiples
    multiples = []
    # have we counted all the multiples in range yet?
    mot_counted = False
    mof_counted = False
    # counter for finding multiples
    counter = 1
    # loop forever (until we break the loop)
    while True:
        # get multiples
        mot = 3 * counter
        mof = 5 * counter
        # is our multiple below 1000?
        if mot < 1000:
            # add multiple to our list
            if mot not in multiples:
                multiples.append(mot)
        else:
            # we've reached all the multiples of 3 under 1000
            mot_counted = True
            # if our second multiple is below 1000
            # and already not in our list of multiples
        if mof < 1000:
            if mof not in multiples:
                # add multiple to our list
                multiples.append(mof)
        else:
            # we've reached all the multiples of 5 under 1000
            mof_counted = True
        if mof_counted and mot_counted:
            break
        else:
            # increase our counter and continue
            counter += 1
    print("Found {} total multiples.".format(len(multiples)))
    print("Sum: {}".format(sum(multiples)))
if __name__ == "__main__":
    euler_1()

6 comments

0 u/omacu 04 May 2019 02:21

Nice post

0 u/peacegnome 04 May 2019 03:11

Less clear, but could be done with math. I might write it out later but basically "1000/3/5" is key

0 u/RevanProdigalKnight 04 May 2019 04:31

Your euler function could still be made more deterministic and shorter than it is.

def euler_1():
    multiples = []
    counter = 1
    while True:
        t = 3 * counter
        if t < 1000:
            if t not in multiples:
                multiples.append(t)
            t = 5 * counter
            if t < 1000:
                multiples.append(t)
            counter += 1
        else:
            break
    print("Found {} total multiples.".format(len(multiples)))
    print("Sum: {}".format(sum(multiples)))

This finds the same answer in only 334 iterations

0 u/RevanProdigalKnight 04 May 2019 04:34

Equivalent JS code that I used to figure out the method beforehand (because my Python is a bit rusty):

function euler_1() {
  const multiples = new Set()
  let t;
  let i =0;
  while ((t = 3 * ++i) < 1000) {
    multiples.add(t)
    if ((t = 5 * i) < 1000) {
      multiples.add(t)
    }
  }
  console.log(`Found ${multiples.size} total multiples in ${i} iterations.`);
  console.log('Sum:', [...multiples].reduce((acc, n) => acc + n, 0));
}
0 u/rcb 04 May 2019 06:09

Couldn't you do this?

N = 1000
x3 = N / 3
x5 = N / 5
x3_5 = N / (3*5)
print(x3 + x5 - x3_5)
0 u/Satirical [OP] 04 May 2019 07:05

Ooh, triangle numbers. Clever.