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

Investigating Ulam sequences 题号:167 难度: 75 中英对照

For two positive integers a and b, the Ulam sequence U(a,b) is defined by U(a,b)1 = a, U(a,b)2 = b and for k > 2, U(a,b)k is the smallest integer greater than U(a,b)(k-1) which can be written in exactly one way as the sum of two distinct previous members of U(a,b).

For example, the sequence U(1,2) begins with
1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
5 does not belong to it because 5 = 1 + 4 = 2 + 3 has two representations as the sum of two previous members, likewise 7 = 1 + 6 = 3 + 4.

Find ∑U(2,2n+1)k for 2 ≤ n ≤10, where k = 1011.

Solution

根据[论文](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.27.7259&rep=rep1&type=pdf)的结论,所有$U(2,v)$($v$为奇数)的乌拉姆数列仅有两个偶数项,剩下都是奇数项,且当$k$充分大时有整数$N$和$D$,满足:$U[k]=U[k-N]+D$,即分段等差,对于不同的$v$值对应的$N$和$D$在论文的表格中有。 根据只有两个偶数的性质,其中一个偶数是$2$,另一个偶数是$2v+2$,那么: 对于已知的序列中的奇数$x$,$x+2$在序列中的充要条件是$x+2-(2v+2)$不在序列中; 对于不在序列中的奇数$x$,$x+2$在序列中的充要条件是$x+2-(2v+2)$在序列中。 可以使用一个队列来保存最近的若干个在序列中的奇数即可,因为$x+2-(2v+2)$是递增的。

Code

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public final class p167 {
    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() {
    	final long k=100000000000L;
    	long ans=0;
    	for(int n=2;n<=10;n++)
    		ans+=solve(2*n+1,k);
    	return ans+"";
	}

    final static long N[]=new long[]{0,0,32,26,444,1628,5906,80,126960,380882,2097152};
    final static long D[]=new long[]{0,0,126,126,1778,6510,23622,510,507842,1523526,8388606};
    static LinkedBlockingQueue<Long> set;
    static long solve(int v,long k){
    	set=new LinkedBlockingQueue<Long>();
    	long n=N[v>>1],d=D[v>>1];
    	long even=(v<<1)+2;
    	long r=k%n+n;
    	long p=k/n-1;
    	long i=0;
    	long now=0;
    	boolean flag=true;
    	while(i<r){
    		if(i==0){
    			now=2;i++;
    		}else if(i==1){
    			now=v;i++;
    			set.add(now);
    		}else if(flag){
    			now+=2;
    			if(now<even) i++;
    			else{
    				i+=2;
    				flag=false;
    			}
    			set.add(now);
    		}else{
    			boolean galf=true;//标记now是否在序列中
    			while(true){
    				now+=2;
    				boolean con=set.contains(now-even);
    				if(galf && con)
    					galf=false;
    				else if(galf || con)
    					break;
    			}
    			set.add(now);
    			i++;
    		}
    		while(!set.isEmpty()&&set.peek()<now-even-2)
    			set.poll();
    	}
    	return now+p*d;
    }
    
    
    
}
3916160068885
2840ms