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.

Grant
  • 891
  • 1
  • 9
  • 15
  • Do you need to preserve the order? – Fred Larson Dec 24 '11 at 03:35
  • Since I just need the sum, I'm pretty sure that the order won't affect my outcome. – Grant Dec 24 '11 at 03:39
  • Ah, right. I didn't pay enough attention to the question. `set` should work fine. – Fred Larson Dec 24 '11 at 03: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. – Donald Miner Dec 24 '11 at 03: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 '11 at 04:09
  • The other easy way to go about this is to iterate over all of the numbers and check whether the value is modulo 3 or modulo 5. So `sum([x for x in range(1000) if x % 3 == 0 or x % 5 ==0])` (can be done as a list comprehension as in this example or as a for loop, checking each value and adding it to a return value as you go). – David H. Clements Dec 24 '11 at 04:15
  • related: http://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python – jfs Dec 24 '11 at 05:12

6 Answers6

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.

D.Shawley
  • 58,213
  • 10
  • 98
  • 113
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

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
  • 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 '11 at 04:27
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.

David H. Clements
  • 3,590
  • 2
  • 24
  • 26
  • 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 '11 at 03: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. – Abhranil Das Dec 24 '11 at 04: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 ^_^ – David H. Clements Dec 24 '11 at 04: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 '11 at 04: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.

Brigand
  • 84,529
  • 20
  • 165
  • 173
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.

Community
  • 1
  • 1
jfs
  • 399,953
  • 195
  • 994
  • 1,670
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)))
Zach Young
  • 10,137
  • 4
  • 32
  • 53