Suma de dígitos. Digit  sum.                                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

---

Sea el conjunto formado por los números en base b de k dígitos.
Determinar la cardinalidad del subconjunto formado por los números cuya suma de dígitos es igual a un entero positivo N .

 

   En la siguiente expresión,

El coeficiente de x ^N es la solución buscada.

Podemos determinar el valor de la solución como la suma de los coeficientes de  { x  ^N − 1 …  x  ^{N −  b  + 1} }  en la expansión del segundo factor.

Este problema lo resolvimos en otra ocasión,  suma de dados , en ese caso la base b era 6, generalizando el problema a una base arbitraria, podemos deducir,

donde suma_cifras ( b, k, N ) representa la suma de dígitos, si permitimos que el dígito más significativo asuma el valor 0.

El problema se reduce a calcular ( b − 1 ) sumas de dados.

 

   Por otro lado, podemos construir, para una base dada, una suerte de triángulo aritmético, filas ordenadas según el valor de k   y columnas por N .
A modo de ejemplo, tomando números en base 3,

Podemos determinar el valor, de cada uno de los elementos, como la suma de los tres valores en la fila inmediatamente anterior por encima y a la izquierda del valor deseado.

Definiendo D ( b , k , N  ) como la solución al problema de la suma de dígitos en base b de k dígitos con suma N ,

Obtenemos unas ecuaciones que permiten construir una solución recursiva del problema.

 

∎

 

 suma de dados 

---

Media Opensofias, CC0, via Wikimedia Commons

---

---

Consider the set of base b numbers of k digits, calculate cardinality of its subset with digit sum upto N .

 

   In this expression,

The x ^N coefficient is the solution searched for.

The sum of the coefficients  { x  ^N − 1 …  x  ^{N −  b  + 1} } , in the expansion of second factor , gives the solution's value.

We already solved this problem,  dice sum , base b was 6. Working this problem on an arbitrary base we deduce,

where figures_sum ( b, k, N ) is defined as the digit sum, zero allowed at the most significant digit

Hence problem is reduced to ( b − 1 ) dice sums.

 

   In the other hand, given a base we can build an arithmetic triangle, rows indexed by k   and columns by N . As an example, take base 3.

Value of any element can be calculated as the sum of the three values up and to the left of its own position.

Denoting D ( b , k , N  ) as the value of solution to the digit sum problem, on number base b of k digits that sum upto N ,

These equations allow us to build up a recursive solution.

 

∎

 

 dice sum 

---

Media Opensofias, CC0, via Wikimedia Commons