Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Representing numbers as sums of fibonacci numbers

  1. Oct 25, 2011 #1
    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 $#%&.

    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.
     
  2. jcsd
  3. Oct 25, 2011 #2

    chiro

    User Avatar
    Science Advisor

    Hey kaalen and welcome to the forums.

    Just to clarify are you trying to represent an arbitrary number in a base system that has every base corresponding to the specific fibonnaci number?

    In other words you take any number N and and you write it as a linear combination of other fibonacci numbers?
     
  4. Oct 25, 2011 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Since by defnition [itex]F_{n+1} = F_n + F_{n-1}[/itex] your "pseudo-binary" representaton is not unique. For example 5 could be 1x5 + 0x3 + 0x2 + 0x1 or
    0x5 + 1x3 + 1x2 + 0x1

    The consequece is, you can "carry forwards" using the previous TWO digits, not just one. In other words you can replace ...011... by ...100... anywhere without changing the value of the "number".

    If you do that, you can see a pattern developing in the two lowest-order digits as you count:

    1 = 00001
    2 = 00010
    3 = 00011 = 00100
    4 = 00101
    5 = 00110 = 01000
    6 = 01001
    7 = 01010
    8 = 01011 = 01100 = 10000
    9 = 10001
    etc
     
  5. Oct 25, 2011 #4
    Hmm, this is wrong
    1 = 00001
    2 = 00010 --> that's still 1
    3 = 00011 = 00100 --> that's not 3, it's 2
    4 = 00101 --> that's 3
    5 = 00110 = 01000 --> that's 3
    6 = 01001 --> that's 4
    etc

    If you look at the above instructions (in pdf), they say the following
    I get lost where the bolded text starts.

    This is how I counted so far
    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
    Then for 5 I have the following three options (like you said representation isn't unique)
    5 001011
    5 001100
    5 010000

    If I follow the same rules as for incrementing up to 4 I get the following
    111 that's 4
    last two digits are 11, so we change to 01 and report carry, therefore I get
    (1+1)01 and that's
    1001... which...damn, is not 5 but 4 so I did something wrong. I'll keep staring at my notebook and maybe I'll get it eventually
     
  6. Oct 26, 2011 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    OK, you are using the digits (from right to left) to represent 1, 1, 2, 3, 5, etc

    I ignored the duplicated "1" so my digits represent 1, 2, 3, 5, 8, etc.

    So you can just add a "0" to the end of all my numbers, or replace every final "0" with "00" and every final 1" with "01". or there will be other ways to write some numbers ending in "11" .

    It doesn't make any real difference, except it introduces even more alternative ways to write the same number.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Representing numbers as sums of fibonacci numbers
  1. Beast Numbers (Replies: 1)

  2. Truncating a number (Replies: 4)

  3. Number of digit (Replies: 2)

Loading...