Problem 16: Sum of Digits

Another really simple one.

2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^(1000)?

Actually this is the simplest problem so far. A simple conversion to a String and an iteration is all that is needed.

numberString = str(2**1000)
sum = 0
for number in numberString:
    sum += int(number)
print sum

Problem 10: Sum of Primes

Problem 10 is fairly interesting.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

The solution is a lot easier if you are familiar with the Sieve of Eratosthenes. Wikipedia has a fairly good article on the Sieve, in which they sum up the steps as follows;

1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
2. Initially, let p equal 2, the first prime number,
3. While enumerating all multiples of p starting from p², strike them off from the original list,
4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
5. Repeat steps 3 and 4 until p² is greater than n.
6. All the remaining numbers in the list are prime.

Seems easy enough, here is an fairly direct translation in Python;

start = 2
numbers = range(start, n + 1)

for i in numbers:
    multiple = i
    while i * multiple <= n:
        try:
            numbers.remove(i * multiple)
        except ValueError:
            pass
        multiple += 1
        
return numbers

Python's ability to remove items from a List seems to be lacking here; at the very least the code is a little more terse then usual. The remove operation raises an error is the element is not present, so telling it to pass will simply ignore the resulting error. I am sure there is a terser way to represent the Sieve in Python, but the code above emphasizes readable and is comparable to pseudo code, except for the error handling.

The problem with the previous implementation is that it is slow. with a N of 10000 taking about a second, a N of 100000 taking ~101 seconds, and a N of 1000000 uncomfortably heating up my laptop, though it should clock in at about an hour.

Excuse my sloppy Big O notation, but according to Wikipedia, the complexity of the Sieve is O(n(logn)(loglogn)). 

The red flag here is the remove call. While I'm not sure how Python implements List.remove, according to the documentation it removes the first instance of the element it is searching for. So the method needs to iterate the list until it finds the element, and then readjust the remainder of the List, which is a costly operation, especially inside a for and while loop. I believe this would add another n to the complexity, O(n^2(logn)(loglogn)). (Edit: please disregard my sloppy Big O notation here, without knowing the implementation details behind the Python List remove operation I can only hazard a guess. We know that the remove operation stops at the first instance of the char, but then the List must be have an element removed, which can vary in cost depending on the data structure used. Analysis of this operation requires Python guru skills that I currently lack.)  I am really out of practice with Big O notation, so please correct me if I am wrong here.

It took me awhile to figure out how to get the run time of the sieve down, I eventually went online to try to find a hint of how to improve performance. Someone on the internet recommended replacing the composite numbers with zeros. It is painfully obvious once you see it; get rid of the remove operation altogether. Instead of removing the non-prime (composite) elements, replace them with a placeholder value.

Here is the improved implementation;

start = 2
numbers = range(start, n + 1)
placeholder = 0

#set composite numbers as a placeholder value
for i in range(len(numbers)):
    cur = numbers[i]
    if cur != placeholder:
        multiple = cur
        while cur*multiple <= n:
            listPos = (cur*multiple) - start
            numbers[listPos] = placeholder
            multiple += 1

#make a list of primes
primes = []
for i in numbers:
    if i != placeholder:
        primes.append(i)

return primes

This new implementation can handle the two million that we were looking for in problem in about 2 seconds. All that is left is to sum the primes. Here is the complete code;

def sieve(n):
    start = 2
    numbers = range(start, n + 1)
    placeholder = 0
    
    #set composite numbers as a placeholder value
    for i in range(len(numbers)):
        cur = numbers[i]
        if cur != placeholder:
            multiple = cur
            while cur*multiple <= n:
                listPos = (cur*multiple) - start
                numbers[listPos] = placeholder
                multiple += 1
    
    #make a list of primes
    primes = []
    for i in numbers:
        if i != placeholder:
            primes.append(i)
    
    return primes

if __name__ == '__main__':
    primes = sieve(2000000)
    sum = 0
    for i in primes:
        sum += i
    print sum

Problem 8: Consecutive Digits

Another fairly simple problem.

Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

All you have to do is parse through the 1000 char string, taking chunks of 5 characters at a time and then seeing which subset has the largest product.

#raw input is large string from the problem
# surrounded by triple quotes
#remove whitespace from raw input
input = ''.join(rawInput.split())

position = 0
largestProduct = 0
while position < len(input) - 5:
    product = 1
    for i in range(position, position + 5):
        product *= int(input[i])
    if product > largestProduct:
        largestProduct = product
    position += 1
print 'Largest Product: ', largestProduct

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

Problem 1

First problem of the project and it is a pretty simple one.

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.

package euler1;

import java.util.Arrays;
import java.util.Collection;

/**
 * Project Euler Problem 1
 */
public class Main {

    public static void main(String[] args) {
        int sum = generateMultiples(1000, Arrays.asList(new Integer[]{3, 5}));
        System.out.println(sum);
    }

    private static int generateMultiples(int end, Collection multiples) {
        int sum = 0;
        
        for (int i = 0; i < end; i++) {
            for (Integer multiple : multiples) {
                if (i % multiple == 0) {
                    sum += i;
                    break;
                }
            }
        }
        return sum;
    }
}

Not much of interest here, aside from noting that writing this problem in Java felt like writing enterprise FizzBuzz. The use of Collections and Integers might be over engineering on my part, but what can I say, I like the way the For Each loop looks.