05.28.08

Project Euler: Problem 1

Posted in python tagged , at 3:01 pm by redochre

Project Euler is a website with nearly 200 math-type programming problems, which look great for learning and practice.

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.

A Solution:

sum = 0

for i in range(1000):
    if (i % 3 == 0)|(i % 5 == 0):
        sum += i

print sum

There are surely more efficient solutions, but for the moment I’m more concerned about getting familiar with the python syntax than I am with the pretty pretty math.

7 Comments »

  1. Dan | thesamovar said,

    28 May, 2008 at 6:48 pm

    Here’s another solution (one liner):

    sum(i for i in range(1000) if i%3==0 or i%5==0)

    Have fun with learning Python! :-)

  2. redochre said,

    28 May, 2008 at 7:12 pm

    Thanks for more compact solution, Dan! List comprehensions are a new idea for me, so it’s never what I think of the first time around.

  3. Dan | thesamovar said,

    29 May, 2008 at 4:41 pm

    You’re welcome! :-)

    Python’s a great language for these sorts of really elegant solutions. I think the one liner I posted above is lovely because reading it is just like reading the statement of the problem itself.

    Probably it won’t take long to get into the swing of the ‘Pythonic’ way of doing things, I only started programming in it before shortly before Christmas.

    And btw, it’s not actually a list comprehension, it’s a “generator expression”. The difference is subtle, a list comprehension would be:

    sum([i for i in range(1000) if i%3==0 or i%5==0])

    With the square brackets it’s a list comprehension, without them it’s a generator expression. The difference is that in the generator expression you never actually compute the list of all the i. The sum function only needs to go through them one by one so you don’t actually need the whole list, just each element one at a time, which is what generators do.

    I’ll stop rambling now…

  4. redochre said,

    30 May, 2008 at 7:03 am

    Thanks for the clarification, Dan. Looks like I’ll have to look up some documentation on generator expressions (and more on list comprehensions).

    Can you tell me, is there an equivalent to the sum() function for multiplication? I’ve looked, but can’t find anything (though I’m still trying to figure out the best way to search the python documentation too).

  5. Dan | thesamovar said,

    30 May, 2008 at 8:04 am

    As far as I know there isn’t, but you can do it in another way:

    def prod(vals):
    return reduce(lambda x,y: x*y,vals)

    Or slightly nicer and possible faster (but involves an import):

    from operator import mul
    def prod(vals):
    return reduce(mul,vals)

    Here mul is the multiplication function, and reduce(f,[x,y,z]) does f(f(x,y),z), etc., so with mul it just multiplies all the elements together. reduce also works with generators, so this is fairly general.

    For searching, I usually just use google with ‘python’ the first word of my search. So “python product function” found this page (which has some other cool stuff on it):

    http://jaynes.colorado.edu/PythonIdioms.html

  6. redochre said,

    30 May, 2008 at 8:12 am

    Yes! I was just poking around the python.org site and came across another list of idioms and anti-idioms:
    http://docs.python.org/dev/howto/doanddont.html

    It also pointed out the reduce function, which I’m pretty excited about now. I’ll not try to get my head around the lambda function for a little while yet.

  7. starhawk said,

    19 August, 2008 at 7:41 pm

    print 3*333*167 + 5*199*100 – 15*67*33

    Some online friends of mine are trying to get me to work thru these problems, they already are. I really don’t have the time but a little math helps alot. And btw cool blog. I am just learning python so I appreciate stuff like this. peace.


Leave a Comment