login
A092054
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, ...].
1
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, 46, 48, 50, 51, 52, 57, 62, 63, 64, 66, 68, 69, 70, 73, 76, 77, 78, 80, 82, 83, 84, 88, 92, 93, 94, 96, 98, 99, 100, 103, 106, 107, 108, 110, 112, 113, 114, 120, 126, 127, 128, 130
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
2^a(n) = A001902(n) + A092053(n).
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