|
%I #39 Apr 14 2021 05:28:51
%S 1,2,4,6,7,8,11,14,15,16,18,20,21,22,26,30,31,32,34,36,37,38,41,44,45,
%T 46,48,50,51,52,57,62,63,64,66,68,69,70,73,76,77,78,80,82,83,84,88,92,
%U 93,94,96,98,99,100,103,106,107,108,110,112,113,114,120,126,127,128,130
%N Base-2 logarithm of the sum of numerator and denominator of the convergents of the continued fraction expansion [1; 1/2, 1/3, 1/4, ..., 1/n, ...].
%C Consider the convergents of the continued fraction expansion [1; 1/2, 1/3, 1/4, ..., 1/n, ...]. The numerators of the convergents are A001902 (successive denominators of Wallis's product approximation to Pi/2) and the denominators of the convergents are A092053. The sum of the numerators and the denominators equals a power of 2: A001902(n) + A092053(n) = 2^a(n).
%C Also, a(n-1) is the number of the comparisons that Floyd's heap-construction algorithm will use, in the worst case, to create an n-element heap. See Wikipedia link, section "Building a heap". - _Marek A. Suchenek_, Mar 16 2014:
%C First differences appear to be essentially A136480. - _Chris Boyd_, Jan 14 2016
%H Marek A. Suchenek, <a href="http://dx.doi.org/10.3233/FI-2012-751">Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program</a>, Fundamenta Informaticae 120 (2012), pp 75--92.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F 2^a(n) = A001902(n) + A092053(n).
%F It appears that a(n) = Sum_{k=1..n} A001511(floor((k+1)/2)). Equivalently, a(n) = 2n + 1 - A000120(n) - A000120(n+1) = A011371(n) + A011371(n+1). - _Franklin T. Adams-Watters_, Feb 02 2006
%F a(n-1) = 2*n - 2*A000120(n) - A007814(n); see Suchenek link for a proof. - _Marek A. Suchenek_, Mar 16 2014
%e a(4)=6 since [1; 1/2, 1/3, 1/4] = 1 + 1/(1/2 + 1/(1/3 + 1/(1/4))) = 45/19; and the sum of the numerator and denominator of 45/19 equals 45 + 19 = 2^6.
%o (PARI) {a(n)=local(A);CF=contfracpnqn(vector(n,k,1/k)); A=length(binary(numerator(1+CF[1,1]/CF[2,1])))-1}
%Y Cf. A001902, A092053, A136480.
%K nonn
%O 1,2
%A _Paul D. Hanna_, Feb 19 2004
|
