Is the number of elements we need to construct $x$ equal to $\log_2(x) + O(1)$?
This question is inspired by question 2 of the 2018 European Girls' Mathematical Olympiad. I previously posted it on math.stackexchange.
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$. And $f(43)=7$, because $43 = \frac{129}{128} \cdot \frac43 \cdot 2^5$ but $43$ cannot be written as the product of $6$ 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.
- an upper bound for $f(x)$ is given by $\lfloor \log_2(x) \rfloor + s_2(x) - 1 \le 2 \log_2(x)$, where $s_2(x)$ is the sum of the digits of $n$ in binary. This upper bound is not sharp, as for $n=43$ it gives $5+4-1=8$, not $7$.
