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?
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
BEE MBA PMP SCJP6
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
BEE MBA PMP SCJP6
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.
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them.  Laurence J. Peter
Surely exponential? 1.618^n where n is the ordinal number in the bestknown Fibonacci series.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. . . .
BEE MBA PMP SCJP6
Campbell Ritchie wrote:
Surely exponential? 1.618^n where n is the ordinal number in the bestknown Fibonacci series.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. . . .
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
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.
BEE MBA PMP SCJP6
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
SCJP 6.0 96%
(Connecting the Dots ....)
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.
BEE MBA PMP SCJP6
Jim Hoglund wrote:
But Henry, let's see your algorithm. That's more interesting anyway.
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 threadsafe 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?
nth fibonacci number is given by
phi**n/sqrt(5) .
I got the results(999 + log(5) / 2) / log((sqrt(5) + 1) / 2) = 4781.859270753068860133
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;
Jim Hoglund wrote:Boy, I would sure like to see that "one liner."
Paul Clapham wrote:There's a oneliner for this problem which doesn't require calculating any Fibonacci numbers.
Luigi Plinge wrote:This is it as a 1liner, if you have very long lines, and don't care for readability.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Mike Simmons wrote:
is only approximately correct.
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn KlassenKoop
https://coderanch.com/wiki/718759/books/BuildingWorldBackyardPaulWheaton
