Editorial for Lyndon's Golf Contest 1 P9 - Fibonacci: The Finale


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Dingledooper

48 bytes

We can keep track of two variables, a = 0 and b = 1, and repeatedly update their values through the transformation (a, b) \rightarrow (b, a + b). A basic implementation might look something like this:

a,b=0,1
for _ in range(int(input())):a,b=b,a+b
print(a)

A well-known golf trick is to use exec with string multiplication to achieve an artifical loop, which brings us down to 48 bytes:

a,b=0,1
exec('a,b=b,a+b;'*int(input()))
print(a)

46 bytes

To go lower, we can use Binet's formula, which tells us that the n^\text{th} Fibonacci number is equal to \lfloor \frac{\varphi^n}{\sqrt{5}} \rceil. This directly leads us to the 46-byte solution:

print(round((5**.5/2+.5)**int(input())/5**.5))

42 bytes

The 42-byte solution below is based off of AlephSquirrel's in-contest submission:

Let's try to alter the 48-byte solution we had from earlier. Instead of updating a and b, we shall encode the two variables as bx + a, where x is some arbitrarily large base such that x is much larger than both a and b. To perform the transformation, we must somehow convert bx + a \rightarrow (b + a)x + b. After some rearranging on the right side, the transformation becomes bx + a \rightarrow b(x + 1) + ax. The question remains of how to accomplish this transformation.

If we multiply bx + a by x, we get bx^2 + ax. Notice that after applying this operation, only the left terms now remain different: bx^2 + ax \rightarrow b(x + 1) + ax.

Now, there is just one more step to complete the transformation, which is to take the left side, modulo x^2 - x - 1. In other words, we claim that (bx^2 + ax) \bmod (x^2 - x - 1) = b(x + 1) + ax. To show this, let's consider how the modulus affects the left and right terms, separately. For the left term, we have bx^2 \bmod (x^2 - x - 1). Since we have defined x to be significantly larger than b, we see that x^2 - x - 1 divides bx^2 at most b times, leaving a remainder of b(x + 1). For the right term, we have ax \bmod (x^2 - x - 1). As before, x is significantly larger than a, so the ax is unaffected by the modulus. Altogether, this shows that (bx^2 + ax) \bmod (x^2 - x - 1) = (b(x + 1) + ax) \bmod (x^2 - x - 1) = b(x + 1) + ax.

To recap, we started by encoding a and b as n = bx + a, where x is some very large base. Then, to move to the next state, we set n to n \times x \bmod (x^2 - x - 1), which we have shown to be equivalent to (b + a)x + b. To obtain the final answer, we can simply find \lfloor \frac{n}{x} \rfloor or n \bmod x, depending on whether we want to extract a + b or b.

A simple implementation of this is shown below:

x=9**99
n=1
exec('n=n*x%(x*x-x-1);'*int(input()))
print(n//x)

Weighing at a hefty 61 bytes, it may seem that we have gone backwards. However, upon closer inspection, observe that we are actually implementing modular exponentation! In fact, we can rewrite our solution without even needing n:

x=9**99
print(x**int(input())%(x*x-x-1)//x)

This is already 43 bytes, which is enough to pass. However, one more byte can be saved by realizing that x*x-x-1 is equivalent to x*x+~x, thus giving us the 42-byte solution:

x=9**99
print(x**int(input())%(x*x+~x)//x)

As a final remark, an astute reader may relate this result to the generating function for the Fibonacci sequence,

\displaystyle  GF(x) = \frac{x}{1 - x - x^2}

which could have also been used to derive this solution.


Comments

There are no comments at the moment.