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