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.
Si lo quieres compartir o guardar
Share/Bookmark

6 comentarios:

  1. Respuestas
    1. Correcto! Me gustaría saber como lo resolviste ¿Fuerza bruta o por deducción?

      Eliminar
    2. Fuerza bruta en javascript y tarda menos de 1 segundo.

      var suma = 0;
      for (var i=0; i<999999; i++){
      var s = new String(i);
      if (s.indexOf('7')!=-1) suma+=i;
      }
      alert(suma);

      Eliminar
  2. La fórmula general para la suma de los números de D dígitos que incluyen el N es:

    (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.

    ResponderEliminar
    Respuestas
    1. Espectacular. ¿Tendrías por ahí la demostración o el desarrollo matemático para llegar a esa fórmula..?

      Eliminar
  3. Es 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.

    Para 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.

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!