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

%I

%S 1,4,10,16,28,40,52,64,88,112,136,160,184,208,232,256,304,352,400,448,

%T 496,544,592,640,688,736,784,832,880,928,976,1024,1120,1216,1312,1408,

%U 1504,1600,1696,1792,1888,1984,2080,2176,2272,2368,2464,2560,2656,2752

%N a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

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

%D 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.

%H Reinhard Zumkeller, <a href="/A073121/b073121.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>

%H K.-N. Chang and S.-C. Tsai, <a href="http://dx.doi.org/10.1016/S0020-0190(00)00076-4">Exact solution of a minimal recurrence</a>, Inform. Process. Lett. 75 (2000), 61-64.

%H E. D. Demaine, M. L. Demaine, Y. N. Minsky, J. S. B. Mitchell, R. L. Rivest, M. Patrascu, <a href="http://arxiv.org/abs/1203.3602">Picture-Hanging Puzzles</a>, arXiv:1203.3602 [cs.DS], 2012-2014.

%H K. Ellul, J. Shallit and M.-w. Wang, <a href="https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf">Regular expressions: new results and open problems</a>, Journal of Automata, Languages and Combinatorics, preprint.

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%F 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

%F 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

%F 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

%F G.f. A(x) = 2 * (1/x + 2 + x) * A(x^2) - x. - _Michael Somos_, Jul 04 2017

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

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

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

%p end:

%p seq(a(n), n=1..70); # _Alois P. Heinz_, Feb 01 2015

%t 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_ *)

%t 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 *)

%o (Haskell)

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

%o -- _Reinhard Zumkeller_, Mar 23 2012

%o (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 */

%Y Cf. A053644, A053645, A254575.

%Y 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.

%K nonn

%O 1,2

%A _Jeffrey Shallit_, Aug 25 2002

%E Edited by _N. J. A. Sloane_, Feb 16 2016

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 February 17 10:59 EST 2019. Contains 320219 sequences. (Running on oeis4.)