Writing integers as a product of as few elements of $\{\frac21, \frac32, \frac43, \frac54, \ldots\}$ as possible

Question

This question is inspired by question 2 of the 2018 European Girls' Mathematical Olympiad. Also posted on mathoverflow.

Any integer $x \ge 2$ can be written as a product of (not necessarily distinct) elements of the set $A = \{\frac21, \frac32, \frac43, \frac54, \ldots\}$, as can be seen from a simple telescoping argument. Let $f(x)$ be the minimum number of elements of $A$ required.

For example, $f(11)=5$ because $11 = \frac{33}{32} \cdot \frac{4}{3} \cdot \frac{2}{1} \cdot \frac{2}{1} \cdot \frac{2}{1}$ (or, alternatively, $11 = \frac{11}{10} \cdot \frac{5}{4} \cdot \frac21 \cdot \frac21 \cdot \frac21$), but $11$ cannot be written as the product of $4$ or less elements of $A$. In general, it seems difficult to compute $f(x)$ directly.

Clearly we have $f(xy) \le f(x) + f(y)$ for any $x,y \ge 2$. The EGMO question asks to show that this inequality is strict infinitely often (an example is $x=5$, $y=13$). Here we ask:

For integral $x \ge 2$, let $f(x)$ be the smallest $k$ so that $x$ can be written as product of $k$ elements of $\{\frac21, \frac32, \frac43, \ldots\}$.

Is it true that $f(xy) =f(x) + f(y) - O(1)$?

In other words, is the difference between $f(x)+f(y)$ and $f(xy)$ bounded?

Some observations:

• $f(x) \ge \log_2(x)$ as $A$ has no elements larger than $2$;
• if it were true that $f(x) = \log_2(x) + O(1)$, this would imply that the question above has a positive answer.

Answer 1

We can compute an upper bound to $f(x)$ by adding $\lfloor \log_2(x)\rfloor$ to the number of $1$s in the binary expansion of $x$ and subtracting $1$. This gives $f(5)=2+2-1=3,5=\frac 54 \frac 21 \frac 21, f(13)=3+3-1=5, 13=\frac {13}{12} \frac 32(\frac21)^3,f(65)=6+2-1=7,65=\frac {65}{64}(\frac 21)^6$
To prove that we can find an expansion like this, write $x=x_0$ in binary. We will make a descending chain of $x_i$ ending with $1$ where $\frac {x_i}{x_{i+1}}\in A.$ If $x_i$ is odd, $x_{i+1}=x_i-1$. If $x_i$ is even, $x_{i+1}=\frac {x_i}2$. This gets an expression for $x_0$ with the stated number of steps. We have one $-1$ step for every $1$ in the expansion except the leading one and one divide by $2$ step for every power of $2$ in the leading bit. This does not prove that there is not a shorter expression. user133281 gives the example of $43$ which I represent as $\frac {43}{42}2\frac {21}{20}2^2\frac 542^2$ for $8$ terms but can also be $\frac {129}{128}\frac 432^5$ for seven.

Given this expression for $f(x)$ we want to show that we can find $x$ and $y$ such that $xy$ has arbitrarily many fewer $1$ bits in binary than the sum of the number of bits in $x$ and $y$. We use the fact that if $b$ is odd $2^{ab}+1=(2^a+1)(2^{a(b-1)}-2^{a(b-2)}-2^{a(b-3)}-\ldots+1)$ so let $x=2^a+1$ with two bits on, $y=2^{a(b-1)}-2^{a(b-2)}-2^{a(b-3)}-\ldots+1$ with $a(b-1)/2$ bits on and $xy$ has only two bits on, so $f(x)+f(y)-f(xy)=a(b-1)/2$ We still need to justify that there are $y$s that don't have significantly shorter representations.

Answer 2

This is an interesting problem... almost certainly the savings $\delta(x,y)=f(x)+f(y)-f(xy)$ is not bounded, as another answer has heuristically argued, but this seems difficult to prove. Call $$\Delta(x)\equiv \frac{f(x)}{\log_2 x} - 1$$ the "encoding inefficiency" of $x$. We know that $\Delta(x)\ge 0$ for all $x$, with equality when $x$ is a power of $2$. Note that $$\Delta(xy)=\frac{f(xy)}{\log_2 (xy)}-1 = \frac{(f(x) -\log_2 x)+ (f(y)-\log_2 y)}{\log_2 x+\log_2 y} - \frac{\delta(x,y)}{\log_2 (xy)}=\frac{\Delta(x)\log_2 x + \Delta(y)\log_2 y}{\log_2 x + \log_2 y} - \frac{\delta(x,y)}{\log_2(xy)},$$ or $$ \frac{\delta(x,y)}{\log_2(xy)} = \frac{\Delta(x)\log_2 x + \Delta(y)\log_2 y}{\log_2 x + \log_2 y} - \Delta(xy) \ge \frac{1}{2}\Delta(\max\{x,y\}) - \Delta(xy). $$ So we can show that $\delta(x,y)$ is unbounded by exhibiting a family of pairs $\langle x, y \rangle$, with $x \le y$, where $xy$ has an efficient encoding but $y$ does not (for instance, if $\Delta(xy) \rightarrow 0$ and $\Delta(y) \not\rightarrow 0$). While many infinite families have efficient encodings (e.g., those with a fixed or slowly growing number of $1$'s in their binary expansions), the difficulty lies in showing that any particular family of $y$'s has no efficient encodings.

As pointed out by OP, it's not immediately obvious that we can even compute $f(x)$ for a particular $x$; it's worth showing how to do that. We're trying to write $x$ as a product of terms of the form $1 + 1/n$; these terms are no bigger than $2$, but can be arbitrarily close to $1$. If we're trying to write $x$ as a product of $k$ terms, though, the geometric mean of the terms is $\sqrt[k]{x}$, and so $1 + 1/n \ge \sqrt[k]{x}$ for at least one term, or $n \le 1 / (\sqrt[k]{x}-1)$, leaving us only a finite number of $n$'s to check. Specifically, we can write the following recursion:

def shortestTup(x, y = 1):
    '''Return the shortest tuple of n_i >= 1 where the product of 1 + (1 / n_i)                                                                                                   
    is equal to x / y.'''
    if x < y: return None
    k = 0
    while True:
        tup = anyTup(long(x), long(y), k)
        if tup != None: return (k, tup)
        k += 1

def anyTup(x, y, k):
    '''Return a k-or-shorter-tuple of n_i >= 1 where the product of 1 + (1 / n_i)                                                                                                 
    is equal to x / y.'''
    if x < y: return None
    if x == y: return ()
    (x, y) = inLowestTerms(x, y)
    if x == y + 1:
        if k >= 1: return (y,)
        return None
    n = (y - 1) / (x - y)
    while (n + 1)**k * y >= n**k * x:
        tup = anyTup(x * n, y * (n + 1), k - 1)
        if tup != None: return tup + (n,)
        n += 1L
    return None

This code can calculate $f(x)$ for all $x$ up to $5000$ in about $15$ seconds on my machine. In practice, it can encounter stumpers even for not-very-large numbers. For instance, $23 \le f(535601) \le 24$, because one expansion of length $24$ is $$ 535601 = \left(1 + \frac{1}{706846589749298638168071864320}\right)\cdot\left(1 + \frac{1}{375991114190029}\right)\cdot\left(1 + \frac{1}{15328152}\right)\cdot\left(1 + \frac{1}{3391}\right)\cdot\left(1 + \frac{1}{47}\right)\cdot 2^{19}, $$ and the program can rule out expansions of length $22$ quickly; but determining whether there is an expansion of length $23$ takes a very long time. Using this code to check the values $\delta(x,y)$ for all $xy \le 30000$ reveals the following record-setters: $$ \delta(3,11)=f(3) + f(11) - f(33) = 2 + 5 - 6 = 1 \\ \delta(7,23)=f(7) + f(23) - f(161) = 4 + 7 - 9 = 2 \\ \delta(23,23)=f(23) + f(23) - f(529) = 7 + 7 - 11 = 3 \\ \delta(23,359)=f(23) + f(359) - f(8257) = 7 + 12 - 15 = 4, $$ but no more so far. It might be worth checking whether the candidate "inefficient" $y_{a,b}$'s proposed in the other answer do, in fact, lead to large values of $\delta(2^a+1,y_{a,b})$ as a family.