Comprobar la perfecta cuadratura por el modulo de la división contra varias bases

Question

Estoy interesado en una prueba rápida para ver si un número es un cuadrado perfecto. Una buena prueba es observar cómo el número de extremos. En Base 10, un cuadrado perfecto termina en 0,1,4,5,6, o 9. Esto es útil porque puedo trivialmente filtrar los números que terminan de forma diferente antes de lo necesario para hacer más costosas operaciones.

También es cierto que en Base 16, un cuadrado perfecto termina en 0, 1, 4, 9.

Sin embargo, si nos fijamos en la no-perfecto-plaza de los números 11 y 17, podemos ver 11 pases de la Base 10 de la prueba, desde las 11 mod 10 = 1, pero no la Base 16 de la prueba (11 mod 16 = 11). Asimismo, el 17 de falla de la Base 10 de la prueba, sino que pasa a la Base 16 de la prueba. Creo que esto es porque el 10 tiene un factor que 16 no tiene, pero no estoy seguro.

Es fácil ver que la realización de ambas pruebas se filtran más números que cada uno de ellos por su propia cuenta, y es lógico pensar que existen más bases que filtrar los números adicionales.

Mi pregunta es: ¿por Qué estas dos bases de la prueba de un conjunto diferente de números, y cómo puedo elegir un conjunto mínimo de las bases que filtran la mayoría de los números?

(Me doy cuenta de cualquier método de elección de bases puede extenderse infinitamente, pero el infinito y rápido no llegar exactamente a lo largo. Yo soy más curioso en la teoría detrás de esto, y puedo hablar de una prueba de cobertura vs velocidad de equilibrio en Stack Overflow).

Answer 1

NO una respuesta, pero demasiado largo para un comentario.

Me gustaría incluir una pequeña prueba de la instrucción que se abrió con, por un poco de contexto. Si tenemos un número entero en base $10$, puede ser representado como $$n=C_0 10^0+C_1 10^1 +...+ C_k 10^k$$ donde cada una de las $C_i \lt 10$ $k+1$ es el número de dígitos que el número entero. Cuando nos cuadrado de este número entero, por expansión, queda claro que el único término que contiene a $10^0$ va a terminar siendo $$C_0^2 10^0$$ y, como nos quieren representar a su plaza de base $10$, el primer coeficiente de la plaza debe ser menor que $10$, así que el primer dígito de su plaza es $$C_0^2 \bmod 10$$ y, desde $C_0 \lt 10$, el único primeros dígitos de $n^2$ $$1\bmod 10=1$$ $$4\bmod 10=4$$ $$9\bmod 10=9$$ $$16\bmod 10=6$$ $$25\bmod 10=5$$ $$36\bmod 10=6$$ $$49\bmod 10=9$$ $$64\bmod 10=4$$ $$81\bmod 10=1$$ Lo que demuestra su declaración.

Ahora podemos generalizar esto a todas las bases. Un número $n$ base $b$ puede ser representado por $$n=C_0b^0+C_1b^1+...+C_kb^k$$ Donde cada una de las $C_i \lt b$ $k+1$ es el número de dígitos de $n$ base $b$. Siguiendo el mismo camino que hicimos en la última prueba, el conjunto de todas las posibles más pequeño de los dígitos es el conjunto $$\bigcup \limits_{a=1}^{b-1} \{a^2 \bmod b\}$$ deje que este conjunto contiene a $l$ elementos. Entonces usted está en busca de alguna base $b_m$ de que la proporción de $l$ $b_m-1$es mínimo.

Answer 2

La comprobación de su candidato número $x\bmod 24$ es una buena opción, especialmente si usted echa primero de los factores de $4$ $9$ ( $x'$ ). Entonces usted necesita $x'\equiv 1 \bmod 24$ por un candidato de la plaza.

La razón por la que acecha detrás de esto es que el Carmichael función de $\lambda(24)=2$, por lo que cada co-primer plazas a $1 \bmod 24$. Deslinde $4$s y $9$s sólo puede dejar a cero o un factor de $2$ o $3$, respectivamente, en el modificado número (uno de los dos haría que no son cuadrados). Y $24$ es el número más grande con $\lambda=2$.

Para la comprobación frente a cualquier otro de los números primos, en primer lugar reducir el candidato por la fundición de los factores de la plaza de que el primer, y luego la mitad de los posibles valores que se indican candidato plazas - todas las facultades de una raíz primitiva.