Representación de un número natrual por la suma de la progresión geométrica con un factor de escala mínimo

Question

Esta pregunta está inspirada en un leetcode pregunta. Supongamos que tenemos un número $x$ y queremos representar por una progresión geométrica. La forma más fácil de progresión de la es $1+(x-1)$. Pero ¿cómo encontrar a la serie con el mínimo factor de escala? Por ejemplo, $13 = 1 + 12 = 1 + 3 + 9$ $3$ es la solución correcta.

He intentado de alguna manera para trabajar con la ecuación $$\dfrac{r^n - 1}{r-1} = x,$$ y entonces me vino a $$r(x-r^{n-1}) = x-1,$$ lo que significa que tanto $r$ y la otra parte tiene que ser divisores de $x-1$.

Sé cómo hacer que un numéricos de solución con una secuencia de comandos de python, pero ¿cómo sería un matemático abordar este problema? ¿Hay alguna fórmula que puede ayudar? Traté de google "representación de número de la progresión geométrica", pero no encontramos nada.

Answer 1

No sé si este problema tiene muchas instancias interesantes. Hice una búsqueda rápida y encontré$1173$ números$x\leq10^6$ que se pueden escribir en el formulario$$x=1+r+r^2+\ldots+ r^n$ $ con natural$r\geq2$% y$n\geq2$. Entre estos solo hubo dos que poseen más de una representación (para que uno pueda seleccionar uno con un cociente mínimo$r$), a saber,$$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\ .$ $

Answer 2

Al principio, puede usarse las siguientes condiciones de divisibilidad: \begin{align} &r\ |\ x-1,\tag1\\ &r^{n-1}-1\ |\ x-1,\tag2\\ &x\ |\ r^n - 1,\tag3\\ \end {align} para el$n$% \begin{align} &r\in\left[\sqrt[n]{x+1}], \sqrt[n-1]x\ \right],\tag4\\ \end {align} proporcionado y las restricciones$(4)$ permiten optimizar el programa para lo requerido $O(\log x).$

Answer 3

La búsqueda binaria proporciona un algoritmo$O(\log^2x)$. Suponiendo que desea$r>1$, tenga en cuenta que$n-1 \leq \log_2 x$ (porque$x \geq r^{n-1}$). Por lo tanto, puede buscar cada valor de$n$ en este rango.

Para un valor fijo de$n$, para encontrar$r$, realiza una búsqueda binaria. Dejar $f(r)=\dfrac{r^n-1}{r-1}$. Si$f(r)$ es mayor que$x$, busque en la mitad izquierda de su intervalo actual, y si$f(r)$ es más pequeño, busque en la mitad derecha. Si$f(r)=x$, ha terminado.