Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

# Fibonacci Sum

Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

Hello,
I'm trying to write a program that gives the user the Fibonacci sum of a given number. can i get some help with the formula to do this? Before you answer, i already know how to get the Fibonacci Series, but that isn't what i need. When the user gives a number, the program finds the appropriate combination from the Fibonacci series to give that number.

example:
input -->30
output --> {1,8,21} {1,3,5,21} {1,3,5,8,13}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input -->50
output --> {3,13,34} {1,2,13,34} {3,5,8,34} {1,2,5,8,34} {3,5,8,13,21} {1,2,5,8,13,21}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This link will show you what i mean.
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html

Let me know if this is in any way unclear.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 17081

4

Okay, it looks like you have to find all combinations of Fibonacci numbers that add up to a predetermined sum. Looks like they all have to be different, too.

So if you were going to do this with a pencil and a pile of paper, how would you do it? Once you have figured out a method, try to explain that method in careful detail to yourself. Then take that explanation and convert it to your Java program.

The problem looks a bit complicated to me, I don't think it's one that would be assigned to a beginner. So I'm assuming you have some experience in writing Java code. That should help in the second phase, where you convert your hand-written algorithm to code.

Of course if you get stuck, the forum is here to help. Good luck!
Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

I just need one combination for each sum. I already have a formula, but am having trouble understanding the different components.
Rather than the standard:
f(n)= f(n − 1) + f(n − 2)

I have:
n=f(j)+(n-f(j))

What is j?
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Kirstie Fran wrote:I just need one combination for each sum.

But in the examples above you show three sets for the sum 30 and six sets for the sum 50.

I already have a formula, but am having trouble understanding the different components.

I don't think a formula will be nearly as useful as writing out verbally what needs to happen. My algorithm would be something like: 1. find the largest Fibonacci element whose value is smaller than the desired sum. 2. subtract that value from the sum and replace the sum with the result. 3. unless the result of the subtraction is zero, add the Fibonacci element to the set and repeat steps 1 and 2. Your examples imply that elements can't be repeated, so if the set contains any duplication it must be thrown out; this check probably should happen before step 2.
Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

Dennis Deems wrote: I don't think a formula will be nearly as useful as writing out verbally what needs to happen.

Ok, thanks. I was thinking about doing that, but since the professor provided the formula, i wanted to understand what it was about.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 17081

4

Kirstie Fran wrote:I have:
n=f(j)+(n-f(j))

What is j?

Well, no matter what n, f, and j are, that's just a trivial statement about integer arithmetic. You could also write it as "a = b + (a - b)", which as you should recognize is true for all values of a and b. In particular it's true if one of the values is any Fibonacci number whatever -- which is what f(j) means in the absence of a definition for j.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 17624

33

Kirstie Fran wrote:I just need one combination for each sum. I already have a formula, but am having trouble understanding the different components.
Rather than the standard:
f(n)= f(n − 1) + f(n − 2)

I have:
n=f(j)+(n-f(j))

What is j?

Kirstie Fran wrote:
Dennis Deems wrote: I don't think a formula will be nearly as useful as writing out verbally what needs to happen.

Ok, thanks. I was thinking about doing that, but since the professor provided the formula, i wanted to understand what it was about.

Your professor provided you a formula that can be used to find fibonacci numbers.... you still need to find the fibonacci numbers, create a list of them which can be used to be summed up, and then find all the sums that match the sum that you entered.

Henry

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10519

10

Kirstie Fran wrote:I just need one combination for each sum. I already have a formula, but am having trouble understanding the different components.
Rather than the standard:
f(n)= f(n − 1) + f(n − 2)

I have:
n=f(j)+(n-f(j))

What is j?

j is just some counter, representing some j'th number in the fibonacci sequence. N is any integer (I'm guessing here). So, let n = 7

n = f(j) + (n - f(j))

means

7 = f(j) + (7 - f(j))

we can let j = 3. If i recall correctly, f(3) = 2 (since the sequence is 1,1,2,3... and the 3rd value is 2). So now we have

7 = f(3) + (7 - f(3))

7 = 2 + (7 -2)

7 = 2 + 5

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1363

Wow!

So, with this formula (n = f(j) + (n - f(j))) its quite(not much) simpler that to hit the problem with brut force.

What can be done is: recursion

e.g. 10 can be split as

10 = f(4) + 10 - f(4)
i.e. 10 = 2 + 8

Now, with recursion, we can further reduce 8. Just note that now, we cannot use value of n as 2. Thus,
8 = f(5) + 8 - f(5)
i.e. 8 = 3 + 5

Hence, 10 = 2 + 3 + 5

Now, if we see recursion of Fibonacci series and this formula, those are quite similar:

f(4) = f(3) + f(2) = f(1) + f(2) + f(0) + f(1) = 1 + f(0) + f(1) + 0 + 1 = 1 + 0 + 0 + 0 + 1 = 2

similarly,
10 = f(4) + 10 - f(4) = 2 + 8 = 2 + f(5) + 8 - f(5) = 2 + 3 + 5

The trick is - to choose the value of j carefully. The easiest way to ensure is : n - f(j) must be a Fibonacci number.

How to identify a number is Fibonacci?
Well, if n is Fibonacci number, then either 5*n*n + 4 or 5*n*n - 4 is a perfect square.
e.g. 5*3*3 + 4 = 49 which is perfect square, so 3 is a Fibonacci number.
5*4*4 + 4 = 84 ; 5*4*4 - 4 = 76; both 84 and 76 are not perfect squares, so 4 is not a Fibonacci number.

I hope this helps.

Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Siva Vulchi
Ranch Hand

Joined: Nov 17, 2011
Posts: 30
Here is the program that gives desired results

(Edited to remove complete answer -- Paul C)

Hope it helps!!!

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Anayonkar Shivalkar wrote:

The trick is - to choose the value of j carefully. The easiest way to ensure is : n - f(j) must be a Fibonacci number.

How to identify a number is Fibonacci?
Well, if n is Fibonacci number, then either 5*n*n + 4 or 5*n*n - 4 is a perfect square.
e.g. 5*3*3 + 4 = 49 which is perfect square, so 3 is a Fibonacci number.
5*4*4 + 4 = 84 ; 5*4*4 - 4 = 76; both 84 and 76 are not perfect squares, so 4 is not a Fibonacci number.

I hope this helps.

This is needlessly effortful. Far simpler is to generate the Fibonacci series to the extent that the target sum is exceeded, discard the last element, and confine the remaining operations to the resulting set.
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1363

Dennis Deems wrote:Far simpler is to generate the Fibonacci series to the extent that the target sum is exceeded

Do you mean to say that to choose value of n, we have to run in a loop each time checking the nearest larger Fibonacci number? I guess that would be extremely time complex.
I didn't get this part:
Dennis Deems wrote:discard the last element, and confine the remaining operations to the resulting set.
Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

This is what i have for the maths:

My output looks like this: 30, 29, 28, 26, 23, 18, 10,

Line 15 also gives this error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 46
at Program.main

Where did i go wrong?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109

6

Kirstie Fran wrote:This is what i have for the maths:

Line 15 also gives this error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 46
at Program.main

Where did i go wrong?

Well, for one thing, as the error message is telling you, you're trying to access the 47th element (index 46) of an array that doesn't have that many elements.

So you need to look at your code and try to figure out why you're accessing elements that don't exist. If looking at it doesn't help, then add a bunch of println() calls showing the relevant values at various points and letting you see which code paths are being taken. Compare that to what you get when you pretend you're the computer and step through it with pencil and paper.
Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

Kirstie Fran wrote:
Line 15 also gives this error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 46

I modified line 14: for (int i = 0;i<46; i++)
and have eliminated that error
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109

6

Kirstie Fran wrote:
Kirstie Fran wrote:
Line 15 also gives this error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 46

I modified line 14: for (int i = 0;i<46; i++)
and have eliminated that error

Ew. Ick. No.

Now that's 3 places you have the magic number 46 in your code. Don't do that. It makes it extremely brittle if you have to change that value, and nobody seeing that value will know what it means.

Define a meaningfully-named constant and use that instead. In the for loop, you can either use the constant or the array's length variable. They should be equivalent, but one or the other may be considered more "correct" depending on your semantics.
Kirstie Fran
Ranch Hand

Joined: Feb 16, 2011
Posts: 33

Ok, I see what you mean; that makes sense.
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1363

Anayonkar Shivalkar wrote:The trick is - to choose the value of j carefully. The easiest way to ensure is : n - f(j) must be a Fibonacci number.

Please don't go by this. It does not work that way
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Instead of generating the first 46 fibonnacci numbers, I would only generate them until they exceed the value of the user input. Beyond that point you know that they won't be useful. So instead of i < 46, I would make my loop iteration condition fib[i - 1] + fib[i - 2] < input.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4284

2
i didn't read all the posts but i gave Henry a thumbs up because i am working on a similar problem. first i have to generate fibonacci numbers and store them somewhere, and then iterate through them adding up the even numbers.

i also agree this might be a chance to use recursion but recursion is so difficult for us mere mortals

SCJP
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
Randall Twede wrote:i didn't read all the posts but i gave Henry a thumbs up because i am working on a similar problem. first i have to generate fibonacci numbers and store them somewhere, and then iterate through them adding up the even numbers.

i also agree this might be a chance to use recursion but recursion is so difficult for us mere mortals

In general, where a simpler approach is readily available, recursion should be avoided. Generation of the Fibonacci series is trivial.

Don't get me started about those stupid light bulbs.

subject: Fibonacci Sum
Fibonacci Generators and the loop commands.
while loops and all that fun stuff, need assignment help
fibonacci program