Project Euler solutions

These are my solutions for the problems at Project Euler, which I work on occasionally.

Problem 1

/*

Project Euler problem number 1

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.

*/

#include <stdio.h>

int main() {
    int total = 0;
    for ( int i = 0; i < 1000; i++ ) {
        if ( i % 3 == 0 || i % 5 == 0 ) {
            printf( " %i ", i );
            total = total + i;
        }
    }
    printf( "\nTotal: %i\n", total );
    return 0;
}

Runtime 1ms.

The solution forum for problem 1 supplied a few solutions I thought especially novel or elegant. nicocarlos had an interesting solution, explained by euler:

Nice work, nicocarlos!

He is using a clever improvisation of the formulae for arithmetic progressions. For example, to find the sum of the terms 3,6,9,12,..., you would use (n/2)(a+l), where n is the number of terms, a is the first term, and l is the last term. But to find the last term requires a bit of work. The nth term is given by a+(n-1)d, where d is the common difference. So we need to solve 3+3(n-1)=1000, giving 3(n-1)=997, and n=997/3+1=333.333... However, n must be integer, so int(333.333...)=333, and checking, 3+3(333-1)=999; this is the last term before 1000.

In general, a+(n-1)d=x, gives n=int((x-a)/d+1).

But for this problem we can improve even further, as a=d we get n=int(x/d-d/d+1)=int(x/d).

The nth (last) term, l=a+(n-1)d=d+(int(x/d)-1)*d=d*int(x/d).

Combining this to find the sum, S=(n/2)(a+l)=(int(x/d)/2)*(d+d*int(x/d)).

Simplifying, S=d*int(x/d)*(1+int(x/d))/2.

As the problem asks for the sum of multiples of 3 and 5 we find the sum of each series, but as 3,6,9,... and 5,10,15,... have multiples of 15 in common, we need to subtract the series for 15,30,45,...

However, caution is needed. The problem states below then 1000, so we must use 999 in the formula (otherwise it would include 1000 in the sum, as a multiple of 5):

T = 3*int(999/3)*(1+int(999/3))/2 + 5*int(999/5)*(1+int(999/5))/2 - 15*int(999/15)*(1+int(999/15))/2

Therefore, T = 3*333*(1+333)/2 + 5*199*(1+199)/2 - 15*66*(1+66)/2 = 233168.

lazcatluc offered this Haskel one-linner:

sum [3,6..999] + sum [5,10..999] - sum [15,30..999]

johanlindberg had a similar solution done as a Python list comprehension:

sum([x for x in range(1000) if x % 3== 0 or x % 5== 0])

Problem 2

/*

Project Euler problem 2

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.

*/

#include 

int main() {
    unsigned int total = 0;
    unsigned int n0 = 0;
    unsigned int n1 = 1;
    unsigned int n2;
    while ( total < 4000000 ) {
        n2 = n1;
        n1 = n0 + n1;
        n0 = n2;
        if ( n1 % 2 == 0 ) {
            total = total + n1;
        }
    }
    printf( "Total: %u\n", total );
    return 0;
}

Not nearly the most elegant solution, I guess. I'll have to come back to this one.

Runtime 1ms.

Problem 5

/*

Project Euler 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 number that is evenly divisible by all of the numbers 
from 1 to 20?

*/

#include 

int greatestCommonDivisor( long int n1, long int n2 ) {
    // Euclid's algorithm
    if ( n2 == 0 ) {
        return n1;
    } else {
        return greatestCommonDivisor( n2, ( n1 % n2 ) );
    }
}

int leastCommonMultiple( long int n1, long int n2 ) {
    return ( n1 * n2 ) / greatestCommonDivisor( n1, n2 );
}

int main() {
    long int lcm = 1;

    for ( int i = 1; i <= 20; i++ ) {
        lcm = leastCommonMultiple( i, lcm );
        printf( "%i\t%u\n", i, lcm );
    }

    return 0;
}

Hey! I actually learned some math on this one, and practical math too. I've wondered how to do this in the past (but not enough to figure it out).

Runtime 1ms.

Problem 48

I used Python on this one, because I got tired of fighting with the GMP bignum library for C. Python's built-in data types can handle big integers just fine.

#!/usr/bin/env python

"""
    Project Euler problem 48

    The series, 1^(1) + 2^(2) + 3^(3) + ... + 10^(10) = 10405071317.

    Find the last ten digits of the series, 
    1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).
"""

def ebs( base, exponent ):
    # Exponentiation by squaring
    result = 0
    if exponent == 0:
        result = 1
    elif exponent % 2:
        result = base * ebs( ( base * base ), ( exponent / 2 ) )
    else:
        result = ebs( ( base * base ), ( exponent / 2 ) )
    return result

# Only after implementing the above did I find out that Python's 
# built-in pow() already uses a similarly fast technique. Sigh.

total = 0

for i in range( 1, 1000 ):
#    total += ebs( i, i )
    total += pow( i, i )

print str(total)[-10:]

Runtime under 100ms.