Jay Soo

I wrote a Python script to solve Problem 230 on Project Euler. You can read the problem via the link. It involves a sequence known as Fibonacci Word. The sequences goes as follows:

A
B
AB
BAB
ABBAB
BABABBAB
...

The above sequence of words is Fibonacci in that the length of the words form the sequence 1, 1, 2, 3, 5, 8, …

My solution uses the Golden Ratio as a way to figure out whether we are in the A or B. The relationship between Fibonacci sequence and Gold Ratio is pretty well known.

g = 1.6180339887498949 # golden ratio

t = (
    '14159265358979323846264338327950288419716939937510' +
    '58209749445923078164062862089986280348253421170679',
    '82148086513282306647093844609550582231725359408128' +
    '48111745028410270193852110555964462294895493038196'
)

l = len(t[0])

def D(n):
    i = (n-1) % l
    j =  (n-1) // l
    k = 1 if j-1 <= j//g * g < j else 0 # magic
    return int(t[k][i])

print sum([10**i * D((127 + 19*i) * 7**i) for i in range(18)])

Another good read about this topic is the L-system, and also the Fibonacci Rectangle.

Math rocks! :)