## Problem:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn[−]1 + Fn[−]2, where F1 = 1 and F2 = 1.

It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

906609

## Code:The solution may include methods that will be found here: Library.java .

public interface EulerSolution{public String run();}
/*  * Solution to Project Euler problem 4 * By Nayuki Minase *  * http://nayuki.eigenstate.org/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */public final class p004 implements EulerSolution {		public static void main(String[] args) {		System.out.println(new p004().run());	}			public String run() {		int maxPalin = -1;		for (int i = 100; i < 1000; i++) {			for (int j = 100; j < 1000; j++) {				int prod = i * j;				if (Library.isPalindrome(prod) && prod > maxPalin)					maxPalin = prod;			}		}		return Integer.toString(maxPalin);	}	}