Crumpled Paper

Let it never be said that when you crumple paper over and over again it doesn’t reach the consistency of a soft fabric. Yes, you can see through it too.

Project Euler, Problem 1

The first question on Project Euler is:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The naive method to solve this problem is to go through all the numbers from 1 to 1000, and add it to a running sum if it’s divisible by 3 or 5. Here’s how to say that in python:

sum = 0
for x in range(1,1000):
  if x % 3 == 0 or x % 5 == 0:
    sum += x

Since we’re in the age of the computer, we don’t have to worry about speed issues, but let’s assume we do, when running this code substituting one million for one thousand, it takes a few seconds to reach the answer of 233333166668. There should be a faster way.

Let’s assume that you can figure out a way of telling what the sum of multiples of a certain number below a given number is. Then answering this problem would be as simple as writing

sumofmultiples(3) + sumofmultiples(5) – sumofmultiples(15)

Luckily we have such a method Lets say you have to add all the multiples of 3 from 1 to 100, you would end up adding 3+6+9+12+15+18+…+99 this is the same as adding up 3*(1+2+3+4+5+…+33). If you’ve taken a math course you know that 1+2+3+…+x is equal to x*(x+1)/2 . This allows us to rewrite our code as:

def sumofmultiples(x, max):
  n = (max -1) /x
  return n*(n+1)*x /2
sumofmultiples(3,1000) + sumofmultiples(5,1000) - sumofmultiples(15,1000)

Which runs at a pretty speed for many values of x.

Python Web Server

There was an article on Slashdot recently featuring droopy, a python web server. Droopy’s sole purpose is “to let others upload files to your computer.” Droopy is inspiring because it contains a zero-configuration web server, with only ~300 lines of code. Python rules.

Instead of simply using droopy for transferring files, I’ve taken this as an opportunity to learn more, and I’m slowly modifing droopy to act as a general purpose web server. At the moment it serves up a webpage with a random picture, that refreshes with Ajax at the click of a link. Not impressive, but not bad for the first time I’ve touched either python or javascipt.

My future plans are to first make the system more easily extensible, by pulling out scripts and css styles into their own files. Afterwards I’m going to make a simple picture sharing/rating site. You upload your picture with an optional caption, and others thumbs up or thumbs down your picture.

You can find the current version of the server running at brian.chickenkiller.com and you can get the modified droopy source here.