A378568 Lowest weight of rational fraction with denominator n.

1, 2, 3, 2, 4, 2, 5, 2, 3, 2, 6, 2, 6, 2, 3, 2, 7, 2, 7, 2, 3, 2, 8, 2, 4, 2, 3, 2, 8, 2, 8, 2, 3, 2, 4, 2, 9, 2, 3, 2, 9, 2, 9, 2, 3, 2, 9, 2, 5, 2, 3, 2, 10, 2, 4, 2, 3, 2, 10, 2, 10, 2, 3, 2, 4, 2, 10, 2, 3, 2, 10, 2, 10, 2, 3, 2, 5, 2, 10, 2, 3, 2, 11, 2

Offset: 1

Author

Jeffrey Shallit, Dec 01 2024

Keywords

• nonn

Comments

The weight wt(x) of a rational number x is defined to be the sum of the partial quotients in the continued fraction expansion of x. For example, 5/14 = [0,2,1,4], so wt(5/14) = 7. Here a(n) is the minimum, over all m, 1<=m

It is conjectured by Kravitz and Sah that a(n) = O(log n).

Examples

			For n = 23, we have a(23) = 8 because 5/23 = [0,4,1,1,2] with weight 8, and this is the smallest over all fractions m/23 with 1<=m<23.
		

Links

• N. Kravitz and A. Sah, Linear extension numbers of n-element posets, Order 38 (2021), 49-66.
• M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Magazine 54 (1991), 60-63.

Crossrefs

Cf. A178031 (same but for irreducible fractions only).

Programs

PARI

a(n)=if(n==1, return(1)); my(r=oo,t); for(m=1,n-1, t=vecsum(contfrac(m/n)); if(tCharles R Greathouse IV, Dec 01 2024

Formula

a(n) = min_{d|n, d>1} A178031(d) for n>1. - Andrey Zabolotskiy, Dec 01 2024

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.