cp's OEIS Frontend

A378568 Lowest weight of rational fraction with denominator n.

%I A378568 #18 Dec 03 2024 12:24:25
%S A378568 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 A378568 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 A378568 10,2,3,2,10,2,10,2,3,2,5,2,10,2,3,2,11,2
%N A378568 Lowest weight of rational fraction with denominator n.
%C A378568 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 A378568 It is conjectured by Kravitz and Sah that a(n) = O(log n).
%H A378568 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 A378568 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 A378568 a(n) = min_{d|n, d>1} A178031(d) for n>1. - _Andrey Zabolotskiy_, Dec 01 2024
%e A378568 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 A378568 (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 A378568 Cf. A178031 (same but for irreducible fractions only).
%K A378568 nonn
%O A378568 1,2
%A A378568 _Jeffrey Shallit_, Dec 01 2024