Google for it, Euler problem #1 has got a lot of solution implementations. Most of them use similar algo: produce the list of all numbers in the range [0-1000], filter only number divisible by 3 or 5, and compute the sum. This is perfectly fine, and it’s wonderfull to code when your language allow some kind of lazy list (default in Haskell, or often called stream library in other language).

But can we construct the sequence of “number divisible by 3 and 5” directly?

Let’s have a look at what this sequence looks like:

m = 42
l = sorted(list(set(range(0, m, 3) + range(0, m, 5))))
l
[0, 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40]

Well … cannot see a pattern … let’s look at the sequence of difference between 2 consecutive numbers:

map(lambda (x,y): y-x, zip(l, l[1:]))
[3, 2, 1, 3, 1, 2, 3, 3, 2, 1, 3, 1, 2, 3, 3, 2, 1, 3, 1]

Here we go … I have no idea why, but seems that we can construct the sequence using the list of increment 3,2,1,3,1,2,3 (same with m=300).

And then, here come a different python solution:

from itertools import cycle, takewhile

def succ(b, inc):

while True:

b += inc.next()

yield b

sum(takewhile(lambda x: x < 1000, succ(0, cycle([3,2,1,3,1,2,3]))))
[/sourcecode]
By the way, there must be a mathematical solution to this first problem, some kind of magic formula ... any pointer?

### Like this:

Like Loading...

*Related*

April 26, 2008 at 12:12 am

Btw, a quick solution (creating 2 big list in memory) is:

sum(list(set(range(0, 1000, 3) + range(0, 1000, 5))))

April 26, 2008 at 12:15 am

oops, copy-paste too quicly … no need for “list” for sum:

sum(set(range(0, 1000, 3) + range(0, 1000, 5)))