|
Search: id:A137743
|
|
|
| A137743 |
|
Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle. |
|
+0
12
|
|
| 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, 138, 119, 66, 26, 7, 1, 1, 128, 355, 348, 218, 100, 34, 8, 1, 1, 256, 924, 1014, 700, 360, 143
(list; table; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.
|
|
LINKS
|
Index entries for doubling substrings
|
|
FORMULA
|
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.
|
|
EXAMPLE
|
The full matrix is:
[ 1, 1, 1, 1, 1, 1, 1,_ 1,_ 1,__ 1,__ 1,...] (= A000012)
[[], 1, 2, 4, 8,16,32, 64,128, 256, 512,...] (= A000079)
[[],[], 1, 3, 8,21,54,138,355, 924,2432,...] (= A135473)
[[],[],[], 1, 4,13,40,119,348,1014,2966,...] (= A137744)
[[],[],[],[], 1, 5,19, 66,218, 700,2218,...] (= A137745)
[[],[],[],[],[], 1, 6, 26,100, 360,1246,...] (= A137746)
[[],[],[],[],[],[], 1,_ 7, 34, 143, 555,...] (= A137747)
...
|
|
PROGRAM
|
(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])}
for(d=2, 7, print(A137743(10, d)))
|
|
CROSSREFS
|
Cf. A135473, A137740-A137742, A137744-A137748.
Sequence in context: A091186 A138155 A055587 this_sequence A099239 A009998 A113993
Adjacent sequences: A137740 A137741 A137742 this_sequence A137744 A137745 A137746
|
|
KEYWORD
|
more,nonn,tabl
|
|
AUTHOR
|
M. F. Hasler (MHasler(AT)univ-ag.fr), Feb 10 2008
|
|
|
Search completed in 0.002 seconds
|
