Project Euler keeps statistics on its users and the problems they’ve solved. Here’s one thing I found interesting. The five most common programming languages used are:

1. C/C++
2. Python (!)
3. Java
4. C#
5. Haskell

I am also impressed with the 958 users who are programming in BASIC, the 653 who are using pencil and paper, the 459 who use Pascal, and the 5 users who grew up in a time when they still taught COBOL!

Here’s problem #6:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Essentially, I’m evaluating:

Because 100 is such a small upper limit, this problem can be solved trivially by brute force. The difference turns out to be 25,164,150.

What’s perhaps more interesting is that there’s an identity for the sum of the squares of first m natural numbers. I found this in the problem notes, which you get access to once you’ve solved a certain problem. The identity is:

That’s new to me!

Ok, I really wanted to do this problem by hand. It reminds me of a programming course I taught a few years ago. One of the assignments for the students was to write a program that printed out the sum of the integers from 1 to 100. One of my more clever students submitted a one-line program:

print 5050

He got points for cleverness!

But I’m working on programming so I’ll avoid solutions like that for now. Here’s the problem:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

And here’s my solution:

def islcm(n):
	for d in range(1,21):
		if n % d != 0:
			return False
	return True

n = 2*3*5*7*11*13*17*19
p = n

while not islcm(p):
	p = p + n

print p

232,792,560 is the least common multiple of the numbers from 1 to 20, verified by WolframAlpha (see the last line under properties).

This week’s Project Euler problem:

Find the largest palindrome made from the product of two 3-digit numbers.

This problem lets you play around with how data is represented in a computer’s memory. It’s much easier to check whether a word (or “string” to be technical) is a palindrome than to check a number so we multiply two 3-digit numbers and convert it to a string.

def ispalindrome(n):
	s = str(n)
	i,j = 0,len(s)-1
	
	while i <= j:
		if s[i] != s[j]:
			return False
		
		i = i + 1
		j = j - 1
	
	return True

x,y,z = 0,0,0

for p in range(100,1000):
	for q in range(p,1000):
		r = p*q
		if ispalindrome(r) and r>z:
			x,y,z = p,q,r

print x,y,z

The largest palindrome here is 906,609, which is the product of 913 and 993.

This was one of those problems where I was kicking myself by the time I had found the solution. Meaning: the solution was much simpler than I initially thought, and I should have known better! The third problem on Project Euler asks:

What is the largest prime factor of the number 600,851,475,143?

First I thought I would just test every integer less than the square root of 600,851,475,143 (which is approximately 775,146) by brute force. But I thought that would take too long so I turned to the Sieve of Eratosthenes to find all primes less than 775,146, and then test only those primes that I found. As it turns out, the sieve is the slow method, and my original method is the faster one!

import math

def isprime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

n = 600851475143
upper = int(math.sqrt(n))

i = upper

while i > 2:
    if (n % i == 0) and (i % 2 != 0):
        if isprime(i):
            print i
    i = i - 1

The largest prime factor? 6857 verified by WolframAlpha.

Here is the description for the second problem from Project Euler:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The Fibonacci sequence starts with the numbers 1 and 1 (or 0,1 or 1,2) and each new term is generated by adding the previous two. For example, the first ten terms of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55.

At first glance, I thought the sum would grow unreasonably large, but I learned something surprising: there are only 33 Fibonacci numbers less than four million and only eleven of them are even.

Here’s my solution in Python:

a = 1
b = 1
c = a+b
sum = 0

while c <= 4000000:
    if c%2==0:
        sum = sum + c
    a = b
    b = c
    c = a+b

print sum

The result is 4,613,732.

Notes

After completing this problem, I remembered that Python offers some cute syntax to make this easier. In my program above, note that I use a third variable c to help find the next Fibonacci number, a fairly typical pattern in most programming languages. Python lets you do the following:

a,b = 1,1
sum = 0

while b <= 4000000:
    if b%2==0:
        sum = sum + b
    a,b = b,a+b

print sum

I have been eager to try Project Euler ever since I heard about it last year. The site hosts a series of mathematical problems, most of which a computer can solve quickly by brute force. Since my programming skills could use some refining, I’m going to see how far I can get.

Problem #1 states

Add all the natural numbers below one thousand that are multiples of 3 or 5.

This is a nice introductory problem as it requires the use of a loop and a conditional statement as well as the modulus operator. Here is my solution in Python.

n = 1;
sum = 0;
while n < 1000:
    if (n%3==0) or (n%5==0):
        sum = sum + n
    n = n + 1
print sum

For the curious, the “answer” is 233,168.