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 a feeling that out there, there were very poor people who didn’t have enough to eat. But they wore wonderfully colored rags and did musical numbers up and down the streets together.”
—Jill Robinson (b. 1936)