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: sagenb.org. 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.

### Like this:

Like Loading...

*Related*

Tags: nah, prob1

This entry was posted on May 17, 2009 at 4:07 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply