It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φφ = (1 + 5**0.5) / 2
return floor(n * log10(Φφ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
if k < 2:
return 1
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
if k < 2:
return 1
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
φ = (1 + 5**0.5) / 2
return floor(n * log10(φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
if k < 2:
return 1
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
if k < 2:
return 1
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
if k < 2:
return 1
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It shouldn't be too hardIt's possible to findcalculate the inverse of this function. This way, you couldcan find the first Fibonacci with k digits directly, without any loop.:
def euler25(k):
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It shouldn't be too hard to find the inverse of this function. This way, you could find the first Fibonacci with k digits directly, without any loop.
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
Φ = (1 + 5**0.5) / 2
return floor(n * log10(Φ) - log10(5) / 2) + 1
It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:
def euler25(k):
φ = (1 + 5**0.5) / 2
return ceil((k + log10(5) / 2 - 1) / log10(φ))
It seems to return the correct answer for any k in less than 1 μs :
>>> euler25(1000)
4782
>>> euler25(10_000)
47847
>>> euler25(100_000)
478495
>>> euler25(100_000_000_000_000_000)
478497196678166592
The digits are the same as in:
>>> 1 / log10(φ)
4.784971966781666