## Yoak: Miles, Kilometers and Fibonacci Numbers

I’m overdue to post a puzzle, but I’m momentarily tapped out. Here’s a curiosity in the meantime: You can provide a very good estimate of a conversion from miles to kilometers by choosing sequential Fibonacci numbers. The conversion rate is 1.609344 kilometers to a mile. So this gives us:

1 | 2 | 1.609 |

2 | 3 | 3.219 |

3 | 5 | 4.828 |

5 | 8 | 8.047 |

8 | 13 | 12.875 |

13 | 21 | 20.921 |

21 | 34 | 33.796 |

34 | 55 | 54.718 |

55 | 89 | 88.514 |

89 | 144 | 143.232 |

144 | 233 | 231.746 |

233 | 377 | 374.977 |

377 | 610 | 606.723 |

610 | 987 | 981.700 |

987 | 1597 | 1588.423 |

This leaves you in pretty good shape if you need to get from Cincinnati, OH to Destin, FL at 610 Miles, but what if you need to convert some distance that doesn’t happen to be a Fibonacci number? Just build it up from parts!

100 miles is 89+8+3. So in kilometers, that’s 144 + 13 + 5 or 162 kilometers. (160.9344 by conversion…)

OK. Here’s a puzzle, sort of. I found this interesting set of numbers recently:

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 53, 371, 5141, 99481 }

The series doesn’t continue. That’s all of them. What’s special about those numbers?

## Blaine said,

December 3, 2009 at 1:38 am

[spoiler]lamicedaxeh (-:[/spoiler]

## jyoak said,

December 3, 2009 at 5:41 pm

Blaine, :-)

## strauss said,

December 4, 2009 at 2:56 am

I really use this trick on a regular basis! This raises another issue: writing numbers “Base Fibonacci”. Can you show that every number can actually be written as the sum of Fibonacci numbers. Furthermore, that every number can be written uniquely as the sum of fibs so that no two are consecutive (i.e. not 8 & 5, for example)

## jyoak said,

December 9, 2009 at 12:03 am

As Blaine cleverly indicated above in the comments above, the set of numbers in the post are the complete set of integers that, when expressed in hexidecimal format, are the reverse of their representation in decimal.

Must think some more about “base Fibonacci”. :-)

## jyoak said,

December 16, 2009 at 9:39 am

With the “Base Fibonacci” question, it is phrased like an easier version and a harder version of the question. I can’t demonstrate the base or “easy” proposition that you can represent all numbers that way. It seems that it must be true, but I can’t show it. Oddly, I can show that if it is true that you can do that, you can do it without using consecutive digits.

Assume a representation of 1’s and 0’s representing “places” low to high from right to left. So numbers are represented by …8-5-3-2-1 and you could represent 16 as 11100 .

The question then is equivalent to whether we can translate this into a numerically equivalent number with no instances of the string ’11’. Because of how Fibonacci numbers work, any string of ‘011’ can be translated to ‘100’ without changing the value of the number. Do this repetitively until there are no more instances. (This is sure to work as you can pad with zeros on the left as needed.)

So 11100 -> 011100 -> 100100

So instead of having 8+5+3 = 16 we have 13+3=16

11111 = 19

11111 -> 011111 -> 100111 -> 101001

101001 = 13+5+1 = 19

## Mike Jarvis said,

December 29, 2009 at 10:53 am

Proof that all numbers are representable in base Fibonacci comes from the fact that F_n <= sum(F_k,k=1..n-1).

So for example 10000 <= 1111 in baseF.

Then we proceed by induction:

Define F(n) = n’th Fibonacci number, which is 1 with n-1 0’s in baseF. (F(1) = 1, F(2) = 10, F(3) = 100, etc.)

Define G(n) = the number that is all 1’s in baseF with n 1’s. (G(1) = 1, G(2) = 11, G(3) = 111, etc.)

A) All numbers from 1 to G(1) are representable in baseF is trivially true, since G(1) = 1.

B) If all numbers from 1 to G(n) are representable in baseF, then all numbers from 1 to G(n+1) are representable.

Proof: G(n+1) = F(n+1) + G(n), so all numbers from F(n+1)+1 to F(n+1)+G(n) (=G(n+1)) are representable from the premise. And F(n+1) itself is certainly representable. So we just need to prove that the two ranges 1 — G(n) and F(n+1) — G(n+1) are overlapping ranges. i.e. that F(n+1) <= G(n) for all n>=1. (This was my statement at the start of the post.)

F(2) = G(1) = 1 (base 10)

F(3) = G(2) = 2 (base 10)

For n > 2, F(n+1) = F(n) + F(n-1) < G(n)

QED.