# Project Euler Problem 25

rajarshi roy

Greenhorn

Posts: 21

posted 6 years ago

I was trying problem 25 given in the site Project Euler .

It goes like this

Now here I have a problem.No data type that I know can hold a number 1000 digit long..Anyways,I wrote a code

Evidently,this code cannot compute what I want,simply because the data type is not suitable to hold such a huge number.So,what can I do to deal with this kind of situation and get the desired output???

It goes like this

The Fibonacci sequence is defined by the recurrence relation:

F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

F_(1) = 1

F_(2) = 1

F_(3) = 2

F_(4) = 3

F_(5) = 5

F_(6) = 8

F_(7) = 13

F_(8) = 21

F_(9) = 34

F_(10) = 55

F_(11) = 89

F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Now here I have a problem.No data type that I know can hold a number 1000 digit long..Anyways,I wrote a code

Evidently,this code cannot compute what I want,simply because the data type is not suitable to hold such a huge number.So,what can I do to deal with this kind of situation and get the desired output???

posted 6 years ago

BigInteger is capable of storing integer (i.e. non-fractional numbers) of any size. You can switch to that, or throw an exception. C# does the latter unless overflowing is enabled.

If you want to throw an exception, either throw ArithmeticException or a custom subclass of it.

If you want to throw an exception, either throw ArithmeticException or a custom subclass of it.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Jim Hoglund

Ranch Hand

Posts: 525

posted 6 years ago

There are at least 4 ways of calculating fib(n) and this is the best known but also the slowest, as it is quadratic in the number of calls to fib.

Other ways are the linear algorithm Jim is referring to, a logarithmic algorithm that is based on a matrix form, and then there is the approximation formula. See Fibonacci number for more info.

Other ways are the linear algorithm Jim is referring to, a logarithmic algorithm that is based on a matrix form, and then there is the approximation formula. See Fibonacci number for more info.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Jim Hoglund

Ranch Hand

Posts: 525

Ulf Dittmer

Rancher

Posts: 42967

73

posted 6 years ago

I think using BigInteger is a bit against the spirit of those problems. You could use an array of a 1000 ints, each representing one digit, and implement addition on top of that.

Garrett Rowe

Ranch Hand

Posts: 1296

posted 6 years ago

I respectfully disagree. I think the spirit of this problem is that there is an easy to see 'naive' algorithm which may not terminate for many hours (or days maybe, I haven't done the math) and there is a less obvious algorithm that will return relatively instantaneously. The fact that a Java int is only 32 bits is a language implementation detail that is outside the scope of the problem. In some languages the algorithm and the the way the method (function? / procedure?) is called won't even change, all that you have to do is change the type ascription from Int to Integer.

Ulf Dittmer wrote:I think using BigInteger is a bit against the spirit of those problems. You could use an array of a 1000 ints, each representing one digit, and implement addition on top of that.

I respectfully disagree. I think the spirit of this problem is that there is an easy to see 'naive' algorithm which may not terminate for many hours (or days maybe, I haven't done the math) and there is a less obvious algorithm that will return relatively instantaneously. The fact that a Java int is only 32 bits is a language implementation detail that is outside the scope of the problem. In some languages the algorithm and the the way the method (function? / procedure?) is called won't even change, all that you have to do is change the type ascription from Int to Integer.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

posted 6 years ago

I really really recommend that you don't do the fib calculation recursively. Instead, just hold the last two fib values, which you can then use to calculate the next value -- by just adding, move the fib to the prevfib, and the new value into place.

This way, you can calculate the fib and check the length as you go along. For example, to calculate the fib of 4782, I can do it in a single loop of that many iterations and check the size while doing so. To do so recursively, you will need a ridiculous number of fib() calls, which is then in a loop to check the length to get to 4782.

The first algorithm can take seconds while the second can take minutes (or even hours).

Henry

This way, you can calculate the fib and check the length as you go along. For example, to calculate the fib of 4782, I can do it in a single loop of that many iterations and check the size while doing so. To do so recursively, you will need a ridiculous number of fib() calls, which is then in a loop to check the length to get to 4782.

The first algorithm can take seconds while the second can take minutes (or even hours).

Henry

Campbell Ritchie

Sheriff

Posts: 48917

58

posted 6 years ago

There are potentially other Fibonacci series which don't begin 1, 1, but we can ignore them for the purpose of this exercise.

Surely exponential? 1.618^Rob Prime wrote:There are at least 4 ways of calculating fib(n) and this is the best known but . . . it is quadratic in the number of calls to fib. . . .

*n*where

*n*is the ordinal number in the best-known Fibonacci series.

There are potentially other Fibonacci series which don't begin 1, 1, but we can ignore them for the purpose of this exercise.

Jim Hoglund

Ranch Hand

Posts: 525

posted 6 years ago

Whatever. An exploding number of calls, that's good enough for me.

Campbell Ritchie wrote:Surely exponential? 1.618^Rob Prime wrote:There are at least 4 ways of calculating fib(n) and this is the best known but . . . it is quadratic in the number of calls to fib. . . .nwherenis the ordinal number in the best-known Fibonacci series.

Whatever. An exploding number of calls, that's good enough for me.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 6 years ago

Indeed. There's a one-liner for this problem which doesn't require calculating any Fibonacci numbers.

Garrett Rowe wrote:I respectfully disagree. I think the spirit of this problem is that there is an easy to see 'naive' algorithm which may not terminate for many hours (or days maybe, I haven't done the math) and there is a less obvious algorithm that will return relatively instantaneously.

Indeed. There's a one-liner for this problem which doesn't require calculating any Fibonacci numbers.

Jim Hoglund

Ranch Hand

Posts: 525

posted 6 years ago

Boy, I would sure like to see that "one liner." Anyway, the answer is f(4787) and the

code below gets you there quite quickly. It's linear of course. I did the adds across

a pair of StringBuilder objects of 1000 characters and exit when they overflow. I forgot to mention that the result strings are reversed with the 10^0

column on the left. I didn't bother to flip them around.

Jim ... ...

code below gets you there quite quickly. It's linear of course. I did the adds across

a pair of StringBuilder objects of 1000 characters and exit when they overflow. I forgot to mention that the result strings are reversed with the 10^0

column on the left. I didn't bother to flip them around.

Jim ... ...

BEE MBA PMP SCJP-6

posted 6 years ago

What's that 48 doing there? Oh wait, that's '0'

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Sahil Kapoor

Ranch Hand

Posts: 316

posted 6 years ago

I think for such problems you need not really to find fiboneci number.

Like, i encountered one similar problem which goes like this :-

Find the number of zero's in 276 ! ie 276 factorial.

In order to answer this we need not to calculate factorial of 276 , infact there is certain mathematic logic which quickly finds answer to such problems.

I am indeed sure that this problem also belongs to such similar category. I think topics in Number theory could help to solve your problem.

Thanks

Cheers!!!

Like, i encountered one similar problem which goes like this :-

Find the number of zero's in 276 ! ie 276 factorial.

In order to answer this we need not to calculate factorial of 276 , infact there is certain mathematic logic which quickly finds answer to such problems.

I am indeed sure that this problem also belongs to such similar category. I think topics in Number theory could help to solve your problem.

Thanks

Cheers!!!

SCJP 6.0 96%

(Connecting the Dots ....)

posted 6 years ago

I actually got a different answer -- which I actually hinted at in a post a few days ago. My answer is...

x = 4782

fib (x) = 10700662663827589367649805844573968850836838966321516650132352033753145206046940406218891475824897926578046948881775

919574843364666725699595129960304612627480924821861440694330512347744427502737817530875793916661921492591867595539664228371

489431130746995034395470019854326097230672901928705264472437261177158218255484911205250132014786129659313817922355596574520

395061375514678375432291196021299340482607061753977068470682028954869026661854351245219003694806413574474709117076197669456

910700980243934396174741037369125032313655321647736970231677550515951735184605799549194109677783732296657965816465139034881

542563101842241902598460880001101862555502454939371136516570394476295847145485234259504285824253060835444354282126110089928

637950480068943303097732178348645431132057656598684562886168087186938352973506439862976406600007235629179052070511640776148

124918858309459405666883391093509444565763576661516193177537928916615813271596168774879838218204925203484738743847367719345

12787029218636250627816

Henry

Jim Hoglund wrote:Boy, I would sure like to see that "one liner." Anyway, the answer is f(4787) and the

code below gets you there quite quickly.

I actually got a different answer -- which I actually hinted at in a post a few days ago. My answer is...

x = 4782

fib (x) = 10700662663827589367649805844573968850836838966321516650132352033753145206046940406218891475824897926578046948881775

919574843364666725699595129960304612627480924821861440694330512347744427502737817530875793916661921492591867595539664228371

489431130746995034395470019854326097230672901928705264472437261177158218255484911205250132014786129659313817922355596574520

395061375514678375432291196021299340482607061753977068470682028954869026661854351245219003694806413574474709117076197669456

910700980243934396174741037369125032313655321647736970231677550515951735184605799549194109677783732296657965816465139034881

542563101842241902598460880001101862555502454939371136516570394476295847145485234259504285824253060835444354282126110089928

637950480068943303097732178348645431132057656598684562886168087186938352973506439862976406600007235629179052070511640776148

124918858309459405666883391093509444565763576661516193177537928916615813271596168774879838218204925203484738743847367719345

12787029218636250627816

Henry

Mike Simmons

Ranch Hand

Posts: 3076

14

Jim Hoglund

Ranch Hand

Posts: 525

posted 6 years ago

Okay, since I didn't really wring out my code, I will gladly concede victory to Henry.

But Henry, let's see your algorithm. That's more interesting anyway. If anyone cares,

I can explain how I developed mine, and clean it up a bit. This is a great exercise.

Jim ... ...

But Henry, let's see your algorithm. That's more interesting anyway. If anyone cares,

I can explain how I developed mine, and clean it up a bit. This is a great exercise.

Jim ... ...

BEE MBA PMP SCJP-6

posted 6 years ago

Sure... but I cheated. I used the BigInteger, as I just wanted to get to the result.

Henry

Jim Hoglund wrote:

But Henry, let's see your algorithm. That's more interesting anyway.

Sure... but I cheated. I used the BigInteger, as I just wanted to get to the result.

Henry

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 6 years ago

Hmmm... looks like the same algorithm I used to check it, with a few cosmetic differences - I just used one main method, and compared against a BigInteger of 10^999 rather than using toString().length(). But I'm curious about the synchronization everywhere, since nothing in the program seems to use threading. Is that just part of your default style now when writing a class? I think it would be hard to use this class in a thread-safe manner without additional synchronization anyway, since there would be no guarantee that getFib() and getFibIndex() would have any particular relationship to each other if another thread could call incFibIndex() in between calls. Am I missing something?

posted 6 years ago

That's just habit. Sometimes I don't even know that I am doing it -- such as in this case. But, at least, when classes do become used in a threaded manner, I also have the habit of reviewing and refactoring the stuff too.

Henry

Mike Simmons wrote:But I'm curious about the synchronization everywhere, since nothing in the program seems to use threading. Is that just part of your default style now when writing a class? I think it would be hard to use this class in a thread-safe manner without additional synchronization anyway, since there would be no guarantee that getFib() and getFibIndex() would have any particular relationship to each other if another thread could call incFibIndex() in between calls. Am I missing something?

That's just habit. Sometimes I don't even know that I am doing it -- such as in this case. But, at least, when classes do become used in a threaded manner, I also have the habit of reviewing and refactoring the stuff too.

Henry

Ashish Schottky

Ranch Hand

Posts: 93

posted 5 years ago

After reading this problem, it appears to be more difficult than it really is.

I found the answer by working it out in paper and pencil and yes ofcourse with calculator.

Here is what I did.

Consider the golden ratio as (1+sqrt(5))/2=phi

Comparin the number of digits to power of 10, we can see in general will have x digits.

So any number which has 1000 digits will be greater than 10**999.

nth fibonacci number is given by

phi**n/sqrt(5) . SO according to our conditions:

phi**n/sqrt(5) > 10**999

solving this inequality gives us n=4782.

And here is the program:

I found the answer by working it out in paper and pencil and yes ofcourse with calculator.

Here is what I did.

Consider the golden ratio as (1+sqrt(5))/2=phi

Comparin the number of digits to power of 10, we can see in general will have x digits.

So any number which has 1000 digits will be greater than 10**999.

nth fibonacci number is given by

phi**n/sqrt(5) . SO according to our conditions:

phi**n/sqrt(5) > 10**999

solving this inequality gives us n=4782.

And here is the program:

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Well, that does give the right answer to the stated problem. But in my opinion, that's just luck. The problem is that your equation

is only approximately correct. It's a nice approximation, but you can't trust it to be exact. It's tempting to think it's "good enough" for large enough values of n, but it isn't really. Even when we're solving for n and rounding down, which can eliminate much of the error in this formula, but not all. Your prorgram based on this formula happens to give the correct solution for digits = 1000, and digits = 1001 for that matter - but it gives incorrect results (off by one) for digits = 999, or digits = 1002. And many more. Here's a demonstration:

nth fibonacci number is given by

phi**n/sqrt(5) .

is only approximately correct. It's a nice approximation, but you can't trust it to be exact. It's tempting to think it's "good enough" for large enough values of n, but it isn't really. Even when we're solving for n and rounding down, which can eliminate much of the error in this formula, but not all. Your prorgram based on this formula happens to give the correct solution for digits = 1000, and digits = 1001 for that matter - but it gives incorrect results (off by one) for digits = 999, or digits = 1002. And many more. Here's a demonstration:

Campbell Ritchie

Sheriff

Posts: 48917

58

posted 5 years ago

Nice solution, Mike, which when I tried it gave two wrong three right two wrong three right etc. I presume that is simply coincidence.

I thought, has that anything to do with the imprecision of floating-point arithmetic? So I tried it with Speedcrunch, which works to 50 digits, and got these results:

990: 4734

991 4739

992 4744

993 4748

994 4753

995 4758

996 4763

997 4768

998 4772

999 4777

1000 4782

1001 4787

1002 4791

1003 4796

1004 4801

1005 4806

1006 4811

1007 4815

1008 4820

1009 4825

So it would not appear that arithmetical imprecision is the culprit. If you try the formula with rounding up in all instances, it might work better. Try changing line 33 to

I thought, has that anything to do with the imprecision of floating-point arithmetic? So I tried it with Speedcrunch, which works to 50 digits, and got these results:

I got the results(999 + log(5) / 2) / log((sqrt(5) + 1) / 2) = 4781.859270753068860133

990: 4734

991 4739

992 4744

993 4748

994 4753

995 4758

996 4763

997 4768

998 4772

999 4777

1000 4782

1001 4787

1002 4791

1003 4796

1004 4801

1005 4806

1006 4811

1007 4815

1008 4820

1009 4825

So it would not appear that arithmetical imprecision is the culprit. If you try the formula with rounding up in all instances, it might work better. Try changing line 33 to

`int n = (int) ((power + Math.log10(divider)) / Math.log10(phi)) + 1;`
Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Good call. This appears to give correct solutions for all digits > 1. (At least to the limits of the datatypes, which is more than enough for this application.) Apparently I was mistaken about how good an approximation that formula is.

Campbell Ritchie wrote:If you try the formula with rounding up in all instances, it might work better. Try changing line 33 to

int n = (int) ((power + Math.log10(divider)) / Math.log10(phi)) + 1;

Good call. This appears to give correct solutions for all digits > 1. (At least to the limits of the datatypes, which is more than enough for this application.) Apparently I was mistaken about how good an approximation that formula is.

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Um, I believe Jim H was referring to this previous comment:

This could well be a reference to the phi-based solution that Ashish put forward, with Campbell's corrected rounding. Though I think it does still require some justification in terms of accuracy, since the formula

Paul Clapham wrote:There's a one-liner for this problem which doesn't require calculating any Fibonacci numbers.

This could well be a reference to the phi-based solution that Ashish put forward, with Campbell's corrected rounding. Though I think it does still require some justification in terms of accuracy, since the formula

*is*still an approximation. How do we know it's really "good enough", without actually checking the Fibonacci numbers? (Not that such justification isn't possible - I'd just like to know what exactly it is.) Or perhaps Paul was referring to something else entirely.
Shamsudeen Akanbi

Ranch Hand

Posts: 85

1

posted 3 years ago

And my answer to that is this (writted a while ago by me own fair hand):

Newlines are for namby-pambies

Indentation too

Spaces for the faint of heart

So which of those are you?

Real coders know the score

that nothing could be finer

than to compress all their thought

into a one-liner.

Winston

Luigi Plinge wrote:This is it as a 1-liner, if you have very long lines, and don't care for readability.

And my answer to that is this (writted a while ago by me own fair hand):

Newlines are for namby-pambies

Indentation too

Spaces for the faint of heart

So which of those are you?

Real coders know the score

that nothing could be finer

than to compress all their thought

into a one-liner.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Ivan Jozsef Balazs

Rancher

Posts: 979

5

posted 3 years ago

Let f denote (1+sqrt(5))/2 and g denote (1-sqrt(5))/2.

We observe f**2 = (1+5+2.sqrt(5))/4 = (3+sqrt(5))/2 = 1 + f and similarly

g**2 = (1+5-2.sqrt(5))/4 = (3 - sqrt(5))/2 = g + 1

So f and g are solutions of the equation h**2 = h + 1.

Now if h**2 = h + 1 then multiplied with h**n,

h**(n+1) = h ** ( n+1) + h**n

that is, the series h**n satisfies the same recursion as the Fibonacci series.

So any liner combination satisfies the same recursion, given its being linear.

Let us now consider this linear combination

G(n) = (f**n - g ** n) / sqrt(5)

For n=1, G(1) = (f-g)/sqrt(5) = 1

For n=2, G(2) = (f**2 - g**2 )/sqrt(5) but f and g both satisfy h**2=h+1, so

G(2) = (f+1 - (g+1)) / sqrt(5) = (f-g)/sqrt(5) = 1

That is, the above G series satisfies the recursion equation of the Fibonacci series, and they even coincide on n=1 and n=2.

So they are equal.

So G(n) yields a closed formula for F(n), with the main term (f**n)/sqrt(5) giving a much stronger approximation than asymptotic, because

the difference is g**n / sqrt(5), with g being between -1/2 and -1, so its powers alternate in the sign and rapidly tend toward zero.

Mike Simmons wrote:

is only approximately correct.

Let f denote (1+sqrt(5))/2 and g denote (1-sqrt(5))/2.

We observe f**2 = (1+5+2.sqrt(5))/4 = (3+sqrt(5))/2 = 1 + f and similarly

g**2 = (1+5-2.sqrt(5))/4 = (3 - sqrt(5))/2 = g + 1

So f and g are solutions of the equation h**2 = h + 1.

Now if h**2 = h + 1 then multiplied with h**n,

h**(n+1) = h ** ( n+1) + h**n

that is, the series h**n satisfies the same recursion as the Fibonacci series.

So any liner combination satisfies the same recursion, given its being linear.

Let us now consider this linear combination

G(n) = (f**n - g ** n) / sqrt(5)

For n=1, G(1) = (f-g)/sqrt(5) = 1

For n=2, G(2) = (f**2 - g**2 )/sqrt(5) but f and g both satisfy h**2=h+1, so

G(2) = (f+1 - (g+1)) / sqrt(5) = (f-g)/sqrt(5) = 1

That is, the above G series satisfies the recursion equation of the Fibonacci series, and they even coincide on n=1 and n=2.

So they are equal.

So G(n) yields a closed formula for F(n), with the main term (f**n)/sqrt(5) giving a much stronger approximation than asymptotic, because

the difference is g**n / sqrt(5), with g being between -1/2 and -1, so its powers alternate in the sign and rapidly tend toward zero.