Many solutions

Let the number of possible $2^k$ -tuples be denoted as $F(k)$ .

First, we may conclude that f(1)=2. Clearly f(1) is not 1 and it cannot be 3 (or else f(3)=4 leading to bounding problems). Thus it follows that $f(2^k)=2^{k+1}$ .

From here, casework on f(3). It is either 5, 6, or 7. (7 results in a symmetric case with 5.)

If f(3)=5 it follows that f(5)=12. Then f(6),f(7) must be the pairs (13,14), (13,15), or (14,15). Either way, there is one gap.

We will show that the other thing doesn't matter with a small lemma.

Lemma: if f(a)=b and f(a+1)=b+1 then it follows that f(x) is fixed on all intervals $[2^ka,2^k(a+1)]$ and $[2^kb,2^k(b+1)]$ .

Proof: Induction. f(b)=4a, f(b+1)=4a+4, f(4a)=4b, f(4a+4)=4b+4 and tight bounding takes care of the rest. (f(4a+1)=4b+1 and so forth)

So all that remains is a gap of 2 somewhere. Let's say it's (13,14). Then f(14)=28 and f(16)=32. We now have a gap of 4, for f(15). It has 3 options, 29, 30, 31. So this can be recursed to before. There are 6 ways this happens (2 ways for f(3) = 5,7; 3 ways for our choice of f(6), f(7) or f(5), f(6).)

If f(3)=6 it follows that f(6)=12. Importantly, f(5) and f(7) have three options. They exactly mirror the choice we had for f(3). Our choices for f(5), f(7) are independent so we square F(n-1).

So our recurrence is $F(n)=F(n-1)^2+6F(n-2)$ , with initial conditions F(1)=1 and F(2)=3. We can easily evaluate F(6) mod 1000 to get 779.