What is the smallest fraction produced by a sum of fractions with bounded denominator?

411 Views Asked by At

For $x$ a sum of fractions:

$$ x = \sum_{i=1}^{N}\frac{a_i}{b_i} $$ for all $a_i, b_i \in \mathbb{Z}$ with $ 0 < b_i \leq D$ and $N$ are non-zero positive integers, I know that the denominator of $x$ will not exceed the least common multiple of all positive integers less than or equal to $D$. See OEIS A003418.

So the denominator of $x$ will not grow without bound. My question is, what is the smallest fraction (closest to $0$) that such a sum can produce? Please provide a worked example assuming that $D = 12$. $N$ can be any integer greater than $1$.

Edit

I'd also like to know how to find sequences that produce the smallest value for a given $D$ and how many such sequences there are with minimal $N$ and fractions in lowest terms.

1

There are 1 best solutions below

4
On BEST ANSWER

The LCM of $1, \ldots, 12$ is $27720$. One example with sum $1/27720$ (there are infinitely many others) is $$ \dfrac{3}{7} + \dfrac{1}{8} + \dfrac{ 2}{9} + \dfrac{3}{10} + \dfrac{1}{11} -\dfrac{14}{12}$$

Hint: if $L(d)$ is the LCM of $1, \ldots, d$, then $$ \dfrac{1}{L(d)} = \dfrac{\gcd(d,L(d-1))}{d\; L(d-1)}$$

Now use Bezout's identity.

EDIT: There are two sets of $5$ integers $\le 12$ whose LCM is $27720$: $\{5,7,8,9,11\}$ and $\{7,8,9,10,11\}$. Let's try using five fractions with denominators $5,7,8,9,11$. From $3 \times 7 - 4\times 5 = 1$ we have $$\dfrac{3}{5} + \dfrac{-4}{7} = \dfrac{1}{35}$$ From $-13 \times 8 + 3 \times 35 = 1$ and this we have $$ \dfrac{1}{280} = \dfrac{-13}{35} + \dfrac{3}{8} = \dfrac{-39}{5} + \dfrac{52}{7} + \dfrac{3}{8}$$ From $-31 \times 9 + 1 \times 280 = 1$ and this we have $$ \dfrac{1}{2520} = \dfrac{-31}{280} + \dfrac{1}{9} = \dfrac{1209}{5} + \dfrac{-1612}{7} + \dfrac{ -93}{8} + \dfrac{1}{9}$$ Finally, from $-229 \times 11 + 1 \times 2520 = 1$ and this we have $$ \dfrac{1}{27720} = \dfrac{-276861}{5} + \dfrac{369148}{7} + \dfrac{21297}{8} + \dfrac{-229}{9} + \dfrac{1}{11}$$