Project Euler Problem 1 is driving me insane

[generalguy]

That should work, but again, is very slow since you are iterating over a list. Plus it won't work in general ([x]range has an upper limit, 10**20 won't work, for example).

[howlingmadhowie]

That should work, but again, is very slow since you are iterating over a list. Plus it won't work in general ([x]range has an upper limit, 10**20 won't work, for example).

i wonder how slow that is. one hopes that set(args) just calls a malloc(num(args) * sizeof *ptr).

oh hang on. numbers in python are objects to. oh, i see the problem. it may well have a clever hashing function to make checking for the presence of an object in a set a little faster, but we're still looking at O(n) for every insertion here. nasty.

and this is, as you pointed out, horrible:

>>> set(range(1, 10**10))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: range() result has too many items

[benthebadger]

I have been playing around with python 3. This is what I got for Project Euler Problem 1. Lster has been teaching me python.

t = 0
for i in range(0, 1000):
    if i%3==0 or i%5==0:
        t = t + i

print(t) 

[y-lee]

Of course the most efficient solution is simply

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

In case you are wonder how I came up with this consider the following somewhat more verbose yet equivalent version (in python):

def triangle(n):
    return n*(n + 1)/2
    
def euler1(m):
    m = m - 1
    return 3*triangle(m/3) + 5*triangle(m/5) - 15*triangle(m/15)
    
print euler1(1000)

If this is still not clear consider the fact that the sum of 1 to n is really the nth triangle number, which is what my triangle function above calculates. Now the sum of multiples of say 3 from 3 to 3*n is simply 3 times the nth triangle number by the distributive principle .

Now in the problem Find the sum of all the multiples of 3 or 5 below 1000, we find the sum of the multiples of 3 add that to the sum of the multiples of 5. But since 3 and 5 both divide 15 we have added this twice so we then subtract the sum of the multiples of 15, hence

3*triangle(m/3) + 5*triangle(m/5) - 15*triangle(m/15)

Which btw is really the equialvent to my first statement above:

3*333*167 + 5*199*100 - 15*67*33

[generalguy]

Yep. That's all. If you want to generalize it to a set of divisors D, then you must use the inclusion-exclusion principle.

from itertools import izip
import operator as op

def sdiv(k, n):
    max_div = n / k
    return (((max_div)*(max_div+1)) / 2) * k

def powerset(s):
    d = dict(izip
            ((1<<i for i in xrange(len(s))),
            (set([e]) for e in s)
            ))
    subset = set()
    for i in xrange(1, 1<<len(s)):
        subset = subset ^ d[i & -i]
        yield subset

def euler1(sd,n):
    pset = powerset(sd)
    sum = 0
    for ss in pset:
        sum_divs = sdiv(reduce(op.mul, ss),n-1)
        if len(ss) % 2 == 0:
            sum -= sum_divs
        else:
            sum += sum_divs
    return sum
        

pset = powerset([3,5])
facts = ( ((-1) ** ((len(ss) % 2) + 1)) * sdiv(reduce(op.mul, ss),1000-1) for ss in pset )
print sum(facts)
print euler1([3,5],1000) 

The powerset generator is not mine ( i modifed it a little; it also does not return the empty set); it works because you can use binary numbers to model inclusion of elements in a powerset.

[y-lee]

Yep. That's all. If you want to generalize it to a set of divisors D, then you must use the inclusion-exclusion principle.

. . .

The powerset generator is not mine ( i modifed it a little; it also does not return the empty set); it works because you can use binary numbers to model inclusion of elements in a powerset.

Very Impressive code generalguy