A060973 a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n), with a(1)=0 and a(2)=1.

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

Offset: 1

Author

Henry Bottomley, May 09 2001

Keywords

• nonn
• easy

Examples

			a(6) = 2*a(3) = 2*1 = 2.
a(7) = a(3) + a(4) = 1 + 2 = 3.
		

Links

• R. J. Mathar, Table of n, a(n) for n = 1..1000
• Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.
• Michael De Vlieger, Log-log scatterplot of a(n), n = 1..2^16.
• H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications. Preprint 2016.
• 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
• Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
• Ralf Stephan, Some divide-and-conquer sequences ....
• Ralf Stephan, Table of generating functions.

Crossrefs

Cf. A006165, A053646.

Programs

Maple

A060973 := proc(n)
    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;
end proc:  # R. J. Mathar Nov 30 2014

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

PARI

a(n) = my(i=logint(n,2)-1); if(bittest(n,i), n - 2<Kevin Ryde, Aug 19 2022

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A060973(n): return n-1 if n <= 2 else A060973(n//2) + A060973((n+1)//2) # Chai Wah Wu, Mar 08 2022

Formula

a(n) = n - A006165(n) = A006165(n) - A053646(n) = (n - A053646(n))/2 [for n > 1].

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

Conjectures from Peter Bala, Aug 03 2022: (Start)

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