1,2

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

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.

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

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

Jean-Paul Allouche and Jeffrey Shallit, The Ring of k-regular Sequences, II

F. Barbero, G. Gutin, M. Jones, and B. Sheng, Parameterized and approximation algorithms for the load coloring problem, Algorithmica 79, No. 1, 211-229 (2017). Prop 3.

Keh-Ning Chang and Shi-Chun Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.

Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Patrascu, Picture-Hanging Puzzles, arXiv:1203.3602 [cs.DS], 2012-2014.

Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei Wang, Regular expressions: new results and open problems, Journal of Automata, Languages and Combinatorics, preprint.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 37.

Jean-Marc Luck, Revisiting log-periodic oscillations, arXiv:2403.00432 [cond-mat.stat-mech], 2024. See p. 14.

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

Ralf Stephan, Table of generating functions

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.

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

For any n, n^2 <= a(n) <= 9/8 * n^2. - Arnoud van der Leer, Sep 01 2019

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

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

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

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

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

end:

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

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

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

Cf. A053644, A053645, A254575.

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.

Sequence in context: A112984 A343907 A191115 * A167346 A307274 A378708

Adjacent sequences: A073118 A073119 A073120 * A073122 A073123 A073124

Jeffrey Shallit, Aug 25 2002

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

approved