Here is another Project Euler problem – this time a little-bit more challenging:
“The Fibonacci sequence is defined by the recurrence relation:
It turns out that F541 , which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749 , which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.
Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.”
Does this sound XSLT-ish? No, not at all.
has the following properties:
- Execution time: 34.6 sec.
- LOC: 54 (~ 40 express the solution)
- Time to write the code: ~15 min.
- Uses library: FXSL (the f:fibo() function for generating Fibonacci numbers)
The index of the first Fibonacci number with the required properties is more than 300 thousand and the number itself has more than 68 thousand digits.
Not satisfied with the speed of this solution? Want even faster? Then here’s something you may consider:
We have added a a couple of lines of code and look what we have now:
- Execution time: 0.555 sec.
- LOC: 55 (~ 43 express the solution)
- Time to write the code: ~10 min.
As witnessed in the Project Euler thread for this problem (one must have provided the correct answer in order to access this thread), many solutions took longer: from 3.3 seconds, to 30-40 minutes, to couple of hours.
One Python programmer even waited for the end of his brute-force solution … 12 days