Problem 6: Squares and Sums

I think I am going to abandon any pretense of tackling problems in the proper order. The difficulty varies and the more difficult problems are not only more difficult to solve, but also require more time for the write up.

Problem 6 is one of the easy ones.

The sum of the squares of the first ten natural numbers is,
1^(2) + 2^(2) + ... + 10^(2) = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^(2) = 55^(2) = 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.

So easy that the code doesn't really require a write up, there simply isn't much to this problem.

public class Euler6 {

    private static int sumOfTheSquares(int n) {
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += i * i;
        }

        return sum;
    }

    private static int squareOfTheSum(int n) {
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += i;
        }

        return sum * sum;
    }

    public static void main(String[] args) {
        int n = 100;
        int diff = squareOfTheSum(n) - sumOfTheSquares(n);
        System.out.println(diff);
    }
}

Problem 4: Palindrome Product

I am skipping Problem 3 for now as I want to take my time with the write up. In general I am going to try to make these post more verbose otherwise they aren't very useful to anyone, myself included.

That being said let's take a look at 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 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

First thing we want to do is generate all the products of two 3-digit numbers. That can done with a fairly simple loop where we multiple ever possible number from 100 x 100 to 999 x 999. I'm starting at 999 because I think there may be a way to optimize the generation loop by only looking at the largest, more on this later. So the way this loop works is, starting both factors, i and j, at 999, count down i and then when it drops below 100, reset it 999 and decrement the other factor, j. So the iterations would go, 999 x 999, 998 x 999, 997 x 999 .... 100 x 999, 999 x 998, etc.

Here is the main loop in Python;

    i = 999
    j = 999
    pal = 0
    
    while j > 99:
        result = i * j
        if palindrome(result):
            if result > pal:
                pal = result
        i -= 1
        if i < 100:
            i = 999
            j -= 1
    print pal

In each each iteration we check to see if the product is a palindrome and if it is we check to see if it is larger then the previous palindrome. This means that by the time our loop ends we have the largest possible palindrome.

Determining if the product is a palindrome is easily expressed in Python;

def palindrome(n):
    nString = str(n)
    if nString == nString[::-1]:
        return True
    return False

First thing we do is convert the product n into a string. Once we have that it is easy to reverse the string by using the Python slice(?) operation. The syntax for slice is, start position:end position:value of each step, so what

[::-1]

translates to is, starting at the beginning and ending at the end, go through the string backwards (-1). Once you have the reverse string, you can compare it to the original string and determine if it is a palindrome.

Here is the code in its entirety;

def palindrome(n):
    nString = str(n)
    if nString == nString[::-1]:
        return True
    return False

if __name__ == '__main__':
    i = 999
    j = 999
    pal = 0
    
    while j > 99:
        result = i * j
        if palindrome(result):
            if result > pal:
                pal = result
        i -= 1
        if i < 100:
            i = 999
            j -= 1
    print pal 

There are ways to improve on this implementation. As I mentioned before, there is probably a way to check to make sure that you are only doing the largest possible factors first, say 900 x 900 to 999 x 999, by structuring the while loop so it goes through all factors in each hundreds place. The palindrome could also be implemented in a way that doesn't use string conversion. That being said, this program runs in about a second and works, so any additional optimization is really not needed in this case. However if you were going to test for the largest palindrome product of two 4-digit numbers, this implementation is slow, taking about 110.63 seconds. The official Project Euler answer has an more optimal solution, but since I looked at it I am not going to post the solution here as my own.

Problem 2

Whelp I just wiped out this entire post by accident. That is so awesome. I've learned an important lesson about Blogger.

Oh well, it was probably too long of a post for such an uninteresting problem.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

if __name__ == '__main__':
    sum = 0
    cur = 1
    prev = 0

    while cur + prev <= 4000000:
        newPrev = cur
        cur = cur + prev
        prev = newPrev
        if (cur % 2 == 0):
            sum = sum + cur
    print sum