1234567891011121314151617181920212223242526272829303132 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 18 March 2022
- # https://github.com/trizen
- # https://projecteuler.net/problem=104
- # Runtime: 5.904s
- # Solution using Binet's formula to compute the first 9 digits of fib(n),
- # and also modular exponentiation to compute the last 9 digits of fib(n).
- func f(n) {
- n*log((1+sqrt(5))/2) - log(5)/2
- }
- func nth_fib_first_k_digits(n,k,b=10) {
- var v = f(n)
- var l = b.log
- int(b**(k-1) * exp(v - l*floor(v/l)))
- }
- var t = @(1..9).join
- for (var k = 2749; true; ++k) {
- if ((fibmod(k, 1e9).to_s.sort == t) && (nth_fib_first_k_digits(k, 9).to_s.sort == t)) {
- say k
- break
- }
- }
|