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

Table of n, a(n) for n=1..67.

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

Cf. A001902, A092053, A136480.

Sequence in context: A163578 A345918 A269389 * A334573 A228370 A186112

Adjacent sequences: A092051 A092052 A092053 * A092055 A092056 A092057

Keyword

nonn

Author

Paul D. Hanna, Feb 19 2004

Status

approved