Nathan comment on Using Fibonacci Numbers to Convert from Miles to Kilometers and Vice Versa

Privacy Controls Software from ParetoLogic

A non-virtual function says, you have to do this and you must do it this way. A virtual function says you have to do this, but you don't have to do it this way. That's their fundamental difference.

Scott Meyers

I am doing a startup!

Cross-browser testing from your browser

I have written my third book!

Perl one-liners explained

You're viewing a comment by Nathan and its responses.

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

Reply To This Comment

Name:

E-mail: (why do I need your e-mail?)

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

Website:

Comment:

Comment Help

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

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

Using Fibonacci Numbers to Convert from Miles to Kilometers and Vice Versa

Reply To This Comment

Friends

Info

Advertise on catonmat