Fibbinary number

In mathematics, the fibbinary numbers are the numbers whose binary representation does not contain two consecutive ones. That is, they are sums of distinct and non-consecutive powers of two.

Relation to binary and Fibonacci numbers

The fibbinary numbers were given their name by Marc LeBrun, because they combine certain properties of binary numbers and Fibonacci numbers:

The number of fibbinary numbers less than any given power of two is a Fibonacci number. For instance, there are 13 fibbinary numbers less than 32, the numbers 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, and 21.
The condition of having no two consecutive ones, used in binary to define the fibbinary numbers, is the same condition used in the Zeckendorf representation of any number as a sum of non-consecutive Fibonacci numbers.
The th fibbinary number can be calculated by expressing in its Zeckendorf representation, and re-interpreting the resulting binary sequence as the binary representation of a number. For instance, the Zeckendorf representation of 19 is 101001, the binary sequence 101001, interpreted as a binary number, represents, and the 19th fibbinary number is 41.
The th fibbinary number is even or odd if and only if the th value in the Fibonacci word is 0 or 1, respectively.

Properties

Because the property of having no two consecutive ones defines a regular language, the binary representations of fibbinary numbers can be recognized by a finite automaton, which means that the fibbinary numbers form a 2-automatic set.
The fibbinary numbers include the Moser–de Bruijn sequence, sums of distinct powers of four. Just as the fibbinary numbers can be formed by reinterpreting Zeckendorff representations as binary, the Moser–de Bruijn sequence can be formed by reinterpreting binary representations as quaternary.
A number is a fibbinary number if and only if the binomial coefficient is odd. Relatedly, is fibbinary if and only if the central Stirling number of the second kind is odd.
Every fibbinary number takes one of the two forms or, where is another fibbinary number.
Correspondingly, the power series whose exponents are fibbinary numbers,
obeys the functional equation
provide asymptotic formulas for the number of integer partitions in which all parts are fibbinary.
If a hypercube graph of dimension is indexed by integers from 0 to, so that two vertices are adjacent when their indexes have binary representations with Hamming distance one, then the subset of vertices indexed by the fibbinary numbers forms a Fibonacci cube as its induced subgraph.
Every number has a fibbinary multiple. For instance, 15 is not fibbinary, but multiplying it by 11 produces 165, which is.