FIBOBASE - Fibonacci Counting System
English | Vietnamese |
SM is specially passionate to represent integers in different counting systems.
This time, SM spent a lot of time for the Fibonacci Binary counting system.
Features of this system is that there aren’t two digits 1 standing side by side.
An integer M can be expressed as
M10 = anan-1…a2a1F ;
which ai = 1 or 0, ai*ai-1 = 0 and M = anFn + an-1Fn-1 + … + a2F2 + a1F1;
which F0 = F1 = 1, Fi = Fi-1 + Fi-2.
Example:
110 = 1F
210 = 10F
310 = 100F
410 = 101F
510 = 1000F
610 = 1001F
710 = 1010F
SM continously wrote natural numbers 1, 2, 3… in the Fibonacci Binary counting system
and got a infinite string containing 0, 1. The beginning of the string is 110100101100010011010…
Looking at his result, SM wondered how many digits 1 in the first N digits of the sequence ?
Input
An integer N (0 <= N <= 1015).
Output
Result in integer.
Example
Input:
21
Output:
10
Added by: | k[N]i[g]h[T]™ |
Date: | 2009-10-18 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 C++ 4.3.2 ERL NODEJS PERL6 VB.NET |