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
Keywords
Examples
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.
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
Programs
-
PARI
{a(n)=local(A);CF=contfracpnqn(vector(n,k,1/k)); A=length(binary(numerator(1+CF[1,1]/CF[2,1])))-1}
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
Comments