OFFSET
1,2
COMMENTS
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).
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:
First differences appear to be essentially A136480. - Chris Boyd, Jan 14 2016
LINKS
Marek A. Suchenek, Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program, Fundamenta Informaticae 120 (2012), pp 75--92.
Wikipedia, Binary heap
FORMULA
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
a(n-1) = 2*n - 2*A000120(n) - A007814(n); see Suchenek link for a proof. - Marek A. Suchenek, Mar 16 2014
EXAMPLE
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.
PROG
(PARI) {a(n)=local(A); CF=contfracpnqn(vector(n, k, 1/k)); A=length(binary(numerator(1+CF[1, 1]/CF[2, 1])))-1}
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Feb 19 2004
STATUS
approved