A number base using the Fibonacci numbers for its places. Since the first two Fibonacci numbers are both 1, in this base all integers end with a 0, or else you simply omit that place as being redundant. I'll take the second option in my examples.

So the number 42 is 10010000: 0*1 + 0*2 + 0*3 + 0*5 + 1*8 + 0*13 + 0*21 + 1*34. It turns out (not hard to prove this) that you only need the digits 0 and 1. Also, you have to adopt the convention that consecutive 1's are forbidden, since 11=100 (1+2=3, by the very definition of the Fibonacci series) and you'd wind up with multiple representations for the same number. Under that constraint, numbers have a unique representation.

It's a special kind of torture/pleasure to work with such numbers... I learned weird things about what happens when you work on simplifying the digits when you get one which is more than 1, to get it back into a well-formed digit string. And try coding your HP calculator to compute them. I did.


Added December 11, 2000:

apirkle is right, but that approach isn't always the easiest to use. It requires that you compute Fibonacci numbers, which isn't always convenient. What I did in programming my calculator was to notice that a "2" in the ith place was the same as a "1" in the i-2nd place and a "1" in the i+1st place (not hard to prove this). Generally, when a number was >1, add half to the place above it and half to the place two below it and set it to zero (or one if it was odd to start with). Then repeat that. Alternate with the identity of making consecutive 1's into 0's and replacing with a 1 in the next higher place (so whenever there are two >1 places in a row, add the smaller of them to the next higher place and subtract it from the two, leaving one zero). Keep working with those two, and eventually you get to all 1s and 0s.

ariels, I'm going to have to look at that! Ah, I see why it works. Cool.

Knuth points out a very useful property of the Fibonacci number base: conversions between kilometers and miles.

All you do is shift the digits!
For example, say I want to convert 65kmh to mph. Well, 6510 = 55 + 8 + 2 = 100010010fib, and shifting (right) we have 10001001fibmph = (34 + 5 + 1)mph = 4010mph (it's actually closer to 4110mph).

Details of why this works are left as an exercise to the interested reader.

Log in or register to write something here or to contact authors.