当前位置:首页 » Project Euler » 详细页

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.

xAG(x)
(√5−1)/41
2/52
(√22−2)/63
(√137−5)/144
1/25

Solution

和137题很相似,根据$s(x)$、$xs(x)$、$x^2s(x)$可以将无穷求和式改写为: $$s(x)=\frac{x+3x^2}{1-x-x^2}$$ 令$s(x)=k$,则: $$x=\frac{-(1+k)\pm \sqrt{5k^2+14k+1}}{2(2+k)}$$ 则$5k^2+14k+1$是完全平方数时$s(x)$是有理数。 直接暴力求解,时间复杂度太高。 利用[整数变量方程求解器](https://www.alpertron.com.ar/QUAD.HTM)可以得到一些不同的起始值。 然后对于$b^2=5k^2+14k+1$可以由递推给出: $$k_{n+1}=-9k_n-4b_n-14$$ $$b_{n+1}=-20k_n-9b_n-28$$

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))
    				ans.add(k);
    		}
    	}
    	java.util.Collections.sort(ans);
    	long sum=0;
    	for(int i=0;i<30;i++)
    		sum+=ans.get(i);
    	return ""+sum;
    }

}
5673835352990
1ms