Por ejemplo entre 1 y 99 esta suma da 1188.
Si lo quieres compartir o guardar
martes, 17 de abril de 2012
909 - Vuelven los castigos
La tarea para mañana es encontrar la suma de todos los números comprendidos entre 1 y 999999 que tienen al menos un siete.
Por ejemplo entre 1 y 99 esta suma da 1188.
Por ejemplo entre 1 y 99 esta suma da 1188.
Suscribirse a:
Enviar comentarios (Atom)
Entradas
250681749318 ?
ResponderEliminarCorrecto! Me gustaría saber como lo resolviste ¿Fuerza bruta o por deducción?
EliminarFuerza bruta en javascript y tarda menos de 1 segundo.
Eliminarvar suma = 0;
for (var i=0; i<999999; i++){
var s = new String(i);
if (s.indexOf('7')!=-1) suma+=i;
}
alert(suma);
La fórmula general para la suma de los números de D dígitos que incluyen el N es:
ResponderEliminar(5*(10^(D-1)-9^(D-1))+9^(D-2)*N)*(10^D-1)
En el problema D=6 y N=7. Sustituyendo de obtiene el resultado de Anónimo.
Espectacular. ¿Tendrías por ahí la demostración o el desarrollo matemático para llegar a esa fórmula..?
EliminarEs más fácil hacerlo que explicarlo. Primero calculo cuanto suman los números que contienen el 0, y después cuánto tengo que sumar para sustituir los 0 por N y cuánto tengo que restar para sustituir los N por 0.
ResponderEliminarPara calcular los números que contienen el 0 calculo cuánto suman todos los números y le resto la suma de los que no contienen el 0. La suma de todos los números es 45*10^(D-1)*(10^D-1)/9. Se obtiene sumando los dígitos que están en la primera posición ((0+1+2+3+4+5+6+7+8+9)*10^(D-1)*10^(D-1), que es la suma de los 10 dígitos por la cantidad total que hay por su valor posicional), los que están en la segunda ((0+1+2+3+4+5+6+7+8+9)*10^(D-1)*10^(D-2)), los que están en la tercera ((0+1+2+3+4+5+6+7+8+9)*10^(D-1)*10^(D-3)) y así hasta la última ((0+1+2+3+4+5+6+7+8+9)*10^(D-1)*10^(D-D)). La suma es 45*10^(D-1)*111…111 = 5*10^(D-1)*999…999 = 5*10^(D-1)*(10^D-1).
Los números que no contienen el 0 se calculan de forma análoga, con la salvedad de que los dígitos son (1+2+3+4+5+6+7+8+9), la cantidad total es 9^(D-1) y el valor posicional no varía, sigue siendo 10^(D-1), 10^(D-2), 10^(D-3), hasta 10^(D-D). La suma es 45*9^(D-1)*111…111 = 5*9^(D-1)*999…999 = 5*9^(D-1)*(10^D-1).
Por tanto la suma de los números que contienen el 0 es 5*10^(D-1)*(10^D-1)- 5*9^(D-1)*(10^D-1) = 5*(10^(D-1)-9^(D-1))*(10^D-1).
Para hallar la suma de los números que contienen N sustituyo 0 por N en todos los números que contienen el 0, y también sustituyo N por 0 en esos números.
Hay 10^(D-1) números que contienen el 0 en la primera posición, el mismo número que en la segunda o en cualquier otra. Algunos números los tomo varias veces, los que tienen varios 0, pero no me importa porque solo quiero saber cuanto aportan a la suma los N que los sustituyen. Los 10^(D-1) de la primera posición aportan 10^(D-1)*N cada uno, luego en total aportan 10^(D-1)*10^(D-1)*N. Los de la segunda posición aportan 10^(D-1)*10^(D-2)*N, los de la tercera 10^(D-1)*10^(D-3)*N y así hasta los de la última que aportan 10^(D-1)*10^(D-D)*N. En total suman 10^(D-1)*111…111*N = 10^(D-1)*(10^D-1)/9*N.
Ahora hay que restar lo que aportaban los N que sustituyo por 0. La cantidad de números que tienen N como primer dígito y 0 en algún otro es 10^(D-1)-9^(D-1), pues hay 10^(D-1) de la forma NXXX…XXX en total y de ellos 9^(D-1) no contienen el 0. Por tanto los que tenían N como primer dígito aportaban (10^(D-1)-9^(D-1))*10^(D-1)*N, los que lo tenían como segundo dígito (10^(D-1)-9^(D-1))*10^(D-2)*N, y así hasta los que lo tenían como último que aportaban (10^(D-1)-9^(D-1))*10^(D-D)*N. De nuevo cuento varias veces los que tenían N repetido, pues solo resto el valor posicional del dígito y no tengo en cuenta los demás. El valor total a restar es (10^(D-1)-9^(D-1))*111…111*N = (10^(D-1)-9^(D-1))*999…999/9*N = (10^(D-1)-9^(D-1))*(10^D-1)/9*N.
El total es 5*(10^(D-1)-9^(D-1))*(10^D-1) + 10^(D-1)*(10^D-1)/9*N - (10^(D-1)-9^(D-1))*(10^D-1)/9*N. Sacando factor común 10^D-1 y operando se llega a la fórmula (5*(10^(D-1)-9^(D-1))+9^(D-2)*N)*(10^D-1).
Perdón por el ladrillo, pero no lo sé decir más corto. De hecho me resultó más fácil hallar la fórmula que explicarla.