You're replying to a comment by Nathan.

Nathan Permalink
January 15, 2010, 19:31

Any natural number N can be expressed as

1 + 1 + 1 + .... + 1 kilometers (x miles = 2x kilometers). So here's a question...

We know that any natural number can be expressed (not uniquely) as the sum of Fibonacci factors. Given a (potentially huge) natural number, how can you write it as the sum of Fibonacci factors so that the smallest factor is as large as possible?

e.g. for 6

6 = 1 + 5
6 = 2 + 2 + 2
6 = 1 + 2 + 3
6 = 1 + 1 + 2 + 2
6 = 3 + 3
etc.

6 = 3 + 3 is "best" since all other factorizations involve factors less than 3. Similarly, 11 = 5 + 3 + 3 or 11 = 8 + 3 both have smallest factor 3 (and I think you can't do better).

Brute force works for small numbers, but becomes hard for large ones. Any ideas?

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the first letter of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.