3

First off, I apologize for my inaccurate vocabulary. I am an absolute ground-zero beginner. Anyways, I am attempting to solve this problem: http://projecteuler.net/problem=1

To be brief, I'm trying to write a script that will find the sum of all the multiples of 3 or 5 below 1000.

My (extremely basic) approach was with this program:

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

a = sum(x)
b = sum(y)
n = a + b

print n

I realized that this was wrong because there are numbers like 15 that are included twice (it's a multiple of both 5 and 3). So is there a way to fix this or am I approaching this problem from a completely wrong angle? Or do I need to just study more before I try solving this problem? I also apologize if this has been explained in a previous post, but I looked around for a bit.

7
  • Do you need to preserve the order? Dec 24, 2011 at 3:35
  • Since I just need the sum, I'm pretty sure that the order won't affect my outcome.
    – Grant
    Dec 24, 2011 at 3:39
  • Ah, right. I didn't pay enough attention to the question. set should work fine. Dec 24, 2011 at 3:47
  • 2
    Once you solve the problem, make sure you read the unlocked forum for the answer to this problem. There are much more elegant and efficient ways than exploiting set behavior. Dec 24, 2011 at 3:57
  • Woah. I checked out other peoples' solutions, but I'm way to inexperienced to understand any of it. They're all using functions I've never even heard of it. Is it better for the solutions to be more complex? I guess those types of solutions demonstrate your abilities better, huh? Well, I'll be content with my simplicity for now.
    – Grant
    Dec 24, 2011 at 4:09

6 Answers 6

4

It is called inclusion exclusion principle so you can do like

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

##multiple of 15 are counted twice
z=range(15,1000,15)


a = sum(x)
b = sum(y)
c = sum(z)
n = a + b -c
print(n)

but beauty is in using generators or list comprehensions

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

Where % is modulo and is remainder in integer devision. Nice thing about this is that codes reads so fluently and is direct translation of rules and can be read from left to right.

Both algorithms run times depends on n in this case is 1000. If n would be for instance 1000000000 you would have to wait for long time to complete. If you apply little mathematics you can find out that

sum(a for a in range(a1,a2,n)) 

is actually arithmetic progression and total of this can be calculated in constant time no matter how big n is. http://en.wikipedia.org/wiki/Project_Euler#Example_problem_and_solutions

1
  • Ahhh, I see. Wow, I really liked your solution. It never even occurred to me that multiples of 15 are the only ones being repeated. I shouldn't be surprised. I'm still in secondary school, and my maths aren't too high. But thanks again!
    – Grant
    Dec 24, 2011 at 4:27
4

You can use a set to eliminate the duplicates:

>>> len(x)
333
>>> len(y)
199
>>> s = set(x + y)
>>> len(s)
532

Then you can sum the members of the set instead.

2

Simple method:

sum(set(x+y))

sets have a fair bit of functionality you'll find useful for the PE problems.

You could also do it with a simple loop over the entire range pretty easily.

4
  • Thank you so much! That worked perfectly! Although, to be completely honest, I have almost no idea what the 'set' function does yet. I clearly have much to learn, but anyways, thanks again!
    – Grant
    Dec 24, 2011 at 3:59
  • 1
    @Grant, the set function creates a set out of operations on other lists. Now, since set elements do not repeat, if it encounters repeating entities while creating the set, it preserves only one of them. Dec 24, 2011 at 4:05
  • To add a little more to @AbhranilDas's comment: A set stores every element that you add to it exactly once in an unordered manner, and makes operations such as "is a in x" or "everything in x but not in y" fast and easy. In this case, we are taking advantage of that everything is stored uniquely: it can exist exactly once. I linked to the python documentation, feel free to let us know if you have any questions about it ^_^ Dec 24, 2011 at 4:17
  • So essentially, a set is the equivalent of a list but it doesn't have duplicate 'entities'? Wait. That can't be right. Haha, I guess I'll just go read python's documentation. Thanks, anyways.
    – Grant
    Dec 24, 2011 at 4:21
1

You're looking for sets.

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

x = list(set(x) - set(y))

Depending on what you're doing, you'll have to change the code. The above removes everything in y from x. It's like lists but you can do arithmetic on the items.

1

To merge sorted sequences you could use heapq.merge:

import heapq
print list(heapq.merge(xrange(3, 20, 3), xrange(5, 20, 5)))
# -> [3, 5, 6, 9, 10, 12, 15, 15, 18]

To remove duplicate items you could use unique_justseen recipe from itertools documentation:

print list(unique_justseen([3, 5, 6, 9, 10, 12, 15, 15, 18]))
# -> [3, 5, 6, 9, 10, 12, 15, 18]

In this case unique_justseen() could be simplified to:

from itertools import groupby, imap
from operator  import itemgetter

def unique_justseen(iterable):
    return imap(itemgetter(0), groupby(iterable))

These functions don't require input arguments to be sequences. They accept arbitrary iterables (including infinite) e.g., to generate an infinite sequence of multiples of 3 or 5:

import heapq
from itertools import count, takewhile

m3, m5 = count(3, 3), count(5, 5) 
m3_5 = heapq.merge(m3, m5)
uniq_m3_5 = unique_justseen(m3_5) # *all* unique multiples of 3 or 5

To find the solution:

print sum(takewhile(lambda x: x < 1000, uniq_m3_5))
# -> 233168
# check that it is correct
print sum(set(range(3, 1000, 3) + range(5, 1000, 5)))
# -> 233168
print sum(x for x in xrange(1000) if x % 3 == 0 or x % 5 == 0)
# -> 233168
print sumk(3, 1000) + sumk(5, 1000) - sumk(15, 1000)
# -> 233168

Where sumk() is:

def sumk(k, n):
    m = (n-1)//k
    return k*m*(m+1)//2

The formula is from the Wikipedia link provided by @ralu.

0

I don't know if this is less effecient, but making two sets and doing boolean operations on both to remove duplicates seems redundant since the definition of a set is

an unordered collection of distinct hashable objects
(emphasis added)

so just add both ranges to one set and let "creating" the set remove the dupes:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.