Solution to Project Euler Problem 25: 1000-digit Fibonacci number - The Fibonacci sequence is defined by the recurrence relation: Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be: F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 The 12th term, F12, is the first term to contain three digits. What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
Updated: April 11, 2021 — Training Time: 2 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 25: 1000-digit Fibonacci number.
Difficulty: Easy.
Objective: The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
Input: None.
Expected Output: 4728.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
import java.math.BigInteger;
public class SikademyEulerSolution {
private static final int DIGITS = 1000;
public String run() {
BigInteger lowerThres = BigInteger.TEN.pow(DIGITS - 1);
BigInteger upperThres = BigInteger.TEN.pow(DIGITS);
BigInteger prev = BigInteger.ONE;
BigInteger cur = BigInteger.ZERO;
for (int i = 0; ; i++) {
// At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
if (cur.compareTo(upperThres) >= 0)
throw new RuntimeException("Not found");
else if (cur.compareTo(lowerThres) >= 0)
return Integer.toString(i);
// Advance the Fibonacci sequence by one step
BigInteger temp = cur.add(prev);
prev = cur;
cur = temp;
}
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import itertools
def compute():
DIGITS = 1000
prev = 1
cur = 0
for i in itertools.count():
# At this point, prev = fibonacci(i - 1) and cur = fibonacci(i)
if len(str(cur)) > DIGITS:
raise RuntimeError("Not found")
elif len(str(cur)) == DIGITS:
return str(i)
# Advance the Fibonacci sequence by one step
prev, cur = cur, prev + cur
if __name__ == "__main__":
print(compute())