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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A073121 a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,2). 10
1, 4, 10, 16, 28, 40, 52, 64, 88, 112, 136, 160, 184, 208, 232, 256, 304, 352, 400, 448, 496, 544, 592, 640, 688, 736, 784, 832, 880, 928, 976, 1024, 1120, 1216, 1312, 1408, 1504, 1600, 1696, 1792, 1888, 1984, 2080, 2176, 2272, 2368, 2464, 2560, 2656, 2752 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

A recurrence occurring in the analysis of a regular expression algorithm.

REFERENCES

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.

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

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

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

K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.

E. D. Demaine, M. L. Demaine, Y. N. Minsky, J. S. B. Mitchell, R. L. Rivest, M. Patrascu, Picture-Hanging Puzzles, arXiv:1203.3602 [cs.DS], 2012-2014.

K. Ellul, J. Shallit and M.-w. Wang, Regular expressions: new results and open problems, Journal of Automata, Languages and Combinatorics, preprint.

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

R. Stephan, Table of generating functions

FORMULA

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, 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*x/(1-x)^2 * ((2*x+1)/3 + sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003

G.f. A(x) = 2 * (1/x + 2 + x) * A(x^2) - x. - Michael Somos, Jul 04 2017

EXAMPLE

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

MAPLE

a:= proc(n) option remember; `if`(n=1, 1,

      2*(a(iquo(n, 2))+a(n-iquo(n, 2))))

    end:

seq(a(n), n=1..70);  # Alois P. Heinz, Feb 01 2015

MATHEMATICA

a[n_] := a[n] = If[n == 1, 1, 2*(a[Quotient[n, 2]] + a[n - Quotient[n, 2]])]; Table[a[n], {n, 1, 70}] (* Jean-Fran├žois Alcover, Feb 24 2016, after Alois P. Heinz *)

a[ n_] := If[ n < 1, 0, Module[{m = 1, A = 1}, While[m < n, m *= 2; A = (Normal[A] /. x -> x^2) 2 (1 + x)^2 - 1 + O[x]^m]; Coefficient[A, x, n - 1]]]; (* Michael Somos, Jul 04 2017 *)

PROG

(Haskell)

a073121 n = a053644 n * (fromIntegral n + 2 * a053645 n)

-- Reinhard Zumkeller, Mar 23 2012

(PARI) {a(n) = n--; if( n<0, 0, my(m=1, A = 1 + O(x)); while(m<=n, m*=2; A = subst(A, x, x^2) * 2 * (1 + x)^2 - 1); polcoeff(A, n))}; /* Michael Somos, Jul 04 2017 */

CROSSREFS

Cf. A053644, A053645, A254575.

Sequences of form a(n)=r*a(ceil(n/2))+s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

Sequence in context: A036063 A112984 A191115 * A167346 A027430 A298031

Adjacent sequences:  A073118 A073119 A073120 * A073122 A073123 A073124

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Aug 25 2002

EXTENSIONS

Edited by N. J. A. Sloane, Feb 16 2016

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 11:57 EDT 2018. Contains 316359 sequences. (Running on oeis4.)