The Fibonacci sequence is defined by the recurrence relation:

`Fn = F(n-1) + F(n-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 first term in the Fibonacci sequence to contain 1000 digits?

**Running time:**

- Checking for a palindrome in Base 10 first: 500ms
- Checking for a binary palindrome first: 650ms

**Assessment:** This problem isn’t super interesting. What I did find interesting was that changing the order of the isPalindrome() comparison resulted in a significant difference in execution times. This makes sense because there are more binary palindromes than Base 10 palindromes. For no particular reason, I expected the compiler to optimize that section so the difference wouldn’t be as stark.

I commented out the slower method so you can play with it if my explanation is unclear.

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 |
public class Problem036 { private static boolean isPalindrome(String s) { String s2 = new StringBuffer(s).reverse().toString(); if (s.equals(s2)) return true; else return false; } public static void main(String[] args) { long begin = System.currentTimeMillis(); long Sum = 0; for (int i = 0; i < 1000000; i++) { if ( isPalindrome(Integer.toString(i)) && isPalindrome(Integer.toBinaryString(i)) ) Sum += i; /*if (isPalindrome(Integer.toBinaryString(i)) && isPalindrome(Integer.toString(i))) Sum += i;*/ } System.out.println(Sum); long end = System.currentTimeMillis(); System.out.println(end-begin + "ms"); } } |