¿Cuántos números primos entre 1000-10000 (inclusive) que si se toma la suma de sus dígitos, ese número es divisible por 8?

Question

Cada año intento competir en concursos de matemáticas en mi escuela y me encuentro con problemas como...

Cuántos números primos entre 1000-10000 (inclusive) que si se toma la suma de sus dígitos, ese número es divisible por 8. Por ejemplo 17, 1+7=8. Que es divisible por 8.

Tenemos que mostrar nuestro trabajo. D

Answer 1

Sabes que la máxima suma de dígitos posible (ignorando la condición de primo por un momento) es $36$ debido a la suma de dígitos de $9999$ dentro de su rango.

Los posibles dígitos bajo esa barrera que son divisibles por $8$ (ignorando $0$ ) son $8, 16, 24, 32$ .

¿De cuántas maneras puedes escribir cada una de ellas como una suma de $4$ dígitos donde cada dígito cae dentro de $0 \leq d \leq 9$ ?

Si trabajaras en equipo y tuvieras que hacerlo a mano, probablemente podrías dividir y conquistar y hacer que cada persona se ocupara de un dígito diferente para enumerar todos los casos más rápidamente.

Sin embargo, usted ya conoce el $24$ digitsum es una pérdida de tiempo, ya que cualquier número cuya digitsum es divisible por $24$ también será divisible por $3$ lo que significa que el propio número será divisible por $3$ y por lo tanto no es primo.

A continuación, se pueden eliminar los casos que no se pueden reordenar para formar un número primo (como los que faltan un $1, 3, 7$ ou $9$ para formar el último dígito del primo).

Esto le deja con los siguientes casos:

$8 = [[0, 0, 1, 7], [0, 0, 3, 5], [0, 1, 1, 6], [0, 1, 2, 5], [0, 1, 3, 4], [0, 2, 3, 3], [1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3]]$

$16 = [[0, 0, 7, 9], [0, 1, 6, 9], [0, 1, 7, 8], [0, 2, 5, 9], [0, 2, 7, 7], [0, 3, 4, 9], [0, 3, 5, 8], [0, 3, 6, 7], [0, 4, 5, 7], [1, 1, 5, 9], [1, 1, 6, 8], [1, 1, 7, 7], [1, 2, 4, 9], [1, 2, 5, 8], [1, 2, 6, 7], [1, 3, 3, 9], [1, 3, 4, 8], [1, 3, 5, 7], [1, 3, 6, 6], [1, 4, 4, 7], [1, 4, 5, 6], [1, 5, 5, 5], [2, 2, 3, 9], [2, 2, 5, 7], [2, 3, 3, 8], [2, 3, 4, 7], [2, 3, 5, 6], [3, 3, 3, 7], [3, 3, 4, 6], [3, 3, 5, 5], [3, 4, 4, 5]]$

$32 = [[5, 9, 9, 9], [6, 8, 9, 9], [7, 7, 9, 9], [7, 8, 8, 9]]$

A continuación, para cada permutación única de cada caso que esté dentro de su rango aceptable (que también termina en $1, 3, 7$ ou $9$ ), comprueba si el número es realmente primo. Sólo hay $276$ números para probar.

Una forma de hacerlo es enumerando los primos (relevantes) en $\sqrt{10000} = 100$ :

$7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$

Luego compruebas la divisibilidad de cada uno de ellos en tu número candidato. Si todos fallan la prueba, entonces el número candidato es primo.

Supongo que al menos puedes usar una calculadora para este paso, porque de lo contrario probablemente sea un problema demasiado tedioso para hacerlo a mano. El tamaño de tu equipo tendría que ser lo suficientemente grande como para poder realizar todos los cálculos de comprobación de primalidad en el tiempo asignado.

Otro enfoque (suponiendo que tuviera un equipo lo suficientemente grande) es dividir el $1000-10000$ en trozos y hacer que cada persona enumere su sección del rango y luego usar el enfoque de la criba segmentada de Eratóstenes usando los primos bajo $100$ para tachar los números compuestos. Entonces puedes comprobar directamente las sumas de los dígitos de los primos resultantes.

Answer 2

Otro enfoque es comenzar con todos los números de tres dígitos de $100$ a $999$ . Se añade un dígito de unidad a cada uno para hacer la suma digital total $8$ , $16$ ou $32$ (no $24$ ya que esto implicaría un múltiplo de $3$ ). A continuación, se comprueba la primalidad de cada número de cuatro dígitos.

En realidad, no es necesario conservar todos los números iniciales de tres dígitos. Se rechazan aquellos en los que la suma de los tres dígitos es par porque el dígito de las unidades tendría que ser par, lo que supone un problema. También encontramos:

Sumas de tres dígitos de $17$ , $19$ y $21$ fallan porque no podemos obtener la suma de cuatro dígitos para $32$ .

Sumas de tres dígitos de $3$ , $11$ y $27$ fallan porque el dígito de las unidades añadidas es $5$ .

Una suma de tres dígitos de $7$ permite que dos candidatos con $1$ o $9$ como un dígito de las unidades, pero otras sumas de tres dígitos que sobreviven sólo dan un candidato por semilla de tres dígitos.

Con estas propiedades se reducen los juicios a unos pocos cientos. Aquí está el principio de la lista de candidatos:

1007 1043 1061 1069 1087 1133 1151 1159 1177 1223 1241 1249 1267 1313 1331 1339 1357 1393 1403 1421 1429 1447 1483 1511 1519 1537 1573 1591 1601 1609 1627 1663 1681 1717 1753 1771 1807 1843 1861 1933 1951 etc.