<s>[INST] Writing integers as a product of as few elements of $\{\frac21, \frac32, \frac43, \frac54, \ldots\}$ as possible 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.

 [/INST] 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.
</s>