Rincón Matemático

Matemática => Matemática Aplicada => Mensaje iniciado por: jacks en 20 Enero, 2012, 02:32 pm

Título: Sum of digits
Publicado por: jacks en 20 Enero, 2012, 02:32 pm
Let \( S = \left\{20,21,22,23,.....210\right\} \). Consider all positive differences of elements of \( S \).

If \( M \) is the Sum of all these differences, find the Sum of the digits of \( M \)
Título: Re: Sum of digits
Publicado por: filomates en 20 Enero, 2012, 08:04 pm
La suma de los dígitos de M da 18
Por otra parte M=1137150.
Si he acertado, expondré el razonamiento. En caso contrario, seguiré pensando.
Adelanto que la idea principal es que las diferencias positivas entre todos los números son sucesiones finitas {1,2,3,...,190},
{1,2,3,..., 189}, ....{1,2,3}, {1,2}, {1}.
En total hay 190 de tales sucesiones cada vez más cortas.
Si sumamos todas ordenadamente, vemos que el 1 aparece 190 veces, el 2 aparece 189 veces, ...., el 190 aparece 1 vez
y que la suma es \(  \displaystyle\sum_{k=1}^{190}{k(190-k)}  \)
Esta suma puede hacerse aplicando las propiedades de los símbolos sumatorios y las formulas de la suma de los n primeros números naturales y la delos n primeros cuadrados de los números naturales.
¿Me equivoqué o acerté? En caso de error,¿en los cálculos o en el planteamiento?
Bueno, espero respuesta.
Saludos.
Título: Re: Sum of digits
Publicado por: jacks en 20 Enero, 2012, 08:49 pm
Thanks filomates for Nice answer

but original question is

Let \( S = \left\{2^0,2^1,2^2,2^3,.....2^{10}\right\} \). Consider all positive differences of elements of \( S \).

If \( M \) is the Sum of all these differences, find the Sum of the digits of \( M \)
Título: Re: Sum of digits
Publicado por: filomates en 21 Enero, 2012, 12:51 am
Bueno, parece que una confusión creó otro problema diferente del original, pero también interesante.
Gracias jacks, por corregir la confusión .
Ahora me centro en el problema "auténtico"
Bien, creo que el problema se resuelve de la misma manera.
Razonando de igual manera que en la entrada anterior, se llega a que la suma de las diferencias que nos piden es \(  \displaystyle\sum_{k=1}^{10}{k\cdot 2^k}  \)
Ahora la dificultad está en encontrar una fórmula para esa suma. Esa fórmula existe y aunque no la he deducido, si que la he encontrado en un libro y es \(  \displaystyle\sum_{k=1}^{n}{k\cdot 2^k}=2(2^n\cdot n-2^n+1)  \).
Aplicando esa fórmula para n=10 llegamos a M=18434. La suma de las cifras de M es 20.

¿Es correcto el resultado? ¿Es correcto el razonamiento?
Además me pregunto: ¿Existirá algún procedimiento para resolver este problema que nos de la suma de las cifras de M sin necesidad de encontrar previamente M?
Saludos y hasta la próxima
Título: Re: Sum of digits
Publicado por: pierrot en 21 Enero, 2012, 03:26 am
Hello jacks, filomates

Ahora la dificultad está en encontrar una fórmula para esa suma. Esa fórmula existe y aunque no la he deducido, si que la he encontrado en un libro y es \(  \displaystyle\sum_{k=1}^{n}{k\cdot 2^k}=2(2^n\cdot n-2^n+1)  \).

One way to deduce this formula is defining \( \displaystyle a_n=\sum_{k=1}^n k\cdot 2^k \). Then:

\( \left\{\begin{align*} a_1&=2 \\a_{n+1}&=a_n+(n+1)\cdot 2^{n+1}\end{align*}\right. \)


From this equations we can find an explicit formula for \( a_n \) using the theory of linear recurrence relations.

Greetings from Uruguay
Título: Re: Sum of digits
Publicado por: jacks en 21 Enero, 2012, 05:03 pm
Thanks Pablon and filomates
Título: Re: Sum of digits
Publicado por: filomates en 13 Marzo, 2022, 01:10 am
Se que es raro contestar a un mensaje de hace 10 años, pero me he topado con este problema, lo he vuelto a resolver y he encontrado algunas cosas que hay que corregir

Hello jacks, filomates

Ahora la dificultad está en encontrar una fórmula para esa suma. Esa fórmula existe y aunque no la he deducido, si que la he encontrado en un libro y es \(  \displaystyle\sum_{k=1}^{n}{k\cdot 2^k}=2(2^n\cdot n-2^n+1)  \).

One way to deduce this formula is defining \( \displaystyle a_n=\sum_{k=1}^n k\cdot 2^k \). Then:

\( \left\{\begin{align*} a_1&=2 \\a_{n+1}&=a_n+(n+1)\cdot 2^{n+1}\end{align*}\right. \)


From this equations we can find an explicit formula for \( a_n \) using the theory of linear recurrence relations.

Greetings from Uruguay
Me voy a dedicar primero a deducir la fórmula para \(     \displaystyle\sum_{k=1}^n{k2^k}     \)
Spoiler
  Considero un valor de k fijo y la diferencia \(  (k+1)2^{k+1} -k2^k   \) y vamos a desrrollarla
\(   (k+1)2^{k+1} - k2^k = 2^k (2(k+1)-k)=2^k (k+2)    \)
Ahora sumamos todas esas igualdades desde k=1 hasta k=n
\( \displaystyle\sum_{k=1}^n{ (k+1)2^{k+1} - k2^k} = \displaystyle\sum_{k=1}^n{2^k (k+2)} \)
El primer miembro de la igualdad es una suma telescópica, de manera que queda \(  (n+1)2^{n+1}-2    \), mientras que el segundo miembro lo podemos expresar como \(   \displaystyle\sum_{k=1}^n{k2^k}+2\displaystyle\sum_{k=1}^n{2^k}   \)
Sabemos además que \(   \displaystyle\sum_{k=1}^n{2^k} = 2^{n+1} -2  \)
Hemos llegado a que \(  (n+1)2^{n+1} - 2 = \displaystyle\sum_{k=1}^n{k2^k} +2(2^{n+1}-2)   \)
De ahí podems despejar, simplificar y llegar a \(   \displaystyle\sum_{k=1}^n{k2^k} =(n-1)2^{n+1}+2  \), que es la fórmula que manejaba en entradas antriores de este hilo
 
[cerrar]
En una próxima entrada/respuesta pretendo resolver los dos problemas que se plantean en el mismo. A ver si ahora doy la respuesta correcta, que me parece que la que di en su momento, aunque nadie intervino para aclarar, no es la correcta.
Por supuesto, si alguien "se motiva" es bienvenido a poner su solución, faltaría más
Título: Re: Sum of digits
Publicado por: Richard R Richard en 13 Marzo, 2022, 01:28 pm
Otra forma de calcular M es


\( M=\displaystyle\sum\limits_{i=0}^n(2i-n)2^i \)


Pero no te libras de resolver \( i2^i \) que vuelve a aparecer.


Si existe una  forma de calcular la suma de los dígitos me imagino debe provenir desde la perspectiva de  hacer esto en binarios, números de base 2.
Título: Re: Sum of digits
Publicado por: Juan Pablo Sancho en 13 Marzo, 2022, 04:25 pm
Para sacar el sumatorio en general:
\( P = 1 \cdot k + 2 \cdot k^2 + 3 \cdot k^3 \cdots +  n \cdot k^n  \)
\( kP = k^2 + 2 \cdot k^3 + 3 \cdot k^4 + \cdots + n \cdot k^{n+1}  \)
Restamos:
\( P-kP = k + k^2 + k^3 + \cdots + k^n - n \cdot k^{n+1}  \)
\( P-kP = \dfrac{k-k^{n+1}}{1-k} - n \cdot k^{n+1}  \)
Si \(  k\neq 1 \) en nuestro caso \( k=2 \).
\( P = \dfrac{k-k^{n+1}}{(1-k)^2} - n \cdot \dfrac{k^{n+1}}{1-k}  \)
Título: Re: Sum of digits
Publicado por: Richard R Richard en 13 Marzo, 2022, 08:26 pm
 Aplicando lo antedicho por Juan Pablo
Obtengo \( M=4+n+2^{n+1}(n-2) \) 

solo se me ocurre hacer que

\( 4=2^2 \)\( n=10=2^3+2 \)
entonces para el caso particular \( n=10 \)
\( M=2^2+2^3+2+2^{n+1}(2^3+2-2)=2^2+2^3+2^1+2^{n+4}=2^2+2^3+2^1+2^{14}= \)
quizá exista una forma mas fácil que  desconozco para \( n \) arbitrario

en binario es fácil ver que \( M=10000000001110 \)
pero no veo forma de evitar calcular M en decimal para sumar sus cifras, \( M=2+4+8+16384=16398 \)
luego la suma de sus dígitos es \( \mathbf{27} \) Oopps!!! corregido.
 
Spoiler
para verificar empíricamente en \( n=3 \)
 con valores 1,2,4,8  las diferencias son \( 7+6+4+2+3+1=23 \)

y

\( M(3)=4+n+2^{n+1}(n-2)=4+3+2^{3+1}(3-2)=7+16=23 \)


verifica y la suma de sus dígitos es 5.
[cerrar]
Saludos
Título: Re: Sum of digits
Publicado por: filomates en 14 Marzo, 2022, 04:19 am
La fórmula \(  M=n+4+(n-2)2^{n+1}  \) es correcta, me parece, pero hay que explicar de dónde viene.
Por lo demás los resultados coinciden con lo que me sale. La suma de las cifras de M sale 27.
Aparte de esto, el reto está en encontrar una manera de hallar las suma de las cifras de M sin saber M, si es que es posible
Título: Re: Sum of digits
Publicado por: Richard R Richard en 14 Marzo, 2022, 11:05 am


Cada termino de la suma de M es \( 2^i-2^j \)  si desarrollas


\( M=\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=0}^{i-1}2^i-2^j \)

Si haces factor común verás que \( 2^n \) aparece \( n \) veces sumando  y ninguna restando, \( 2^{n-1} \) aparece \( n-1 \) veces sumando y una vez restando por lo que operando sumará solo \( n-2 \) veces...
\( 2^0 \) resta las n veces.

Entonces \( (2i-n) \) representa el resultado de calcular el factor común \( 2^i \) al desarrollar los sumatorios

Rearmando un nuevo sumatorio queda

\( M=\displaystyle\sum\limits_{i=0}^n(2i-n)2^i \)


Luego se aplica lo juan pablo indica




\( M=\displaystyle\sum\limits_{i=0}^n(2i-n)2^i=2\left[\dfrac{2-2^{n+1}}{(1-2)^2} - n \cdot \dfrac{2^{n+1}}{1-2}\right]-n\displaystyle \sum\limits_0^n 2^i \)




luego recordar que


cuando \( k=2 \)este termino queda


\(  \displaystyle \sum\limits_0^n 2^i=2^{n+1}-1 \)


luego reemplazamos y el resto es operar



\( M=2\left[2-2^{n+1} + n 2^{n+1}\right]-n2^{n+1}+n \)



\( M=4+n+2^{n+1} (-2+ 2n -n) \)

\( M=n+4+(n-2)2^{n+1}  \)


Saludos
Título: Re: Sum of digits
Publicado por: Masacroso en 14 Marzo, 2022, 04:36 pm
EJERCICIO ALTERNATIVO
Lo que está en este spoiler se debe a que había asumido que \( S=\{20,\ldots ,210\} \), luego he visto el tercer mensaje del hilo mostrando que era un error de transcripción.

La suma de las diferencias positivas viene dada por la expresión \( \sum_{20\leqslant j<k\leqslant 210}(k-j) \). Con algo de álgebra y cálculo finito obtenemos

\( \displaystyle{
\begin{align*}
\sum_{20\leqslant j<k\leqslant 210}(k-j)&=\sum_{20\leqslant j\leqslant k\leqslant 210}(k-j)\\
&=\sum_{k=20}^{210}\sum_{j=20}^{k}(k-j)\\
&=\sum_{k=20}^{210}\left(k(k-19)-\tfrac1{2}(k+1)^{\underline{2}}+190\right)\\
&=\sum_{k=20}^{210}(k^{\underline{2}}-18k-\tfrac1{2}(k+1)^{\underline{2}}+190)\\
&=\left[\frac{k^{\underline{3}}}{3}-9k^{\underline{2}}-\frac{(k+1)^{\underline{3}}}{6}+190\right]_{20}^{211}\\
&=\frac1{6}\left[ k^{\underline{2}}(k-59)\right]_{20}^{211}+191^{\underline{2}}\\
&=1161280
\end{align*}
} \)

donde \( a^{\underline{k}} \) es un factorial descendente y donde el último paso lo he hecho con una calculadora. Por tanto la suma de los dígitos sería \( 19 \) (la cuenta anterior también la he comprobado con el Wolfram y me da lo mismo).

Igualmente la expresión "la suma de todas las diferencias positivas" es un poco vaga, quizá no se corresponda con la suma anterior sino con "la suma de todas las diferencias positivas distintas", entonces la suma inicial sería \( \sum_{k=1}^{190}k=191\cdot 95=18145 \) por lo que el resultado final sería entonces \( 19 \) (curiosamente da el mismo resultado, no sé si será una coincidencia o hay algo más profundo ahí a considerar).

Añado: bueno, el primer cálculo se puede simplificar mucho si hacemos el cambio de variable \( k-j=r \), entonces tenemos que

\( \displaystyle{
20\leqslant j\leqslant k\leqslant 210\iff 0\leqslant r\leqslant 210-j\,\land\, 20\leqslant j\leqslant 210\\
\therefore\quad \sum_{20\leqslant j<k\leqslant 210}(k-j)=\sum_{j=20}^{210}\sum_{r=0}^{210-j}r=\frac1{2}\sum_{j=20}^{210}(211-j)^{\underline{2}}=\frac1{2}\sum_{s=1}^{191}s^{\underline{2}}=\frac1{6}192^{\underline{3}}=64\cdot 95\cdot 191=1161280
} \)
[cerrar]

Ups, no había observado que el problema original estaba mal transcrito y que \( S=\{2^k: k\in\{0,\ldots ,10\}\} \), en ese caso la suma sería

\( \displaystyle{
\begin{align*}
\sum_{0\leqslant j<k\leqslant 10}(2^k-2^j)&=\sum_{0\leqslant j\leqslant k\leqslant 10}(2^k-2^j)\\
&=\sum_{j=0}^{10}\sum_{r=0}^{10-j}2^j(2^r-1)\\
&=\sum_{j=0}^{10}2^j\left(2^{11-j}-1-11+j\right)\\
&=\sum_{j=0}^{10}(2^{11}-12\cdot 2^j+j2^j)\\
&=11\cdot 2^{11}-12\cdot 2^{11}+12+\left(j2^j-\sum 2^{j+1}\delta j\right)_{0}^{11}\\
&=-2^{11}+11\cdot 2^{11}-2\cdot 2^{11}+14\\
&=2^{14}+14\\
&=16398
\end{align*}
} \)

donde el último paso se hizo con una calculadora. Si se consideran los dígitos en binario entonces la suma sería \( 4 \). En cifras decimales sería \( 27 \).