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.
I have also run my first benchmarks on several different interpreters. I experiment with the -O switch which runs some sort of optimizations before running the script. Interpreters tried include, Python 2 & 3, Pypy, and Jython. The only modifications needed to run in Python 3 were the use of the new Python 3 "print ()" syntax which also worked in all Python 2 flavors.
There is an Ubuntu Launchpad project where I will host all my solution code. You can get your very own copy on a linux box with bzr installed using this command:
bzr branch lp:eulerplay
Or you can browse online at:
SolutionHere's the code for Problem 1:
#!/usr/bin/env python #This program adds all the integer numbers divisible by 3 and 5 #below a selected maximum number. It is a straight forward, #brute-force approach. if __name__ == '__main__' : #boilerplate import sys #for command line input sum = 0; for i in range(0,int(sys.argv)): #int arg required if (i%3==0) or (i%5==0): #divisible by 3 or 5? sum = sum + i #add to the sum print sum #spit it out at the endThis is run using the following command (with the correct number argument for the question asked):
python add35.py 1000
The correct answer is 233168.
This is a simple, brute-force solution. I loop through the entire range and add up the numbers divisible by 3 and 5. The modulo (%) operator lets me see which numbers are evenly divisible.
The first line lets you invoke the script from the command line without specifying the interpreter. Instead of python add35.py 1000, you can just type ./add35.py 1000. This line is not required when the interpreter is run manually, eg pypy add35.py 1000.
#!/usr/bin/env pythonThe sys library lets you access command line arguments in python. There are much fancier and more bullet proof ways of doing this, but none are quite this simple.
import sys astring = sys.argv #argv is the script nameThis is how python handles for loops:
for i in range(x,y):
BenchmarksThe following are some simple benchmarks using the unix "time" command. Python can be run on a variety of interpreters without modification. My 4-core Intel i7 processor positively spoils me for other machines (Hopefully it's not bragging to say, "Your benchmarks may be slower"). Python 2.7.3 comes with my copy of Ubuntu 12.04. I also tried Pypy version 2.7.2, Python 3.2.3 and Jython 2.5.1 running on Java 1.6.0_24.
Code runs in a single thread for all benchmarks in this example. The "real"number is the wall clock time the program took to set up and run. This includes loading the interpreter into memory, any optimizations, and the reporting of results. Later programs may be multi-threaded, but this one didn't need that.
This simple example can be timed with the following command:
time python add35.py 1000
time python -O add35.py 1000
In this case, the -O (optimze) switch takes longer than running unoptimized:
bryan@myComputer:~/play$ time python add35.py 1000
bryan@myComputer:~/play$ time python -O add35.py 1000
Adding a few zeros makes the -O switch (just barely) worthwhile:
bryan@myComputer:~/play$ time python add35.py 100000000
bryan@myComputer:~/play$ time python -O add35.py 100000000
Python 3 took longer and required a modification to the print statement syntax. print sum had to become print(sum). It looks to me like Python 3 has a way to go before it starts getting optimized.
bryan@bryan-Aspire-V3-771:~/play$ time python3 -O add35.py 100000000
On a lark I tried this in pypy. Pypy is a python interpreter written in a version of python instead of c. It seems like an interpreter written in an interpreted language would be the definition of clunky, but this isn't the case for pypy. Pypy runs a lot faster in this simple case:
bryan@myComputer:~/play$ pypy -O add35.py 1000000002333333316666668
Jython crashed with an out of memory error after 37 seconds for the number 100000000. Jython fits my preconceived idea of an interpreter inside an interpreter much better than Pypy. I guess my jython benchmarks will be a bit limited. Jython was able to solve the original problem, also shown below.
java.lang.OutOfMemoryError: java.lang.OutOfMemoryError: Java heap space
bryan@myComputer:~/play$ time jython add35.py 1000
This is a straight-forward problem with a straight forward solution. While a faster algorithm might be found (multiplying by threes and fives until you get to the target number might be faster) but it was not necessary. The solution to the initial question above is 233168.
Pypy is the fastest interpreter for this problem by a factor of almost 7x. Python 3 was slower than Python 2 and Jython was very slow even for this simple problem. Jython ran out of memory and crashed when working with the bigger number.