Java solution to Project Euler Problem 36

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.

Leave a Reply

Your email address will not be published. Required fields are marked *