# Java solution to Project Euler Problem 36

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.

```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");
}
}```