Binary Representation

There's a very clean way of figuring out which set of Fibonacci values you need. We'll show how to find the chain you want for F(20)F(20) by working backwards.

  • First, write out your number in binary.
  • The last bit of the number determines whether it's odd or even. If it's even, then the chain needs to end by going from n→2nn \rightarrow 2n. If it's odd, the chain needs to end by going from n→2n+1n \rightarrow 2n + 1.
  • Now we know the last step of the chain. We can simply repeat this process to find the next-to-last step, and so on and so forth.
  • At the end, we simply apply that chain in order.

We always start with n=1n = 1, which maps nicely to the fact that any binary number starts with a 11. This elegant correspondence gives us exactly what we need.

Binary Representation

There's a very clean way of figuring out which set of Fibonacci values you need. We'll show how to find the chain you want for F(20)F(20) by working backwards.

  • First, write out your number in binary.
  • The last bit of the number determines whether it's odd or even. If it's even, then the chain needs to end by going from n→2nn \rightarrow 2n. If it's odd, the chain needs to end by going from n→2n+1n \rightarrow 2n + 1.
  • Now we know the last step of the chain. We can simply repeat this process to find the next-to-last step, and so on and so forth.
  • At the end, we simply apply that chain in order.

We always start with n=1n = 1, which maps nicely to the fact that any binary number starts with a 11. This elegant correspondence gives us exactly what we need.