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

%I #55 May 14 2024 05:19:57

%S 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,

%T 16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,18,19,20,21,22,

%U 23,24,25,26,27,28,29,30,31,32,32,32,32,32,32,32,32,32,32,32,32,32,32

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

%H R. J. Mathar, <a href="/A060973/b060973.txt">Table of n, a(n) for n = 1..1000</a>

%H Max A. Alekseyev, <a href="https://arxiv.org/abs/2304.04324">Enumeration of Payphone Permutations</a>, arXiv:2304.04324 [math.CO], 2023.

%H Michael De Vlieger, <a href="/A060973/a060973.png">Log-log scatterplot of a(n)</a>, n = 1..2^16.

%H H.-K. Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>. Preprint 2016.

%H 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:<a href="https://doi.org/10.1145/3127585">10.1145/3127585</a>

%H Jeffrey Shallit, <a href="https://arxiv.org/abs/2203.02917">Intertwining of Complementary Thue-Morse Factors</a>, arXiv:2203.02917 [cs.FL], 2022.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>.

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.

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

%F 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.

%F 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

%F Conjectures from _Peter Bala_, Aug 03 2022: (Start)

%F a(n - a(n)) = a(n - a(n - a(n - a(n)))).

%F If b(n) = a(a(n)) then b(n - b(n)) = b(n - b(n - b(n - b(n)))) for n >= 2. (End)

%F Sum_{n>=2} 1/a(n)^2 = Pi^2/6 + 2. - _Amiram Eldar_, Sep 08 2022

%e a(6) = 2*a(3) = 2*1 = 2.

%e a(7) = a(3) + a(4) = 1 + 2 = 3.

%p A060973 := proc(n)

%p option remember;

%p if n <= 2 then

%p return n-1;

%p fi;

%p if n mod 2 = 0 then

%p 2*procname(n/2)

%p else

%p procname((n-1)/2)+procname((n+1)/2);

%p fi;

%p end proc: # _R. J. Mathar_ Nov 30 2014

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

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A060973(n): return n-1 if n <= 2 else A060973(n//2) + A060973((n+1)//2) # _Chai Wah Wu_, Mar 08 2022

%o (PARI) a(n) = my(i=logint(n,2)-1); if(bittest(n,i), n - 2<<i, 1<<i); \\ _Kevin Ryde_, Aug 19 2022

%Y Cf. A006165, A053646.

%K nonn,easy

%O 1,4

%A _Henry Bottomley_, May 09 2001