Suma de las cifras de todos los números de 4 cifras divisibles por 7

Question

¿Cuál sería la manera de enfocar este problema?

Answer 1

Una forma de hacerlo es observar el patrón subyacente de cuándo cambia cada dígito a medida que se cuenta desde el primero hasta el último número de la serie. Yo lo haré para el dígito de miles, y tú puedes probar con el resto. Tendrás que pensar en cada uno de ellos por separado.

El primero es $1001$ y el último es $9996$ .

Hacer esto con un ordenador es fácil. Hacerlo a mano es sencillo, pero hay que fijarse en los detalles. Hay muchas posibilidades de equivocarse por uno.

El primer número divisible por $7$ en cada mil es:

$$1001, 2002, 3003, 4004, 5005, 6006, 7000, 8001, 9002,$$

y el último es sólo siete menos el primero de los próximos mil:

$$1995, 2996, 3997, 4998, 5999, 6993, 7994, 8995, 9996.$$

Existen $143$ términos de la serie de $1001$ a $1995$ . Lo mismo ocurre con los otros miles excepto el $6000$ 's, donde hay $142$ términos. (Esto debería quedar claro al observar la diferencia entre el primero y el último de cada millar. Esta diferencia en todos menos el $6000$ 's es $994$ pero en el $6000$ la diferencia es $987$ .)

Por lo tanto, la suma de todos los dígitos de millar es $(143 \times 45) - 6 = 6429.$

Realiza un análisis similar para las otras tres cifras. Cada uno tiene un patrón.

Answer 2

Hay 9 números decimales de 1 dígito. Dividirlos en su residuo módulo 7 y se obtiene:

$$(0,\{7\}), (1,\{1,8\}), (2,\{2,9\}), (3,\{3\}), (4,\{4\}), (5,\{5\}), (6,\{6\})$$

Podemos extenderlo a los números de 2 cifras. Primero multiplicamos todos los números de 1 dígito por 10, lo que tiene el efecto de barajar todos los residuos, pero de una manera fija: 0 va a 0, y $n \neq 0$ va a $3n \mod 7$ . Así, todos los múltiplos de 2 cifras de 10 se pueden paeticionar de esta manera:

$$(0, \{70\}), (3,\{10,80\}), (6,\{20,90\}), (2,\{30\}), (5, \{40\}), (1,\{50\}), (4,\{60\})$$

Hay 10 cifras decimales. Se pueden dividir por residuo módulo 7 así:

$$(0,\{0,7\}), (1,\{1,8\}), (2,\{2,9\}), (3,\{3\}), (4,\{4\}), (5,\{5\}), (6,\{6\})$$

Ahora podemos hacer una especie de producto cartesiano entre estas dos particiones para calcular la partición de todos los números de 2 cifras por residuo. Aquí está la entrada residuo-0 de esa partición:

$$(0,\{70,77,14,84,21,91,35,42,49,56,63\})$$

Se creó combinando el $(0,\{70\})$ entrada con el $(0,\{0,7\})$ entrada, el $(3,\{10,80\})$ entrada con el $(4,\{4\})$ etc. Usted puede ver que esto va a ser muy verboso.

Al final sólo nos interesan las sumas de dígitos, por lo que no necesitamos llevar la cuenta de cada número de cada clase de residuo. Sólo necesitamos llevar la cuenta del tamaño del conjunto y de la suma de dígitos.

Al combinar dos entradas de partición, con residuo, recuentos y sumas $(r_1,c_1,s_1)$ y $(r_2,c_2,s_2)$ su entrada combinada será $(r_1r_2 \mod 7, c_1c_2, c_1s_2 + c_2s_1)$ .

Por ejemplo, considere la posibilidad de combinar $(3,\{10,80\})$ y $(2,\{2,9\})$ . Sus versiones convertidas son $(3,2,9)$ y $(2,2,11)$ . Combinándolos se obtiene $(5,4,40)$ . Hacerlo por el camino largo da como resultado $(t,\{12,19,82,89\})$ que también tiene 4 entradas y suma de dígitos 40.

Por lo tanto, empezar de nuevo con las versiones abreviadas de los conjuntos.

9 Números decimales de 1 dígito:

$$(0,1,7), (1,2,9), (2,2,11), (3,1,3), (4,1,4), (5,1,5), (6,1,6)$$

Multiplícalos por 10, lo que no cambia la suma de dígitos.

$$(0,1,7), (3,2,9), (6,2,11), (2,1,3), (5,1,4), (1,1,5), (4,1,6)$$

10 dígitos decimales:

$$(0,2,7),(1,2,9),(2,2,11),(3,1,3),(4,1,4),(5,1,5),(6,1,6)$$

Después de un molesto, pero factible cantidad de trabajo se puede obtener los números de 2 dígitos:

$$(0,13,125),(1,13,129),(2,12,114),(3,13,118),(4,13,122),(5,13,126),(6,13,121)$$

Los números de 3 cifras:

$$(0,128,1792),(1,128,1794),(2,129,1806),(3,129,1809),(4,129,1803),(5,129,1806),(6,128,1790)$$

Y los números de 4 cifras:

$$(0,1286,23792),(1,1286,23791),(2,1286,23790),(3,1286,23798),(4,1285,23778),(5,1285,23767),(6,1286,23784)$$

Mirando la entrada para el residuo 0 sabemos que hay 1286 números de 4 dígitos divisibles por 7, y su suma de dígitos es 23792.

Answer 3

Programáticamente, esto se puede resolver de la siguiente manera:

long sum = 0;

for (int i = 1000; i < 9999; i++)
    if (i % 7 == 0) {
        print(" "+i);
        sum+=i;
    }

lo que da el siguiente resultado: 7071071

donde % se supone que significa $modulo$

---

Edición: Lo siento, tienes razón @John

Para un problema dado, este es un cálculo correcto:

long sum = 0;

for (int n = 1000; n <= 9999; n++)
    if (n % 7 == 0)
        sum += digitSum(n);

la recursiva digitSum método:

static int digitSum(int n) {
    if (n == 0)
        return 0;
    return n%10 + digitSum(n/10);
}

el resultado es: 23792