For positive integers n and k, let a "k-fibonacci-bitsequence of n" be a bitsequence with k 1 where the 1 on index i describe not Math.pow(2,i) but Fibonacci(i). These positive integers that add up to n, and let the "rank" of a given k- fibonnaci-bitsequence of n be its position in the sorted list of all of these fibonacci-bitsequences in lexicographic order, starting at 0.
For example, for the number 39 we have following valid k-fibonacci-bitsequences, k <=4. The fibonacci numbers behind the fibonacci-bitsequence in this example are following:
34 21 13 8 5 3 2 1
10001000 k = 2 rank = 0
01101000 k = 3 rank = 0
10000110 k = 3 rank = 1
01101100 k = 4 rank = 0
So, I want to be able to do two things:
Can I do this without having to compute all the k-fibonacci-bitsequences of n that come before the one of interest?
For brevity lets say »k-fbs of n« instead of »k-fibonacci-bitsequences of n«.
Can I do this without having to compute all the k-fbs of n that come before the one of interest?
I'm not sure. So far I still have to compute some of fbs. However, you might have thought we had to start from 00…0 and count up – this is not the case. We can do it the other way around and start from the highest fbs and work our way down very efficiently.
This is not a complete answer. However, there are some observations that could help you:
In the following pseudo-code we use the data-type fbs which is basically an array of bools. We can read and write individual bits using mySeq[i] where bit i represents the Fibonacci number fib(i). Just as in your question, the bits myFbs[0] and myFbs[1] do not exist. All bits are initialized to 0 by default. An fbs can be used without [] to read the represented number (n). The helper function #(fbs) returns the number of set bits (k) inside an fbs. Example for n = 7:
fbs meaning representation helper functions
1 0 1 0
| | | `— 0·fib(2) = 0·1 ——— myFbs[2] = 0 #(myFbs) == 2
| | `——— 1·fib(3) = 1·2 ——— myFbs[3] = 1 myFbs == 7
| `————— 0·fib(4) = 0·3 ——— myFbs[4] = 0
`——————— 1·fib(5) = 1·5 ——— myFbs[5] = 1
For any given n we can easily compute the lexicographical maximum (across all k) fbs of n as this fbs happends to be the Zeckendorf representation of n.
function zeckendorf(int n) returns (fbs z):
1 int i := any (ideally the smallest) number such that fib(start) > n
2 while n-z > 0
3 | if fib(i) < n
4 | | z[i] := 1
5 | i := i - 1
zeckendorf(n) is unique and the only fbs of n with k=#(zeckendorf(n)). Therefore zeckendorf(n) has rank=0. Also, there exists no k'-fbs of n with k'<#(zeckendorf(n)).
Any k-fbs of n can be transformed into a (k+1)-fbs of n by replacing the bit sequence 100 by 011 anywhere inside the fbs. This works because fib(i)=fib(i-1)+fib(i-2).
If our input k-fbs of n has rank=0 and we replace the right-most 100 then our resulting (k+1)-fbs of n also has rank=0. If we replace the second-right-most 100 our resulting (k+1)-fbs has rank=1 and so on.
You should be able answer both of your questions using repeated transformations starting at zeckendorf(n). For the first question it might even be sufficient to only look at the k-stable transformations 011…100→100…011 and 100…011→011…100 of the given fbs (think about what these transformations do to the rank).