Archive for November, 2008

Project Euler: Problem 2

November 18th, 2008

An elegant solution to the Fibonacci problem.

from math import sqrt, pow

def fib(n):
    phi = (1 + sqrt(5))/2
    return int((pow(phi, n) - pow(1 - phi, n))/sqrt(5))

if __name__==’__main__’:
    i = 3
    sum = 0
    stop = 4000000

    while True:
        curr = fib(i)

        if curr > stop: break

        sum = sum + fib(i)
        i = i + 3
    print sum

Unlike the other solutions I found online, mine is not done through brute-force. To generate the Fibonacci number at index i, you don’t need to loop through the sequence until i. There is a closed form solution to this. For even-numbers in the sequence, it’s rather simple. An even number occurs with index 3, 6, 9, 12, 15, … Notice a pattern? I hope you do. :)

Posted in Computers at 11:21 AM by Jack | No Comments »

Project Euler: Problem 28

November 10th, 2008

Thought I’d post up my solution to Problem 28 on Project Euler.

After the answer was submitted I read through some of the other code the people have posted. It seems that there are a lot more programmers than mathematicians because almost all of the solutions were brute-force algorithms… and quite a few were written in assembly. *shrug*

Anyway, here is the problem.

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

The first you to notice is that you don’t have to actually construct the spiral in order to solve this problem. It can be shown quite simply that in an nxn spiral, the values of the four corners are as follows:

top-right: n^2
top-left: n^2 - n + 1
bottom-left: n^2 - 2n + 2
bottom-right: n^2 - 3n + 3

Adding all that up yields 4n^2 -6n + 6.

At this point you can easily loop through from 3 to 1001 (in increments of 2) and add up the results. Just make sure you add a 1 to the results for the base case. :)

Of course, if you’re like me you wouldn’t be satisfied with that result. All we’re dealing with are some simple summations, so the result for an nxn spiral should be easily expressed by a formula. In fact, here’s the formula.

Sum(i = 1:500)[4(2*i + 1)^2 - 6(2i + 1) +6]

The beginning reads “sum from i=1 to 500″… I’m not too sure how to type out sigma notations properly.

Converting the summation into closed form gives the formula we’re looking for. I’m leaving out the steps, but it’s fairly simple anyway.

(16n^3)/3 + (10n^2)/2 + 26n/3

And here is the complete solution in Python.

from math import pow
def prob28(n): return (16*pow(n, 3) + 26*n)/3 + 10*pow(n, 2)
print prob28(500) + 1

Posted in Computers at 11:42 PM by Jack | 1 Comment »

Project Euler

November 10th, 2008

I came across this interesting project online. It’s called Project Euler, and the point is to use both mathematical skills and programming skills to solve the posted problems. You can use whatever language to solve, and you input the answer to validate it. So far I’ve worked on the very first one, and it’s pretty fun, both from a programming perspective, and from a math geek POV.

Here’s my solution to Problem 1:

Problem: Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution (Python):
reduce(lambda x,y: x+y, ifilter(lambda x: x%3==0 or x%5==0, range(1,1000)))

:)

Posted in Computers at 2:58 PM by Jack | No Comments »