|
%I #77 Mar 09 2024 11:03:12
%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 Jean-Paul Allouche and Jeffrey 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 Jean-Paul Allouche and Jeffrey Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H F. Barbero, G. Gutin, M. Jones, and B. Sheng, <a href="https://doi.org/10.1007/s00453-016-0259-z">Parameterized and approximation algorithms for the load coloring problem</a>, Algorithmica 79, No. 1, 211-229 (2017). Prop 3.
%H Keh-Ning Chang and Shi-Chun 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 Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Patrascu, <a href="http://arxiv.org/abs/1203.3602">Picture-Hanging Puzzles</a>, arXiv:1203.3602 [cs.DS], 2012-2014.
%H Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei 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 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 37.
%H Jean-Marc Luck, <a href="https://arxiv.org/abs/2403.00432">Revisiting log-periodic oscillations</a>, arXiv:2403.00432 [cond-mat.stat-mech], 2024. See p. 14.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F a(n) = 2*(a(floor(n/2)) + a(ceiling(n/2))) for n >= 2; alternatively, a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c.
%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 For any n, n^2 <= a(n) <= 9/8 * n^2. - _Arnoud van der Leer_, Sep 01 2019
%F a(n) = 2*(a(floor(n/2)) + a(ceiling(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*((m-> a(m)+a(n-m))(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(ceiling(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
|
