Английская Википедия:Fibbinary number
Шаблон:Short description 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.Шаблон:R
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:Шаблон:R
- 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.Шаблон:R
- 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.Шаблон:R
- The <math>n</math>th fibbinary number (counting 0 as the 0th number) can be calculated by expressing <math>n</math> in its Zeckendorf representation, and re-interpreting the resulting binary sequence as the binary representation of a number.Шаблон:R For instance, the Zeckendorf representation of 19 is 101001 (where the 1's mark the positions of the Fibonacci numbers used in the expansion Шаблон:Nowrap), the binary sequence 101001, interpreted as a binary number, represents Шаблон:Nowrap, and the 19th fibbinary number is 41.
- The <math>n</math>th fibbinary number (again, counting 0 as 0th) is even or odd if and only if the <math>n</math>th value in the Fibonacci word is 0 or 1, respectively.Шаблон:R
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.Шаблон:R
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.Шаблон:R
A number <math>n</math> is a fibbinary number if and only if the binomial coefficient <math>\tbinom{3n}{n}</math> is odd.Шаблон:R Relatedly, <math>n</math> is fibbinary if and only if the central Stirling number of the second kind <math>\textstyle \left\{{2n\atop n}\right\}</math> is odd.Шаблон:R
Every fibbinary number <math>f_i</math> takes one of the two forms <math>2f_j</math> or <math>4f_j+1</math>, where <math>f_j</math> is another fibbinary number.Шаблон:R Correspondingly, the power series whose exponents are fibbinary numbers, <math display=block>B(x)=1+x+x^2+x^4+x^5+x^8+\cdots,</math> obeys the functional equationШаблон:R <math display=block>B(x)=xB(x^4)+B(x^2).</math>
Шаблон:Harvtxt provide asymptotic formulas for the number of integer partitions in which all parts are fibbinary.Шаблон:R
If a hypercube graph <math>Q_d</math> of dimension <math>d</math> is indexed by integers from 0 to <math>2^d-1</math>, 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.Шаблон:R
Every number has a fibbinary multiple. For instance, 15 is not fibbinary, but multiplying it by 11 produces 165 (101001012), which is.Шаблон:R
References
