Representing numbers as sums of fibonacci numbers

In summary: So, in summary, if your last two fits in your string are 01, you turn it into a 1 and you're done. If the last two fits in your string are 11, you replace the last two fits with 00.
  • #1
kaalen
20
0
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.
 
Technology news on Phys.org
  • #2
kaalen said:
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.

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?
 
  • #3
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
 
  • #4
AlephZero said:
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

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
If the last fit is a 0, we change it into a 1 and we are done. If
the last fit is a 1, we consider the previous fit as well. If the previous (penulti-mate) fit is a 0—that is, the last two fits in our fitstring are 01—we simply turn
it into a 1, so that now the last two fits are 11. (This works because the last two
positions both correspond to a value of 1.) On the other hand, if the previous
fit is also a 1, so that our fitstring ends with 11, we replace the last two fits by
01, and report a carry to the previous position—what we have done is to convert
x11 = x00 +011 = x00 +100 = (x +1)00 and then added 1 to obtain (x +1)01.
In the general case, then, we are at position i and have a carry. If the fit at po-sition i is a 0, we simply replace it by a 1 and are done. If, however, the fit is a
1, we now have 2Fi to set up in the fitstring and this is not a Fibonacci number.
But 2Fi = Fi+1 + Fi− 2, so we can propagate this carry upward and downward,
replacing the fit at position i by a 0. Now, notice that upward propagation always
follows the pattern (x +1)0: the fit to the right of the carry position is always a 0.
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
 
  • #5
kaalen said:
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

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.
 

What is the Fibonacci sequence?

The Fibonacci sequence is a mathematical sequence where each number is the sum of the two preceding numbers, starting with 0 and 1. So the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

How do you represent numbers as sums of Fibonacci numbers?

To represent a number as a sum of Fibonacci numbers, you need to find the closest Fibonacci number that is less than or equal to the given number. Then, subtract that number from the given number and repeat the process until the remainder is 0. The sum of all the Fibonacci numbers used in this process is the representation of the given number.

What is the significance of representing numbers as sums of Fibonacci numbers?

Representing numbers as sums of Fibonacci numbers can help in identifying patterns and relationships between numbers. It can also be useful in cryptography and coding theory.

Is there a limit to the size of numbers that can be represented as sums of Fibonacci numbers?

No, there is no limit to the size of numbers that can be represented as sums of Fibonacci numbers. However, as the numbers get larger, it may be more difficult to find the closest Fibonacci number and the process may require more steps.

Are there any real-world applications of representing numbers as sums of Fibonacci numbers?

Yes, there are several real-world applications of representing numbers as sums of Fibonacci numbers. For example, it can be used in financial analysis and predicting stock market trends. It can also be used in music theory to create harmonious melodies and in art to create visually pleasing compositions.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
3K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Math Proof Training and Practice
4
Replies
107
Views
14K
  • General Math
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
8K
Replies
5
Views
1K
Replies
9
Views
3K
  • STEM Educators and Teaching
Replies
11
Views
31K
Back
Top