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.^[1][2]

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:^[1]

• 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.^[1]
• 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.^[1]
• The ${\displaystyle n}$th fibbinary number (counting 0 as the 0th number) can be calculated by expressing ${\displaystyle n}$ in its Zeckendorf representation, and re-interpreting the resulting binary sequence as the binary representation of a number.^[1] For instance, the Zeckendorf representation of 19 is 101001 (where the 1's mark the positions of the Fibonacci numbers used in the expansion 19 = 13 + 5 + 1), the binary sequence 101001, interpreted as a binary number, represents 41 = 32 + 8 + 1, and the 19th fibbinary number is 41.
• The ${\displaystyle n}$th fibbinary number (again, counting 0 as 0th) is even or odd if and only if the ${\displaystyle n}$th value in the Fibonacci word is 0 or 1, respectively.^[3]

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.^[4]

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.^[5]

A number ${\displaystyle n}$ is a fibbinary number if and only if the binomial coefficient ${\displaystyle {\tbinom {3n}{n}}}$ is odd.^[1] Relatedly, ${\displaystyle n}$ is fibbinary if and only if the central Stirling number of the second kind ${\displaystyle \textstyle \left\{{2n \atop n}\right\}}$ is odd.^[6]

Every fibbinary number ${\displaystyle f_{i}}$ takes one of the two forms ${\displaystyle 2f_{j}}$ or ${\displaystyle 4f_{j}+1}$, where ${\displaystyle f_{j}}$ is another fibbinary number.^[3][7] Correspondingly, the power series whose exponents are fibbinary numbers, $${\displaystyle B(x)=1+x+x^{2}+x^{4}+x^{5}+x^{8}+\cdots ,}$$ obeys the functional equation^[2] $${\displaystyle B(x)=xB(x^{4})+B(x^{2}).}$$

Madritsch & Wagner (2010) provide asymptotic formulas for the number of integer partitions in which all parts are fibbinary.^[7]

If a hypercube graph ${\displaystyle Q_{d}}$ of dimension ${\displaystyle d}$ is indexed by integers from 0 to ${\displaystyle 2^{d}-1}$, 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.^[8]

Every number has a fibbinary multiple. For instance, 15 is not fibbinary, but multiplying it by 11 produces 165 (10100101₂), which is.^[9]

References

1. Sloane, N. J. A. (ed.), "Sequence A003714 (Fibbinary numbers)", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
2. Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF), Springer, pp. 62, 755–756.
3. Kimberling, Clark (2004), "Ordering words and sets of numbers: the Fibonacci case", in Howard, Frederic T. (ed.), Applications of Fibonacci Numbers, Volume 9: Proceedings of The Tenth International Research Conference on Fibonacci Numbers and Their Applications, Dordrecht: Kluwer Academic Publishers, pp. 137–144, doi:10.1007/978-0-306-48517-6_14, ISBN 978-90-481-6545-2, MR 2076798
4. Allouche, J.-P.; Shallit, J.; Skordev, G. (2005), "Self-generating sets, integers with missing blocks, and substitutions", Discrete Mathematics, 292 (1–3): 1–15, doi:10.1016/j.disc.2004.12.004, MR 2131083
5. Sloane, N. J. A. (ed.), "Sequence A000695 (Moser–de Bruijn sequence)", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
6. Chan, O-Yeat; Manna, Dante (2010), "Congruences for Stirling numbers of the second kind" (PDF), Gems in Experimental Mathematics, Contemporary Mathematics, vol. 517, Providence, Rhode Island: American Mathematical Society, pp. 97–111, doi:10.1090/conm/517/10135, ISBN 978-0-8218-4869-2, MR 2731094
7. Madritsch, Manfred; Wagner, Stephan (2010), "A central limit theorem for integer partitions", Monatshefte für Mathematik, 161 (1): 85–114, doi:10.1007/s00605-009-0126-y, MR 2670233, S2CID 15008932
8. Klavžar, Sandi (2013), "Structure of Fibonacci cubes: a survey", Journal of Combinatorial Optimization, 25 (4): 505–522, doi:10.1007/s10878-011-9433-z, MR 3044155, S2CID 5557314
9. Sloane, N. J. A. (ed.), "Sequence A300867 (The least positive k such that k * n is a Fibbinary number)", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation