A137743 - OEIS

%I #27 Nov 10 2018 02:49:47

%S 1,1,1,1,2,1,1,4,3,1,1,8,8,4,1,1,16,21,13,5,1,1,32,54,40,19,6,1,1,64,

%T 138,119,66,26,7,1,1,128,355,348,218,100,34,8,1,1,256,924,1014,700,

%U 360,143,43,9,1,1,512,2432,2966,2218,1246,555,196,53,10,1

%N Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle.

%C The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.

%H <a href="/index/Do#repeat">Index entries for doubling substrings</a>

%F T(m,n)=0 for n < m, T(m,m)=T(1,n)=1, T(m,m+1)=m, T(m,m+2)=C(m+2,2)-2 = A034856(m); T(2,2+n)=2^n.

%F For m > 3, T(m,m+2) = T(m-1,m+1) + T(m,m+1) + T(m+1,m+1). - _Thomas Anton_, Nov 05 2018

%e The full matrix is:

%e [ 1, 1, 1, 1, 1, 1, 1,_ 1,_ 1,__ 1,__ 1,...] (= A000012)

%e [[], 1, 2, 4, 8,16,32, 64,128, 256, 512,...] (= A000079)

%e [[],[], 1, 3, 8,21,54,138,355, 924,2432,...] (= A135473)

%e [[],[],[], 1, 4,13,40,119,348,1014,2966,...] (= A137744)

%e [[],[],[],[], 1, 5,19, 66,218, 700,2218,...] (= A137745)

%e [[],[],[],[],[], 1, 6, 26,100, 360,1246,...] (= A137746)

%e [[],[],[],[],[],[], 1,_ 7, 34, 143, 555,...] (= A137747)

%e ...

%o (PARI) A135473(Nmax,d=3 /* # digits in the initial string = row of the triangular matrix */)={ local( t,tt,ee,lsb, L=vector(Nmax,i,[]) /*store separately words of given length*/, w=log(d-.5)\log(2)+1/* bits required to code d distinct digits*/); L[d]=Set(sum(i=1,d-1,i<<(w*i))); for( i=d,Nmax-1, for( j=1, #t=eval(L[i]), forstep( ee=w,w*i,w, /*upper cutting point*/ forstep( len=w, min(ee,w*(Nmax-i)),w, /* length of substring */ lsb = bitand( tt=t[j], 1<<ee - 1); /* substring + tail */ forstep( ii=i+len/w,Nmax,len/w, setsearch( L[ii], tt = bitand( tt<<len, -1<<ee)+lsb) & next; L[ii] = setunion( L[ii], tt )); ) ) ) ) ); vector(Nmax,i,#L[i])}

%o for(d=2,7,print(A137743(10,d)))

%Y Cf. A135473, A137740-A137742, A137744-A137748.

%K nonn,tabl

%O 1,5

%A _M. F. Hasler_, Feb 10 2008

%E More terms from _Alois P. Heinz_, Aug 31 2011