forked from nayuki/Project-Euler-solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathp025.java
More file actions
47 lines (37 loc) · 1.4 KB
/
p025.java
File metadata and controls
47 lines (37 loc) · 1.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
* Solution to Project Euler problem 25
* Copyright (c) Project Nayuki. All rights reserved.
*
* https://www.nayuki.io/page/project-euler-solutions
* https://github.com/nayuki/Project-Euler-solutions
*/
import java.math.BigInteger;
public final class p025 implements EulerSolution {
public static void main(String[] args) {
System.out.println(new p025().run());
}
/*
* Because the target number is relatively small, we simply compute each Fibonacci number starting
* from the beginning until we encounter one with exactly 1000 digits. The Fibonacci sequence grows
* exponentially with a base of about 1.618, so the numbers in base 10 will lengthen by one digit
* after every log10(1.618) ~= 4.78 steps on average. This means the answer is at index around 4780.
*/
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;
}
}
}