login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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, 43, 9, 1, 1, 512, 2432, 2966, 2218, 1246, 555, 196, 53, 10, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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

LINKS

Table of n, a(n) for n=1..66.

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.

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

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)

...

PROG

(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: A218664 A247286 A055587 * A099239 A167630 A322264

Adjacent sequences:  A137740 A137741 A137742 * A137744 A137745 A137746

KEYWORD

nonn,tabl

AUTHOR

M. F. Hasler, Feb 10 2008

EXTENSIONS

More terms from Alois P. Heinz, Aug 31 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 24 00:02 EDT 2019. Contains 322404 sequences. (Running on oeis4.)