Tautvidas Sipavičius

Web development, programming and tech

Solving Euler Problems

| Comments

I recently discovered projecteuler.net, where you can find mathematical/computer programming problems and solve them.

Lately I’ve been trying to learn more Python, so I decided to give it a try - solving Euler problems with Python.

My progress

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.My solution:

Problem 4 
1
2
3
4
5
6
7
8
9
10
11
12

list = []
for i in range(100, 1000):
    for j in range(100, 1000):
        x = i * j;
        y = str(x)
        if(x == int(y[::-1])):
            list.append(x)
            largest = 0
for i in list:
    if(i > largest):
        largest = i
print largest

It basically runs 2 loops to generate the numbers and each calculated number is turned into a string, reversed, turned back into an integer and compared with the original number. One thing I do not like about the code already is that it uses an additional array, which can be removed with a simple if statement (might not even need that either). It needs refactoring, but it got me the answer, so - moving on.

Problem 5

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?

My solution:

Problem 5 
1
2
3
4
5
6
7
8
9
10
11
12
13

def isEvenlyDivisible(x):
    for i in range(1, 20):
        if(x % i != 0):
            return 0
    return 1
i = 1
found = 0
while(found == 0):
    if(isEvenlyDivisible(i) == 1):
        print i
        found = 1
        break;
    i = i + 1

This one took some time. Because of my brute force approach, it took ~ 5 minutes to complete. I knew that lowest common multiple needed to be found, but because as far as I know LCM is computed for 2 numbers at a time, I couldn’t come up with a quicker algorithm in a few minutes. Rather it became a brute force algorithm, not very effective, but got the job done.

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

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

My solution:

Problem 6 
1
2
3

sumOfSquares = sum([i ** 2 for i in range(1, 101)])
sumSquare = sum(range(1, 101)) ** 2
print sumSquare - sumOfSquares

I think this solution is the best so far. Solved in 3 lines, can be easily merged into a single line. Range generates a list of numbers [1, 2, 3… 99, 100]. Using list comprehension I use the same list and square each list element, that also returns a list, which sum function uses to calculate total sum of squares. ** is used instead of a math.pow function.

Comments