hacker.org

That was fun.

While solving "Big Fib" with bc driven by a perl-script and using the dijkstra-simplification, I realized that getting the solution for this challenge would take more time and cycles than I want to spent on it.

So, I changed to C with GMP and was really thrilled by the speed of GMP in computing fib members (damn, should have known that before ) . But GMP lacks ln() so I spent some extra time to bring in MPFR.

.done! (phewww)

You know, a little bit of pretty basic applied math knowledge makes this (and BiggestFib as well) solvable without any fancy libraries in 2 or 3 lines of code and a very small fraction of a second.

with a little bit knowledge of "sectio aurea" you don't need any coding at all, just the Windows calculator and you'll find the solution manually in only some seconds ...

Phew, finally solved that one... after I got the BigFib I really was shocked by the BiggerFib challenge, a short attempt to calculate this number (w/o thinking about the ln-part too much) led me to the point that this is simply senseless...

It was not until half an hour ago that I read about ways to calculate big f(n) and to recap the laws of logarithmics.

Now on to the biggest fib

EDIT: OK, biggest is not really harder than bigger...

rmplpmpl wrote:EDIT: OK, biggest is not really harder than bigger...

Except in the sense that "bigger" is fully calculable in a vaguely reasonable time period (a few days, for me) - it wasn't until "biggest" that I took the more efficient approach.

sometimes it helps to "think" before starting to hack in some code !
compuation is done in a few milliseconds if done right.

Well the ln part makes it easier than expected

XD I did it in one line

print(150000000*log(1.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748475408807538689175212663386222353693179318006076672635443)-.5*log(5))

Which is a way of writing

x*log(phi)-.5*log(5)

Wolfram|Alpha did it.

Has anyone solved it with Python? Could you please post your solution? Or any C++ approach? (I would like to learn C++ and I appreciate reading examples)

moose wrote:Wolfram|Alpha did it.

Has anyone solved it with Python? Could you please post your solution? Or any C++ approach? (I would like to learn C++ and I appreciate reading examples)

I think most of us probably used the formula for the nth Fibonacci number, ending up with:
-(Log[5]/2) + Log[-(2/(1 + Sqrt[5]))^n + (1/2 (1 + Sqrt[5]))^n]
(WolframAlpha will show this in a nice format).
Then noting that the -(2/(1+Sqrt[5]))^n term will become very close to 0 as n increases, so we end up with:
-(Log[5]/2) + n Log[(1/2 (1 + Sqrt[5]))]
which is very easy to find.

If I remember well, I had opened excell when I came to these 2 challenges. So I have multiplyed and subtracted the logarithms there...