Cuántos números son menos de un millón tales que la suma de sus dígitos es $\le 19$?

Question

Cuántos números son menos de un millón tales que la suma de sus dígitos es $\le 19$?

Esta pregunta es la Generación de las Funciones del ejercicio.

La solución de los reclamos, la respuesta es el coeficiente de $x^{19}$ en la:

$$ \left( 1 + x + x^2 + ... + x^9 \right)^6 \left(\frac{1}{1-x}\right) $$

El término izquierda es obvio, pero ¿por qué multiplicar por $\frac{1}{1-x}$?

En general, si $F(x)$ genera $a_n$ $\frac{F(x)}{1-x}$ genera $\sum\limits_{k=0}^n a_k$, pero no veo es que el ajuste aquí.

Answer 1

Esto ya ha sido insinuado en un comentario, pero si $$F(x) = (1 + x^2 + x^3 + x^4 + x^5 +x ^6 + x^7 + x^8 + x^9)^6,$$ a continuación, el coeficiente de $x^{19}$ $F(x)$ es el número de enteros no negativos a menos de $10^6$ para que la suma de los dígitos de la parte entera de la decimal representación es exactamente $19.$

Pero desea que la suma de los dígitos a ser en la mayoría de las $19,$ , por lo que usted desea la suma de los coeficientes de los veinte primeros términos de $F(x)$ (es decir, que el exponente de a $x$ rangos de$0$$19$), que como ya saben es el coeficiente de $x^{19}$ en el serie representación de $\dfrac{F(x)}{1 - x}.$

Answer 2

Escribí algo de código en java para la fuerza bruta de este problema, y tengo la respuesta 147,070. Voy a poner el código de abajo.

(NOTA: Ahora me di cuenta de que esto no es exactamente la respuesta a su pregunta, pero voy a dejarlo en caso de que sea útil para alguien en algún punto en el tiempo.)

public class million {
   public static void main(String args[]) {
       int x = 0;
       int counter = 0;

       while (x < 1000000) {
           int test = x;
           int sum = 0;

           while (test > 0) {
                sum += test % 10;
                test = test / 10;
            }

           if (sum <= 19) {
               counter += 1;
           }    

       x += 1;
       }

       System.out.println(counter);
   }
}