Español

English

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,

( x + x² + … + x ^b − 1 ) ( 1 + x + x ² + … + x ^b − 1 ) ^k − 1

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

                                          (  1  −  x  ^b ) ^k − 1
(  x  +  x² + … +  x ^b − 1 )  ―――――――――
                                            (  1  −  x   ) ^k − 1

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,

suma_dados ( b, k, N ) = suma_cifras ( b, k, N − k )

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.

b
suma_dígitos ( b, k, N )  =      ∑      suma_dados ( b, k − 1, N + k − m )
m = 2

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,

0 1 0 0 0 0 0 ...
k = 1 0 1 1 0 0 0 0 ...
k = 2 0 1 2 2 1 0 0 ...
k = 3 0 1 3 5 5 3 1 ...

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 ,

_{b − 1}
D ( b , k , N ) = ∑ D ( b , k − 1, N − i )
⁰

D ( b , k , 1 ) = 1
D ( b , k , N ) = 0 , N > ( b − 1 ) ∙ k
D ( b , k , N ) = 0 , N < 1
D ( b , k , N ) = D ( b , k , ( b − 1 ) ∙ k + 1 − N )

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

∎

🔗

suma de dados

Media

English

Español

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

In this expression,

( x + x² + … + x ^b − 1 ) ( 1 + x + x ² + … + x ^b − 1 ) ^k − 1

The x ^N coefficient is the solution searched for.

                                          (  1  −  x  ^b ) ^k − 1
(  x  +  x² + … +  x ^b − 1 )  ―――――――――
                                            (  1  −  x   ) ^k − 1

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,

dice_sum ( b, k, N ) = figures_sum ( b, k, N − k )

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.

b
digit_sum ( b, k, N )  =      ∑      dice_sum ( b, k − 1, N + k − m )
m = 2

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.

0 1 0 0 0 0 0 ...
k = 1 0 1 1 0 0 0 0 ...
k = 2 0 1 2 2 1 0 0 ...
k = 3 0 1 3 5 5 3 1 ...

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 ,

_{b − 1}
D ( b , k , N ) = ∑ D ( b , k − 1, N − i )
⁰

D ( b , k , 1 ) = 1
D ( b , k , N ) = 0 , N > ( b − 1 ) ∙ k
D ( b , k , N ) = 0 , N < 1
D ( b , k , N ) = D ( b , k , ( b − 1 ) ∙ k + 1 − N )

These equations allow us to build up a recursive solution.

∎

🔗

dice sum

Media

Follow, be first to know