A073121 a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,2).
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
Offset: 1
Keywords
Examples
a(1)=1, a(2) = 2*(a(1)+a(1)) = 4, a(3) = 2*(a(2)+a(1)) = 10.
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
- 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
Crossrefs
Programs
-
Haskell
a073121 n = a053644 n * (fromIntegral n + 2 * a053645 n) -- Reinhard Zumkeller, Mar 23 2012
-
Maple
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 -
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 *) -
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 */
Formula
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
Extensions
Edited by N. J. A. Sloane, Feb 16 2016
Comments