Editorial for Lyndon's Golf Contest 1 P9 - Fibonacci: The Finale
Submitting an official solution before solving the problem yourself is a bannable offence.
We can keep track of two variables, and , and repeatedly update their values through the transformation . 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 bytes:
a,b=0,1 exec('a,b=b,a+b;'*int(input())) print(a)
To go lower, we can use Binet's formula, which tells us that the Fibonacci number is equal to . This directly leads us to the -byte solution:
The -byte solution below is based off of 's in-contest submission:
Let's try to alter the -byte solution we had from earlier. Instead of updating and , we shall encode the two variables as , where is some arbitrarily large base such that is much larger than both and . To perform the transformation, we must somehow convert . After some rearranging on the right side, the transformation becomes . The question remains of how to accomplish this transformation.
If we multiply by , we get . Notice that after applying this operation, only the left terms now remain different: .
Now, there is just one more step to complete the transformation, which is to take the left side, modulo . In other words, we claim that . To show this, let's consider how the modulus affects the left and right terms, separately. For the left term, we have . Since we have defined to be significantly larger than , we see that divides at most times, leaving a remainder of . For the right term, we have . As before, is significantly larger than , so the is unaffected by the modulus. Altogether, this shows that .
To recap, we started by encoding and as , where is some very large base. Then, to move to the next state, we set to , which we have shown to be equivalent to . To obtain the final answer, we can simply find or , depending on whether we want to extract or .
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 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 :
This is already 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 -byte solution:
As a final remark, an astute reader may relate this result to the generating function for the Fibonacci sequence,
which could have also been used to derive this solution.