I have the following homework to do. Apologies if it seems very easy - I just had a knee surgery and I think I can't really think straight due to pain medication, I feel so fuzzy and sleepy and my damn knee still hurts like $#%&.(adsbygoogle = window.adsbygoogle || []).push({});

So instead of representing numbers in a binary way I need to represent them as sums of fibonacci numbers where i-th number indicates whether that fibonacci number is part of the sum.

For example string 101110 represents the number f6+f4+f3+f3+f2 = 14.

What I need to do is come up with an algorithm to increment such fibonacci counter.

I found these solutions on the internet http://lcbb.epfl.ch/algs10/ex2-sol.pdf but I'm not even able to wrap my head around that at the moment.

If I go baby steps and count from 0 upwards

853211 (these are just fib. numbers to help with my short attention span)

0 000000

1 000001

2 000011 - last two flits are 01, we change them to 11

3 000101 - change last two to 01 and report carry 1

4 000111 - last two flits are 01, simply change to 11

5 001001 - last two flits are 11, change to 01, carry 1 to the 3rd position and then one more forward cause the 3rd one is 1

The result is 4 instead of 5 so I messed it up somewhere.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Representing numbers as sums of fibonacci numbers

Loading...

**Physics Forums | Science Articles, Homework Help, Discussion**