Editorial for Lyndon's Golf Contest 1 P9 - Fibonacci: The Finale
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
48 bytes
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 artificial loop, which brings us down to 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 Fibonacci number is equal to
. This directly leads us to the
-byte solution:
print(round((5**.5/2+.5)**int(input())/5**.5))
42 bytes
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 exponentiation! In fact, we can rewrite our solution without even needing
:
x=9**99
print(x**int(input())%(x*x-x-1)//x)
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:
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,
which could have also been used to derive this solution.
Comments