|
%I #7 Jun 14 2017 00:43:35
%S 2,3,2,5,5,2,7,7,7,2,8,9,9,9,2,9,11,11,11,11,2,13,12,13,13,13,13,2,14,
%T 13,15,15,15,15,15,2,18,15,16,17,17,17,17,17,2,19,19,17,19,19,19,19,
%U 19,19,2,24,23,19,20,21,21,21,21,21,21,2,25,27,21,21,23,23,23,23,23,23,23
%N Ulam type (1-additive) sequences u[1]=2, u[2]=2n+1, u[k+1] is least unique sum u[i]+u[j]>u[k], 1<=i<j<=k; formatted as a table and read by antidiagonals.
%C Any of the sequences u=U(2,2n+1) has u[1]=2 and u[n+4]=4n+4; in between these there are the odd numbers 2n+1,...,4n-3. For n>1 there are no other even terms and the sequence of first differences becomes periodic for k>=t (transient phase), such that u[k] = u[k-floor((k-t)/p)*p] + floor((k-t)/p)*d, where p is the period (cf. A100729) and d the fundamental difference (cf. A100730). See the cross-references, especially A002858, for more information.
%H Project Euler, <a href="http://projecteuler.net/index.php?section=problems&id=167">Problem 167: Investigating Ulam sequences</a>
%e The sequence contains the terms of the table T[n,k] = U(2,2n+1)[k], read by antidiagonals: a[1]=T[1,1]=2, a[2]=T[1,2]=3, a[3]=T[2,1]=2, a[4]=T[1,3]=5,...
%e n=1: U(2,3)= 2, 3, 5, 7, 8, 9,13,14...
%e n=2: U(2,5)= 2, 5, 7, 9,11,12,...
%e n=3: U(2,7)= 2, 7, 9,11,13,...
%e n=4: U(2,9)= 2, 9,11,...
%o (PARI) ulam(a,b,Nmax=30,i)=a=[a,b]; b=[a[1]+b]; for( k=3,Nmax, i=1; while(( i<#b && b[i]==b[i+1] && i+=2 ) || ( i>1 && b[i]==b[i-1] && i++),); a=concat(a,b[i]); b=vecsort(concat(vecextract(b,Str("^..",i)),vector(k-1,j,a[k]+a[j]))); i=0; for(j=1,#b-2, if( b[j]==b[j+2], i+=1<<j)); if(i,b=vecextract(b,2^#b-1-i))); a
%o /* now this sequence */
%o A135737(Nmax=100)=local(T=vector(sqrtint(Nmax*2)+1,n, ulam(2,2*n+1, sqrtint(Nmax*2)+2-n)),i,j); vector(Nmax,k,if(j>1,T[i++ ][j-- ],j=i+1;T[i=1][j]))
%Y Cf. A001857 = U(2, 3), A007300 = U(2, 5), A003668 = U(2, 7); A100729-A100730 (period); A002858 = U(1, 2), A002859 = U(1, 3), A003666 = U(1, 4), A003667 = U(1, 5).
%K nice,nonn,tabl
%O 1,1
%A _M. F. Hasler_, Nov 26 2007
|
