Solving the Project Euler Problems – 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.

This one oddly seems relatively simple. simply take a number, work out the sum of 1 to that number then square it, work out the sum of the squares of 1 to that number and find the difference between your 2 results. Job done!

Solving the Project Euler Problems – 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?

This one isn’t so much a problem of programming as it is mathematics, as it isn’t just a case of multiplying all the numbers from 1 to 20, that would just result in 20!, which is far bigger than our actual answer.

For reference 20! = 2,432,902,008,176,640,000, which is 2 quintillion 432 quadrillion 902 trillion 8 billion 176 million 640 thousand.

Taking into account the prime numbers up to 20 we have 2, 3, 5, 7, 11, 13, 17 and 19, so our number still needs to be divisible by 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 and 20. Our number so far is 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

By virtue of being multiples of these prime factors, our number is already divisible by 6 (2 × 3), 10 (2 × 5) and 14 (2 × 7). The numbers now remaining are 4, 8, 9, 12, 16, 18 and 20.

If we multiply our number by 2, it is now divisible by 4 (it was divisible by 2), 12 (it was divisible by 6) and 20 (it was divisible by 10). The numbers now remaining are 8, 9, 16 and 18 and our number is 2 × 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

Multiplying by 2 again will make our number divisible by 8, and doing it again will make it divisible by 16, leaving only 9 and 18 and making our number 2 × 2 × 2 × 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19.

Now multiplying our number by 3, as it was already divisible by both 3 and 6, will now make it divisible by 9 and 18.

Our number is now 2 × 2 × 2 × 2 × 3 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 116,396,280. Far smaller than our result for 20! above!

Incidentally, by virtue of being divisible by 3 and 7, our number is also divisible by 21. And as it’s divisible by 2 and 11, it is also divisible by 22.

Solving the Project Euler Problems – 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.

Python’ s very nice way of manipulating integers into strings and string into integers was very helpful with this one, all I had to do was create a function to check if a number is a palindrome (to keep the code neat) and use this to verify our results. If this function returns true and the product of our two numbers is larger than our current result, simply overwrite our result.

Solving the Project Euler Problems – Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?

This problem is the first one that has taken some real effort, as no language seems to have any built-in function for determining whether or not a number is prime.

Part of my memory however is convinced that the R language, which I first worked with all the way back in university, did have a function to list all the prime factors of a number, so either my memory is corrupted or, well, chances are it is, as even after sending hopeful texts to people I’m still in touch with from that same course I came up dry. Relearning R is something for another day though, so for this problem, Python it is!

The reason for Python over PHP, as I could just as unhappily do this one in PHP, is that the point of doing these exercises is to expand my knowledge of multiple languages rather than just “solve them”.

Going forward I will likely solve these in a number of languages, but I certainly envisage the main 2 being PHP and Python.

Trying to work out a function that would return the prime factors of a number has turned out to be a huge pain, and even then by looking at the code you’ll see I still haven’t managed it! This function does however iterate through the number, reducing it down to its highest prime factor, also covering the case where our number itself is prime.

I even tried venturing into the world of generators and using yield rather than return – definitely something to leave for another day frankly, maybe later in these problems, who knows?