Problem 1 and Sage


In my previous post I mentioned that much of the work I did by hand in the second solution for problem 1, taking all subset of divisors and computing the appropriate sums without constructing sets of multiples, could be done behind the scenes in Sage. I’d like to share that solution now.

# 1 + 2 + ... + n
def sumton(n):
    return n * (n+1) / 2

# sum of multiples of n up to and including b
def sumults(b,n):
    return n*sumton(b//n)

bound = 1000 - 1 # subtract 1 to not include the bound
divs = Set([3,5]) # add as many divisors as you want here
sum = 0

for ss in powerset(divs):
    if(len(ss) > 0):
        sign = (-1)**(len(ss) - 1)
        sum += (sign * sumults(bound,lcm(ss)))

print sum

Notice that lcm is built-in in Sage, so you can save some writing with that. The main improvement comes from the powerset function, so you don’t need to mess with binary strings. According to the documentation, the subsets show up in no particular order, but when I run it the empty set is first. It seems there should be some cute way to not include the empty set at all, and thus remove the if-switch in the for-loop. I can’t quite see what that method would be though, and I guess we wouldn’t technically be allowed to assume the empty set shows up first, based on the documentation. I expect some playing around with iterators, and assuming the empty set comes first, could do it.

I thought I’d also share a helpful website: There, you can sign up for a free account and have access to sage (and any saved work you want) online. Pretty handy. Also saves you installing it.

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: