Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #18 Dec 03 2024 12:24:25
%S 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,
%T 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,
%U 10,2,3,2,10,2,10,2,3,2,5,2,10,2,3,2,11,2
%N Lowest weight of rational fraction with denominator n.
%C 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<n, of wt(m/n).
%C It is conjectured by Kravitz and Sah that a(n) = O(log n).
%H N. Kravitz and A. Sah, <a href="https://doi.org/10.1007/s11083-020-09527-2">Linear extension numbers of n-element posets</a>, Order 38 (2021), 49-66.
%H M. Shrader-Frechette, <a href="https://www.jstor.org/stable/2690435">Modified Farey sequences and continued fractions</a>, Math. Magazine 54 (1991), 60-63.
%F a(n) = min_{d|n, d>1} A178031(d) for n>1. - _Andrey Zabolotskiy_, Dec 01 2024
%e 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.
%o (PARI) a(n)=if(n==1, return(1)); my(r=oo,t); for(m=1,n-1, t=vecsum(contfrac(m/n)); if(t<r, r=t)); r \\ _Charles R Greathouse IV_, Dec 01 2024
%Y Cf. A178031 (same but for irreducible fractions only).
%K nonn,new
%O 1,2
%A _Jeffrey Shallit_, Dec 01 2024