login
A360724
Hajnal's recurrence: a(2n) = a(n) + 3*a(n-1); a(2n+1) = 3*a(n) + a(n-1), with initial values a(0) = 0, a(1) = 1.
1
0, 1, 1, 3, 4, 4, 6, 10, 13, 15, 16, 16, 18, 22, 28, 36, 43, 49, 54, 58, 61, 63, 64, 64, 66, 70, 76, 84, 94, 106, 120, 136, 151, 165, 178, 190, 201, 211, 220, 228, 235, 241, 246, 250, 253, 255, 256, 256, 258, 262, 268, 276, 286, 298, 312, 328, 346, 366, 388
OFFSET
0,4
COMMENTS
liminf a(n)/n^2 = 1/10; in fact a(n) >= (n^2+3n)/10 for all n, and this bound is tight.
limsup a(n)/n^2 = 1/7; in fact a(n) <= (n^2+3n+3)/7 for all n, and this bound is tight.
Although it is not immediately obvious from the definition, the sequence is increasing (but not strictly increasing).
REFERENCES
Message from Peter Hajnal to the author, June 22 2008.
LINKS
FORMULA
a(n) = 10*4^i + (n+1)(n+2) - (6n+9)*2^i, if 3*2^i <= n < 4*2^i; a(n) = (6n+9)*2^i - 14*4^i - (n+1)(n+2)/2, if 4*2^i <= n < 6*2^i.
MAPLE
a:= proc(n) option remember; `if`(n<2, n, (h->
(1+2*m)*a(h)+(3-2*m)*a(h-1))(iquo(n, 2, 'm')))
end:
seq(a(n), n=0..60); # Alois P. Heinz, Feb 18 2023
MATHEMATICA
nn = 120; Array[Set[a[#], #] &, 2, 0]; Do[Set[a[n], If[EvenQ[n], a[#] + 3 a[# - 1] &[n/2], 3 a[#] + a[# - 1] &[(n - 1)/2]]], {n, 2, nn}]; Array[a, nn + 1, 0] (* Michael De Vlieger, Feb 18 2023 *)
CROSSREFS
Sequence in context: A351371 A280448 A100692 * A089640 A086659 A265887
KEYWORD
nonn,look
AUTHOR
Jeffrey Shallit, Feb 18 2023
STATUS
approved