|
|
A060973
|
|
a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n), with a(1)=0 and a(2)=1.
|
|
5
|
|
|
0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
LINKS
|
H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13:4 (2017), #47. doi:10.1145/3127585
|
|
FORMULA
|
If n = 2*(2^m) + k with 0 <= k <= 2^m, then a(n) = 2^m; if n = 3*(2^m) + k with 0 <= k <= 2^m, then a(n) = 2^m + k.
G.f.: -x/(1 - x) + x/(1 - x)^2 * ( 1 + Sum_{k >= 0} t^2*(t - 1) ), t = x^(2^k). - Ralf Stephan, Sep 12 2003
a(n - a(n)) = a(n - a(n - a(n - a(n)))).
If b(n) = a(a(n)) then b(n - b(n)) = b(n - b(n - b(n - b(n)))) for n >= 2. (End)
Sum_{n>=2} 1/a(n)^2 = Pi^2/6 + 2. - Amiram Eldar, Sep 08 2022
|
|
EXAMPLE
|
a(6) = 2*a(3) = 2*1 = 2.
a(7) = a(3) + a(4) = 1 + 2 = 3.
|
|
MAPLE
|
option remember;
if n <= 2 then
return n-1;
fi;
if n mod 2 = 0 then
2*procname(n/2)
else
procname((n-1)/2)+procname((n+1)/2);
fi;
|
|
MATHEMATICA
|
nn = 77; Array[Set[a[#], # - 1] &, 2]; Do[Set[a[i], If[EvenQ[i], 2 a[i/2], a[# + 1] + a[#] &[(i - 1)/2]]], {i, 3, nn}]; Array[a, nn] (* Michael De Vlieger, Mar 22 2022 *)
|
|
PROG
|
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
(PARI) a(n) = my(i=logint(n, 2)-1); if(bittest(n, i), n - 2<<i, 1<<i); \\ Kevin Ryde, Aug 19 2022
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|