Solución de $x^2 + s(x)\cdot x - n = 0$, $s(x)$ es la suma de digitos de $x$.

Question

Este problema viene de una programación de la página web del concurso, pero me gustaría interesado en analizarlo desde las matemáticas prespectiva. Dado este problema, debemos crear un programa que nos puede dar el resultado correcto de la entrada dada. El programa se debe ejecutar en el plazo de los proporcionados por el sistema.

El Problema

Vamos a definir la función $s$ que tome los datos de entrada de enteros positivos tal que $s(x)$ es la suma de los dígitos de $x$.

Por ejemplo, $$s(1024) = 1 + 0 + 2 + 4 = 7$$

Dado un número entero constante $n$ como la entrada del programa. Ahora, encontrar un número entero positivo de la solución de $x$ en la ecuación

$$x^2 + s(x) \cdot x - n = 0.$$

Si hay más de una solución existe, elige el más bajo. Si la solución no existe, dar salida -1.

Límite de tiempo del programa: 2 segundo.

Gama de la entrada $n$: $[1, 10^{18}]$

La Solución

En la búsqueda de la solución, se puede recorrer de un rango de valores posibles de x, y tratar cada uno de estos valor si se satisface la ecuación o no.

Para mejorar el tiempo de ejecución del programa, se debe elegir el menor rango de x.

Mi Pregunta

1. ¿Cuál es el menor rango de valores posibles de x que nos podría recorrer para encontrar la respuesta del problema anterior?

2. Hay una mejor manera de encontrar la solución sin que la iteración de la serie el posible valor de x?

Mi Intento:

Considere la posibilidad de que $$x^2 + s(x) \cdot x - n = 0$$ $$\Leftrightarrow x ( x + s(x) ) = n$$

y ya que tanto $x$ $(x + s(x))$ son enteros positivos y el producto de ambos número del es $n$, podemos concluir que $x$ $(x + s(x))$ es un par de positivos factor de $n$.

Desde $x$ es un factor de $n$, ahora tenemos el primer rango posible de $x$, que es $[1, n]$.

Pero, iterando $x$ durante este intervalo da mal funcionamiento del programa. Para pequeño valor de $n$, que no importa, pero para $n \geq 10^{17}$, el programa alcanzará es el límite de tiempo.

Si pudiera recordar correctamente, tenemos este teorema

$$x_1 \cdot x_2 = x$$

y

$$x_1 \leq x_2$$

implica que

$$x_1 \leq \sqrt{x} \leq x_2$$

Y desde $x (x + s(x)) = n$ $x \leq x + s(x)$

tenemos $x \leq \sqrt{n} \leq x + s(x)$

Ahora tenemos el segundo rango: $[1, \sqrt{n}]$

Pero, aún así, esta gama también dan mal rendimiento para grandes $n$.

Mi último intento es considerar el mayor valor posible de $s(x)$, que es el dígito de $x$ todos los $9$ $x$ menos de o igual al valor máximo de $n$, $10^{18}$.

$$s(x) \leq s(999,999,99 \cdots 9,999) = 9 \cdot 18 = 162$$

Por lo tanto, tenemos

$$x + s(x) \leq x + 162$$

de modo que, $$\sqrt{n} \leq x + s(x) \leq x + 162 \leq \sqrt{n} + 162$$ por lo tanto, $$\sqrt{n} - 162 \leq x \leq \sqrt{n}$$

Ahora, tenemos la mejor gama será más que suficiente para todo valor de $x$. $$l_1 = \max \{ 1, \sqrt{n} - 162 \}$$ $$l_2 = \sqrt{n}$$ el rango es de $[l_1, l_2]$

Pero, a pesar de que debe haber una mejor solución a este problema. De ahí que trate de $$l_1 = \max \{ 1, \sqrt{n} - 162/2 \}$$ Y que variedad es también correcto. Pero no puedo justificar mi hallazgo.

Así que, de ahí mi tercera pregunta:

1. Por qué $l_1 = \max \{ 1, \sqrt{n} - 162/2 \}$ también nos da la solución correcta?

Answer 1

Aunque no es una respuesta completa a sus preguntas, he aquí un truco que te permitirá reducir la colección de números que usted tiene que tratar (y por lo tanto una respuesta a la pregunta 2).

Debido a $10\equiv 1 \pmod 9$, $10^k \equiv 1 \pmod 9$ por cada $k\in \mathbb N$. Si escribimos un número, en términos de sus dígitos, $x=\sum a_k 10^k$, entonces a partir de la $\sum a_k 10^k \equiv \sum a_k \pmod 9$,$s(x)\equiv x \pmod 9$. Este hecho puede ser utilizado para dar una forma de comprobar la aritmética, entre otras cosas.

Por lo tanto, si $x^2 + s(x)x = n$,$2x^2 \equiv n \pmod 9$. Desde $(2)(5)=10 \equiv 1 \pmod 9$, podemos multiplicar para obtener $x^2 \equiv 5n \pmod 9$.

Las plazas modulo 9 $0, 1, 4, 7$, por lo menos que el resto de la división de $5n$ $9$ es uno de estos números, NO hay soluciones.

Si el resto es uno de esos números, usted necesita saber las raíces cuadradas modulo 9 de saber qué valores de $x$ a intentar.

Para esto, tenemos la siguiente.

$0^2\equiv 3^2 \equiv 6^2 \equiv 9 \pmod 9$, $1^2\equiv 8^2 \equiv 1 \pmod 9$, $2^2\equiv 7^2 \equiv 4 \pmod 9$ y $4^2 \equiv 5^2 \equiv 7 \pmod 9$.

El resultado de esto es que si $n$ es un múltiplo de a $9$, entonces usted sólo tiene que comprobar la cantidad de $3$ (reducción del número de cosas que usted tiene que comprobar por un factor de $3$). De lo contrario, dependiendo del módulo de $5n\bmod 9$, usted tiene que comprobar los números NO (5 de el resto de los casos), o usted tiene que comprobar $2/9$ de los números (3 de los casos restantes). Por lo tanto, cualquier intervalo que usted está trabajando, usted tiene por lo menos una velocidad de hasta por un factor de $3$, si no más.

---

Otro comentario, que da una pequeña aceleración más de lo que ya tenemos, pero las respuestas de la pregunta 3. Como se observa, $x<\sqrt n$, y el número de dígitos de $x$ es en la mayoría de las $\lceil \log_{10} x \rceil$, y desde $s(x)$ es en la mayoría de las $9$ multiplicado por el número de dígitos de $x$,$s(x)<9 \lceil \log_{10} \sqrt n \rceil=9\lceil \frac{1}{2}\log_{10} n \rceil$.

Por lo tanto, dado $n$, puede limitar su búsqueda para$x$$[\sqrt n - 9\lceil \frac{1}{2}\log_{10} n \rceil, \sqrt n]$. El factor de $1/2$ aquí las respuestas a la pregunta 3. Nota, que probablemente podría afeitarse $1$ o $2$ números de la gama por ser más cuidadosos con el redondeo, pero no veo ninguna razón obvia por la cual podemos cortar más. Si combinamos esto con el comienzo de mi respuesta, usted tiene que comprobar en la mayoría de las $3\lceil \frac{1}{2}\log_{10} n \rceil$ números para encontrar la solución, si existe, y no los números de una buena parte del tiempo cuando no existe ninguna solución.

Answer 2

Desde $x<\sqrt n$ y $n\le10^{18}$, tenemos que $x<10^9$. Entonces $x$ tiene a más dígitos de $9$ y $s(x)\le9\times9=81$. Esto implica que el $x^2+81\,x-n\ge0$. Se deduce fácilmente que hay que x\ge\frac $$ {-81 + \sqrt {81 ^ 2 + 4\, n}} {2} = \sqrt {n + (81/2) ^ 2} -81/2. $$

Answer 3

Al lado de la excelente modulo 9 trucos Aaron te dio, si $n$ pasa sus pruebas lo más fácil es probar la gama de la correcta $1 \le s(x) \le 162$ $s(x) \pmod 9$. Simplemente enchufe cada uno en la fórmula cuadrática y resuelve la $x$. Si no viene hacia fuera de la integral, pasar a la siguiente. Si es así, Compruebe la suma de dígitos contra la supuesta $s(x)$. Si coincide, éxito y denunciarlo. Si no, ir a la siguiente. En los números de $50$ más para probar, que deben caber en 2 segundos fácilmente.