When I made my first run through the Project Euler problems I:

- did not care so much for algorithms, as I did about the solution;
- and wrote my code such that its function wouldn’t be obvious. There was an unspoken rule about Project Euler: “don’t give away the answer.” You can paste my code into Visual Studio to test my answer, but the solution should not be obvious at a glance.

I wonder what the fuck went through my mind when I look at some of my old answers. First, many of the resources I used then are the resources I use now; Wikipedia is Wikipedia is Wikipedia. Second, my own attitude has changed. My level of formal math and exposure to algorithms *still* sucks, but now I can see it for what it is and go out of my way to remedy that. Third, *how* isn’t as good as *why*. *How* can answer one question, but *why* can give me the answers to several.

Last night, drunk, I came back to problem #9, which is a devious question about primes and triangles. My original C# solution used a brute force method that I scraped from Google. I copied, pasted and verified, and learned not a fucking thing, so on this attempt I wanted to derive a solution from math.

First up is Fibonacci’s method. There’s a venerability in simple ancient methods that remain the best way to tackle a problem. Given pen, paper, an explanation and time you can work through Fibonacci’s method by hand.

Fibonacci’s method impressed me for how it generates an infinite number of different triples, although it doesn’t generate *all* triples (which is why it doesn’t work for problem #9).

A Pythagorean triple is any three numbers, such that:

`a^2 + b^2 = c^2`

Added together, the square of the first two numbers equals the third.

For example:

```
a = 3^2 = 9
b = 4^2 = 16
c = 5^2 = 25
9 + 16 = 25
25 - 16 = 9
25 - 9 = 16
```

Or in Ruby:

`c = a ** 2 + b ** 2`

The Wikipedia description of Fibonacci’s method is poor. It over-complicates the the method.

```
# 1. Pick one odd number to be a.
a = 7
# 1a. Square a.
a **= 2 # => 49
# 2. b is equal to the sum of *odd numbers* before a.
# 3. If a squared = 49, then b squared = 1 + 3 + 5 + 7 + 9 + (...) + 47 = 576
b = (1..(a - 1)).step(2).reduce(:+) # => 576
# 4. c is equal to the sum of odd numbers that includes a.
# 5. c squared = 1 + 3 + 5 + 7 + 9 (...) + 47 + 49 = 625
c = (1..a).step(2).reduce(:+) # => 625
puts a + b == c
puts "a = #{Math.sqrt(a).to_i}"
puts "b = #{Math.sqrt(b).to_i}"
puts "c = #{Math.sqrt(c).to_i}"
```

Output:

```
true
a = 7
b = 24
c = 25
```

And my implementation:

```
def fib_triple_side(n)
n + 1 >> 1
end
def fib_triple(n)
if n % 2 == 0
warn("Warning: Number #{n} will not generate a Fibonacci triplet with this method.")
[0,0,0]
elsif n == 1
# 1^2 + 0^2 == 1^2
[1,0,1]
else
sides = []
n_squared = n ** 2
sides << n
sides << fib_triple_side(n_squared - 2)
sides << fib_triple_side(n_squared)
end
end
p fib_triple(ARGV[0].to_i.abs)
```

The sum of an sequence of consecutive odd numbers is equal to:

`((last_number + 1) / 2) ** 2`

Add one, then half, then square. I skip the squaring because I want `b`

and `c`

, not `b^2`

and `c^2`

. I also substitute a bitwise shift for the division. You half a binary number if you shift the bits one position right:

```
1010 = 10
0101 = 5
```

```
mark@lucy ruby $ ruby 09.rb 7
[7, 24, 25]
```