cp's OEIS Frontend

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

%I A060973 #55 May 14 2024 05:19:57
%S A060973 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 A060973 16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,18,19,20,21,22,
%U A060973 23,24,25,26,27,28,29,30,31,32,32,32,32,32,32,32,32,32,32,32,32,32,32
%N A060973 a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n), with a(1)=0 and a(2)=1.
%H A060973 R. J. Mathar, <a href="/A060973/b060973.txt">Table of n, a(n) for n = 1..1000</a>
%H A060973 Max A. Alekseyev, <a href="https://arxiv.org/abs/2304.04324">Enumeration of Payphone Permutations</a>, arXiv:2304.04324 [math.CO], 2023.
%H A060973 Michael De Vlieger, <a href="/A060973/a060973.png">Log-log scatterplot of a(n)</a>, n = 1..2^16.
%H A060973 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 A060973 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 A060973 Jeffrey Shallit, <a href="https://arxiv.org/abs/2203.02917">Intertwining of Complementary Thue-Morse Factors</a>, arXiv:2203.02917 [cs.FL], 2022.
%H A060973 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>.
%H A060973 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%F A060973 a(n) = n - A006165(n) = A006165(n) - A053646(n) = (n - A053646(n))/2 [for n > 1].
%F A060973 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 A060973 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 A060973 Conjectures from _Peter Bala_, Aug 03 2022: (Start)
%F A060973 a(n - a(n)) = a(n - a(n - a(n - a(n)))).
%F A060973 If b(n) = a(a(n)) then b(n - b(n)) = b(n - b(n - b(n - b(n)))) for n >= 2. (End)
%F A060973 Sum_{n>=2} 1/a(n)^2 = Pi^2/6 + 2. - _Amiram Eldar_, Sep 08 2022
%e A060973 a(6) = 2*a(3) = 2*1 = 2.
%e A060973 a(7) = a(3) + a(4) = 1 + 2 = 3.
%p A060973 A060973 := proc(n)
%p A060973     option remember;
%p A060973     if n <= 2 then
%p A060973         return n-1;
%p A060973     fi;
%p A060973     if n mod 2 = 0 then
%p A060973         2*procname(n/2)
%p A060973     else
%p A060973         procname((n-1)/2)+procname((n+1)/2);
%p A060973     fi;
%p A060973 end proc:  # _R. J. Mathar_ Nov 30 2014
%t A060973 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 A060973 (Python)
%o A060973 from functools import lru_cache
%o A060973 @lru_cache(maxsize=None)
%o A060973 def A060973(n): return n-1 if n <= 2 else A060973(n//2) + A060973((n+1)//2) # _Chai Wah Wu_, Mar 08 2022
%o A060973 (PARI) a(n) = my(i=logint(n,2)-1); if(bittest(n,i), n - 2<<i, 1<<i); \\ _Kevin Ryde_, Aug 19 2022
%Y A060973 Cf. A006165, A053646.
%K A060973 nonn,easy
%O A060973 1,4
%A A060973 _Henry Bottomley_, May 09 2001