| 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 2 + … + x b − 1 ) ( 1 + x + x 2 + … + x b − 1 ) k − 1
El coeficiente de x N es la solución buscada.
( 1 − x b ) k − 1
( x + x 2 + … + 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 )
0
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.
∎
🔗
| 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 2 + … + x b − 1 ) ( 1 + x + x 2 + … + x b − 1 ) k − 1
The x N coefficient is the solution searched for.
( 1 − x b ) k − 1
( x + x 2 + … + 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 )
0
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.
∎
🔗
Congratulations @j2e2xae! You have completed the following achievement on the Hive blockchain And have been rewarded with New badge(s)
Your next target is to reach 200 replies.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPCheck out our last posts: