# Finding the binary representation of the $n$th Fibonacci term

Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6.

My current approach: Find nth term (in decimal) in Fibonacci sequence using matrix exponentiation method and then convert the nth term to binary and then find number of 1's.

My question: Can this program be improved if I straight-away work with binary numbers? Is there a comparatively faster way to find nth term in Fibonacci sequence if we deal with binary numbers?

Fibonacci sequence in decimal: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Fibonacci sequence in binary: 1, 10, 11, 101, 1000, 1101, 10101, 100010, 110111, 1011001, ...

-
Computers work in binary by default.... –  Hurkyl Feb 7 at 10:08
I think you got me wrong! I am asking, whether there is a faster way if we use binary mathematics, like bit-shifting, etc? Or the binary sequence itself gives a pattern to find nth term quickly? –  stalin Feb 7 at 10:11
The number of ones is tabulated at oeis.org/A011373 and code is given for Maple and Mathematica. –  Gerry Myerson Feb 7 at 10:41