Counting the bits set in the Fibonacci number system?

Question

We know that, each non negative decimal number can be represented uniquely by sum of Fibonacci numbers(here we are concerned about minimal representation i.e- no consecutive Fibonacci numbers are taken in the representation of a number and also each Fibonacci number is taken at most one in the representation).

For example:

1->  1
2-> 10
3->100
4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);

so each decimal number can be represented in the Fibonacci system as a binary sequence. If we write all natural numbers successively in Fibonacci system, we will obtain a sequence like this: 110100101… This is called “Fibonacci bit sequence of natural numbers”.

My task is is counting the numbers of times that bit 1 appears in first N bits of this sequence.Since N can take value from 1 to 10^15,Can i do this without storing the Fibonacci sequence ?

for example: if N is 5,the answer is 3.

Answer 1

So this is just a preliminary sketch of an algorithm. It works when the upper bound is itself a Fibonacci number, but I'm not sure how to adapt it for general upper bounds. Hopefully someone can improve upon this.

The general idea is to look at the structure of the Fibonacci encodings. Here are the first few numbers:

     0
     1
    10
   100
   101
  1000
  1001
  1010
 10000
 10001
 10010
 10100
 10101
100000

The invariant in each of these numbers is that there's never a pair of consecutive 1s. Given this invariant, we can increment from one number to the next using the following pattern:

1. If the last digit is 0, set it to 1.
2. If the last digit is 1, then since there aren't any consecutive 1s, set the last digit to 0 and the next digit to 1.
3. Eliminate any doubled 1s by setting them both to 0 and setting the next digit to a 1, repeating until all doubled 1s are eliminated.

The reason that this is important is that property (3) tells us something about the structure of these numbers. Let's revisit the first few Fibonacci-encoded numbers once more. Look, for example, at the first three numbers:

  00
  01
  10

Now, look at all four-bit numbers:

1000
1001
1010

The next number will have five digits, as shown here:

1011 → 1100 → 10000

The interesting detail to notice is that the number of numbers with four digits is equal to the number of values with up to two digits. In fact, we get the four-digit numbers by just prefixing the at-most-two-digit-numbers with 10.

Now, look at three-digit numbers:

000
001
010
100
101

And look at five-digit numbers:

10000
10001
10010
10100
10101

Notice that the five-digit numbers are just the three-digit numbers with 10 prefixed.

This gives us a very interesting way for counting up how many 1s there are. Specifically, if you look at (k+2)-digit numbers, each of them is just a k-digit number with a 10 prefixed to it. This means that if there are B 1s total in all of the k-digit numbers, the number of Bs total in numbers that are just k+2 digits is equal to B plus the number of k-digit numbers, since we're just replaying the sequence with an extra 1 prepended to each number.

We can exploit this to compute the number of 1s in the Fibonacci codings that have at most k digits in them. The trick is as follows - if for each number of digits we keep track of

1. How many numbers have at most that many digits (call this N(d)), and
2. How many 1s are represented numbers with at most d digits (call this B(d)).

We can use this information to compute these two pieces of information for one more digit. It's a beautiful DP recurrence. Initially, we seed it as follows. For one digit, N(d) = 2 and B(d) is 1, since for one digit the numbers are 0 and 1. For two digits, N(d) = 3 (there's just one two-digit number, 10, and the two one-digit numbers 0 and 1) and B(d) is 2 (one from 1, one from 10). From there, we have that

• N(d + 2) = N(d) + N(d + 1). This is because the number of numbers with up to d + 2 digits is the number of numbers with up to d + 1 digits (N(d + 1)), plus the numbers formed by prefixing 10 to numbers with d digits (N(d))
• B(d + 2) = B(d + 1) + B(d) + N(d) (The number of total 1 bits in numbers of length at most d + 2 is the total number of 1 bits in numbers of length at most d + 1, plus the extra we get from numbers of just d + 2 digits)

For example, we get the following:

 d     N(d)      B(d)
---------------------
 1       2          1
 2       3          2
 3       5          5
 4       8         10
 5      13         20

We can actually check this. For 1-digit numbers, there are a total of 1 one bit used. For 2-digit numbers, there are two ones (1 and 10). For 3-digit numbers, there are five 1s (1, 10, 100, 101). For four-digit numbers, there are 10 ones (the five previous, plus 1000, 1001, 1010). Extending this outward gives us the sequence that we'd like.

This is extremely easy to compute - we can compute the value for k digits in time O(k) with just O(1) memory usage if we reuse space from before. Since the Fibonacci numbers grow exponentially quickly, this means that if we have some number N and want to find the sum of all 1s bits to the largest Fibonacci number smaller than N, we can do so in time O(log N) and space O(1).

That said, I'm not sure how to adapt this to work with general upper bounds. However, I'm optimistic that there is some way to do it. This is a beautiful recurrence and there just has to be a nice way to generalize it.

Hope this helps! Thanks for an awesome problem!