Representation of a natrual number by the sum of geometric progression with minimal scale factor This question is inspired by a leetcode question. Let's say we have a number $x$ and we want to represent it by a geometric progression. The easiest progression is $1+(x-1)$. But how to find the series with the minimal scaling factor? For example $13 = 1 + 12 = 1 + 3 + 9$ and $3$ is the right solution.
I tried somehow to work with the equation
$$\dfrac{r^n - 1}{r-1} = x,$$
and then I came to
$$r(x-r^{n-1}) = x-1,$$
which means that both $r$ and the other part has to be dividers of $x-1$.
I know how to make a numeric solution with a python script but how would a mathematician tackle this issue? Is there any formula which can help? I tried to google “representation of number by geometric progression” but did not find anything.
 A: I don't know whether this problem has many interesting instances. I did a quick search and found $1173$ numbers $x\leq10^6$ that can be written in the form $$x=1+r+r^2+\ldots+ r^n$$
with natural $r\geq2$ and $n\geq2$. Among these there were only two that possess more than one such representation (so that one could select one with minimal quotient $r$), namely
$$31=\sum_{k=0}^4 2^k=\sum_{k=0}^2 5^k,\qquad 8191=\sum_{k=0}^{12} 2^k=\sum_{k=0}^2 90^k\ .$$
A: At first, can be used the next conditions of divisibility:
\begin{align}
&r\ |\ x-1,\tag1\\
&r^{n-1}-1\ |\ x-1,\tag2\\
&x\ |\ r^n - 1,\tag3\\
\end{align}
so for the given $n$
\begin{align}
&r\in\left[\sqrt[n]{x+1}], \sqrt[n-1]x\ \right],\tag4\\
\end{align}
and constraints $(4)$ allows to optimize the program to the required $O(\log x).$
A: Binary search gives a $O(\log^2x)$ algorithm. Assuming that you want $r>1$, note that $n-1 \leq \log_2 x$ (because $x \geq r^{n-1}$). Thus, you can search for each value of $n$ in this range.
For a fixed value of $n$, to find $r$, you do binary search. Let $f(r)=\dfrac{r^n-1}{r-1}$. If $f(r)$ is larger than $x$, search in the left half of your current interval, and if $f(r)$ is smaller, search in the right half. If $f(r)=x$, you are done.
