Representation of a natrual number by the sum of geometric progression with minimal scale factor

Question

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.

Answer 1

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).$

Answer 2

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.

Answer 3

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\ .$$