A089636 Least k, 1 <= k <= 2^n, such that the continued fraction for 2^n/k contains the maximum number of elements.

1, 3, 5, 9, 23, 39, 79, 158, 281, 741, 1145, 2297, 4495, 10111, 20223, 40446, 80983, 162009, 323369, 646271, 1216723, 2592211, 5184422, 9733109, 20739329, 41467565, 81559503, 163649289, 311481083, 662667007, 1325334527, 2628708543, 5308871023, 9627863373

Offset: 1

Author

Benoit Cloitre, Jan 01 2004

Keywords

• nonn

Comments

From Jon E. Schoenfield, Nov 05 2014: (Start)

Several terms are close to 2^n / phi, where phi = (1 + sqrt(5))/2 = 1.6180339... (see A001622); e.g., 2^22/a(22) = 4194304/2592211 = 1.6180411... .

When a ratio r of two integers is expressed as a continued fraction, it cannot have a relatively large number of elements (i.e., relative to other fractions whose numerators and denominators are very roughly the same size as the numerator and denominator of r, respectively) if any of the elements of the continued fraction are large, so the elements of the continued fractions for 2^n / a(n) tend to consist only of small numbers, mostly ones; e.g., 131072/80983 = cf[1; 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 3] (20 elements, consisting of 17 ones, 2 threes, and 1 five).

For n = 1..34, the maximum number of elements is 1, 2, 4, 4, 5, 7, 9, 9, 10, 12, 12, 14, 15, 17, 19, 19, 20, 22, 22, 24, 26, 27, 27, 29, 30, 32, 33, 34, 35, 37, 39, 39, 41, 41.

If a(n) is even, then a(n) = 2*a(n-1), so 2^n/a(n) reduces to 2^(n-1)/a(n-1), and the maximum number of elements is the same at n as it is at n-1. Up to n=34, a(n) is even only at n = 8, 16, and 23. (End)

Examples

			From _Jon E. Schoenfield_, Nov 05 2014: (Start)
The continued fractions for 2^3/k for k = 1..2^3 are
8/1 = 8 (1 element)
8/2 = 4 (1 element)
8/3 = 2 + 1/(1 + 1/2) = cf[2;1,2] (3 elements)
8/4 = 2 (1 element)
8/5 = 1 + 1/(1 + 1/(1 + 1/2)) = cf[1;1,1,2] (4 elements)
8/6 = 4/3 = 1 + 1/3 = cf[1;3] (2 elements)
8/7 = 1 + 1/7 = cf[1;7] (2 elements)
8/8 = 1 (1 element)
so the first (and, in this case, only) value of k at which the maximum number of elements (i.e., 4) occurs is k=5; thus, a(3)=5. (End)
		

Crossrefs

Cf. A084242.

Formula

a(n) = A084242(2^n).

Extensions

More terms from Jon E. Schoenfield, Nov 05 2014