### Modified Fibonacci golden nuggets题号：140 难度： 55 中英对照

Consider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + ..., where Gk is the kth term of the second order recurrence relation Gk = Gk−1 + Gk−2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, ... .

For this problem we shall be concerned with values of x for which AG(x) is a positive integer.

The corresponding values of x for the first five natural numbers are shown below.

 x AG(x) (√5−1)/4 1 2/5 2 (√22−2)/6 3 (√137−5)/14 4 1/2 5

### Code

public final class p140 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run(){
long start[][]=new long[][]{
{0,-1},
{0,1},
{-3,-2},
{-3,2},
{-4,5},
{-4,-5},
{2,-7},
{2,7}
};
java.util.ArrayList<Long> ans=new java.util.ArrayList<Long>();
for(int i=0;i<start.length;i++){
long k=start[i][0];
long s=start[i][1];
for(int j=0;j<30;j++){
long knew=-9*k-4*s-14;
long snew=-20*k-9*s-28;
k=knew;
s=snew;
if(k>0 && !ans.contains(k))
}
5673835352990