Hacker News Reader

Comment by sorokod | Hacker News Reader

"just express the original number as a sum of Fibonacci numbers"

This is aways possible, see Zeckendorf's theorem.

https://en.m.wikipedia.org/wiki/Zeckendorf%27s_theorem

As amusing as this is, I could not tell you offhand how to express 121 as a sum of fibonacci numbers. I mean I could figure it out, but I could also either multiply by 1.5 (121mi ~180km) or by 2/3 (121km ~80mi) and it would probably be a little bit faster than the fibonacci way.

As suggested elsewhere, this is more of a party trick then a practical approach to convert between km and miles.

The Wikipedia entry does suggest a greedy algorithm (at each step choosing the largest fib number that fits) though, using that we have

121 = 89 + 21 + 8 + 3

I do think that it has practical applications for the smaller ratios that are easy to remember and/or derive. For example 5:8 is a both a closer approximation than 3:5 that most people use, and is more convenient when miles are a multiple of 5.

One problem with this is that it decomposes 2 * 55 to 89 + 21, etc which makes the conversion slightly harder than just converting 55 and doubling.

Also the decomposition of 88 is 55 + 21 + 8 + 3 + 1. A lot of terms just to find that phi * (Fn - 1) is (F{n+1} - 1) which isn't even very accurate.

Or by the definition that the ratio between consecutive fib numbers approaches Phi, just multiply by 1.618? Though at that point might as well just use the real conversion ratio.

In other news, π² ≈ g.

For 121, I ratio 130:80, then because I started ten under I subtract half that at the end. So about 75.

This is always possible, because 1 is a Fibonacci number.

That is true, the article skips the fact that the approximation using the initial fib numbers is not useful.

from the wiki page:

"Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers."

so, distinct and non-consecutive

Sure, but the conversion method does not require the numbers to be distinct or non-consecutive.

Non consecutive isn't surprising, any consecutive Fibonacci numbers in the sum can be replaced with their sum, which is itself a Fibonacci number by definition

That's not sufficient to be unsurprising.

What if a sum has more than 2 consecutive Fibonacci numbers? That doesn't cause a problem, but it takes a little more work to sort it out.

I find the distinct property much more interesting and non obvious.

It looks like non consecutivity is only there to force unique solutions hence called zeckendorf representations

Reply on news.ycombinator.com