awesty

Problem 2 was another easy one.

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.

I brute forced it again, with a bit of optimisation.

We only need to add the even Fibonacci numbers, and if you look closely at the example above you might notice a pattern.

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

An even number shows up every 3 numbers. So instead of calculating every number in the sequence below 4,000,000 and then test if it’s even, we can calculate every third number and add it straight onto the total. Here is what I came up with.

sum = 0
prev = 1
current = 2
while current < 4000000:
    sum = sum + current
    n = current
    current += 2 * (current + prev)
    prev += 2 * n
    print current
print sum

For fun I also did it in 4 lines. This way is very inefficient, but it is small.

a = [1, 2]
while a[len(a) - 1] < 4000000:
    a.append(a[len(a) - 1] + a[len(a) - 2])
print sum(filter(lambda x: x % 2 == 0, a))

Can anyone think of a shorter and/or more efficient way?

Problem 1 is extremely simple:

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.

I chose to just brute force it. I looped through numbers 1 - 999, checked if it was a multiple of 3 or 5 and if it was added it onto the total.

sum = 0
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        sum = sum + i
print sum

After a bit of editing I was able to get it onto 1 line:

print sum(filter(lambda x: x % 3 == 0 or x % 5 == 0, range(1,1000)))

Not the most efficient solution, but it works.

Lately I have been spending a lot of my time on Project Euler. Project Euler is a site with a heap of math problems (209 to be exact) ranging in difficulty. You pick your favourite programming language and try to solve them.

They start of pretty easy:

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.

And get very, very hard:

A best approximation to a real number x for the denominator bound d is a rational number r/s (in reduced form) with s  d, so that any rational number p/q which is closer to x than r/s has q d.

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. 9/40 has the two best approximations 1/4 and 1/5 for the denominator bound 6. We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

How many ambiguous numbers x = p/q, 0  x  1/100, are there whose denominator q does not exceed 10⁸?

I’ve done 15 so far. I’ve found that it’s great if your trying to learn a new language. I’m doing mine in python, which I’ve never really used before.

I’m going to start making a few posts about trying to solve them.