1,2

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

K. Ellul, J. Shallit and M.-w. Wang, Regular expressions: new results and open problems, in Descriptional Complexity of Formal Systems (DCFS), Proceedings of workshop, London, Ontario, Canada, 21-24 August 2002, pp. 17-34.

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

a(n) == 1 (mod 3), a(n+1)-a(n) = 3* A053644(n). If k>=1: a(2^k)=4^k, a(3*2^k)=(10/9)*4^k. More generally a(m*2^k) = a(m)*4^k. Hence for any n, n^2 <= a(n) <= C*n^2 where C is a constant 1.125 < C < 1.14 and it seems that C = lim k -> infinity a(A001045(k))/A001045(k)^2 where A001045(k) ={2^n - (-1)^n}/3 is the Jacobsthal sequence. In other words, in the range 2^k<=n<=2^(k+1) the maximum of a(n)/n^2 is reached for the only possible n in the Jacobsthal sequence. - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 26 2002

a(n) = 2*(a(floor(n/2))+a(ceil(n/2))) for n >= 2; alternatively a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c

G.f.: 3/(1-x)^2 * ((2x+1)/3 + sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 18 2003

a(1)=1, a(2) = 2(a(1)+a(1)) = 4, a(3) = 2(a(2)+a(1)) = 10

Sequence in context: A089340 A132227 A112984 this_sequence A167346 A027430 A027425

Adjacent sequences: A073118 A073119 A073120 this_sequence A073122 A073123 A073124

nonn

Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Aug 25 2002