### 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.

### Code

import java.util.*;

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 long solve(int v,long k){
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++;
}else if(flag){
now+=2;
if(now<even) i++;
else{
i+=2;
flag=false;
}
}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;
}
i++;
}
while(!set.isEmpty()&&set.peek()<now-even-2)
set.poll();
}
return now+p*d;
}

}
3916160068885
2840ms