Representation With Negafibonacci Numbers
The Fibonacci sequence can be extended to negative index n using the re-arranged recurrence relation
which yields the sequence of "negafibonacci" numbers satisfying
Any integer can be uniquely represented as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:
- −11 = F−4 + F−6 = (−3) + (−8)
- 12 = F−2 + F−7 = (−1) + 13
- 24 = F−1 + F−4 + F−6 + F−9 = 1 + (−3) + (−8) + 34
- −43 = F−2 + F−7 + F−10 = (−1) + 13 + (−55)
- 0 is represented by the empty sum.
Note that 0 = F−1 + F−2 , for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used.
This gives a system of coding integers, similar to the representation of Zeckendorf's theorem. In the string representing the integer x, the nth digit is 1 if Fn appears in the sum that represents x; that digit is 0 otherwise. For example, 24 may be represented by the string 100101001, which has the digit 1 in places 9, 6, 4, and 1, because 24 = F−1 + F−4 + F−6 + F−9 . The integer x is represented by a string of odd length if and only if x > 0.
Read more about this topic: Zeckendorf's Theorem
Famous quotes containing the word numbers:
“I had but three chairs in my house; one for solitude, two for friendship; three for society. When visitors came in larger and unexpected numbers there was but the third chair for them all, but they generally economized the room by standing up.”
—Henry David Thoreau (1817–1862)