"Tendencia" de los dígitos del factorial

Hay nuevos comentarios sin leer

Vamos con el problema de la semana:

Demostrar que la suma de los dígitos de $n!$ (factorial de $n$ ) tiende a infinito, si $n$ tiende a infinito.

Posts aleatorios

Autor: ^DiAmOnD^ | Publicado el 4 de November de 2008
Categorías: Juegos | Imprime este post

Sin comentarios

Trackback | 4 Nov, 2008

Bitacoras.com
Manuel | 4 de November de 2008 | 11:29

Vale… ¿en qué base?

Supongo que en todas. Pero no me gustan nada los problemas que aluden a la representación de los números. Tienden a hacerse molestamente dependientes de la base de numeración.
Xavi | 4 de November de 2008 | 13:47

Hombre, atendamos a que n! tiene a lo sumo:

1+n(1/5+1/25+…+1/(5^[log{5}n]) ceros. Luego suponiendo que el resto de cifras tiene por valor 1.

Se trata de calcular el limite de
[log{10}n]-n(1/5+1/25+…+1/(5^[log{5}n])

y observar que tiende a infinito.

Me limito tan solo a dar la idea, pues no se escribir formulas y no quiero que quede una chapuza. Espero que mi post no sea molesto.
Antonio | 4 de November de 2008 | 14:23

Xavi, ese sería el numero de ceros consecutivos que n! tiene *al final*. Pero es posible que haya más ceros intercalados a la izquierda (por ejemplo, 8!=40320, 12!=479001600) así que en principio no podemos suponer que el resto de las cifras son 1.
Lek | 4 de November de 2008 | 14:27

Yo diría que puesto que $n! >= n$ , cuando $n$ tiende a infinito por fuerza $n!$ tiene que ser mayor
Manuel | 4 de November de 2008 | 16:05

Sigo con el problema de fijar la base de numeración. Supongamos que tenemos una base $b$ tal que $b=\prod_{p_{i} \leq n}p_{i}$ , donde los $p_{i}$ son primos.

Entonces necesitaremos $b$ símbolos para representar cualquier número, pero $n!$ tendría una representación tal, que habría un montón de 0′s.

Yo creo que en ese caso la suma de dígitos no tendría por qué tender a infinto, pero aún no he encontrado la demostración.
Alvaro | 4 de November de 2008 | 16:55

Hola a todos,

se me ha ocurrido pensar que $n!$ es múltiplo de tres. La suma de las cifras de todos los múltiplos de 3 debe ser también múltiplo de 3. ¿No hay manera de usar esta propiedad?
hernan | 4 de November de 2008 | 19:33

Como para ayudar(nos) a pensar: es válida la propiedad sin tomar el factorial ?

Es decir, ¿es verdad que “Cuando n tiene a infinito la suma de sus dígitos tiende a infinito” ?
hernan | 4 de November de 2008 | 20:00

La respuesta a la pregunta de mi comentario anterior (no seguir leyendo si prefieren pensarlo antes) es que la propiedad sólo es verdadera si se interpreta lo de “tender a infinito” para una secuencia en un sentido laxo/impropio, como sinónimo de “no estar acotada”: es obvio que la suma de los dígitos de n no está acotada cuando n tiende a infinito.
Pero en el sentido “técnico”, restringido, matemáticamente riguroso, una secuencia tiende a infinito cuando se mantiene por encima de cualquier dado M a partir de algún N. En este sentido, la propiedad es obviamente falsa, porque, por ejemplo, al pasar n de 99999..99999 a 1000…0000 la secuencia ‘suma de digitos’ cae a 1.
Asumo que la pregunta original, para n!, se refiere a este sentido riguroso de tender a infinito. Aunque la verdad es que ni siquiera en el sentido impropio me resulta fácil ver cómo demostrar que es verdadera (las sugerencias de Alvaro y Lek no sirven para demostrar ni siquiera esa versión débil).
Gulliver | 4 de November de 2008 | 20:01

En lugar de buscar la suma de los dígitos $S(x)$ , yo he atacado contando el número de dígitos que son diferentes de cero $N(x)$ . Al fin y al cabo $S(x)$ tiende a infinito si y solo si $N(x)$ tiende a infinito.

Fijaros que $\displaystyle{ S(x) / 9 <= N(x) <= S(x) <= 9 N(x)}$
Gulliver | 4 de November de 2008 | 20:11

Yo asumo también que el límite se entiende en sentido riguroso. Es decir que se pueden encontrar cotas arbitrariamente grandes de modo que todos los números de la sucesión $N(x)$ son mayores que esa cota a partir de un cierto punto.

En realidad estoy trabajando en suponer lo contrario y encontrar una contradicción. Es decir, estoy suponiendo que existe una cota $M$ de modo que se pueden encontrar $x$ arbitrariamente grandes con $N(x)$ que no supera la cota. $N(x) \le M$
Gulliver | 4 de November de 2008 | 20:15

En los comentarios anteriores me refería a $S(x!)$ y $M(x!)$
hernan | 4 de November de 2008 | 20:57

A ver por acá:

Supongamos que $n > 999$ .
Entonces $n!$ es múltiplo de 999. Entonces, por extensión del criterio de divisibilidad del 9, tomando los dígitos agrupados de a 3 (o sea, pensando en base 10^3), la suma de estos numeros de 3 digitos deberia ser un múltiplo de 999. O sea, por lo menos 999. Esto implica que hay al menos 3 digitos son distintos de cero (mmm está bien esto ? no estoy seguro)…
Gulliver | 4 de November de 2008 | 21:32

Sea $N(y)$ el número de dígitos no nulos en $y$ , supondré que el límite de $N(x!)$ no tiende a infinito.

De acuerdo con esta hipótesis, existe un entero $M$ y otro entero $\displaystyle{ x > 10^{M+1}}$ tal que $N(x!) \le M$ .

Voy a escribir la representación en base 10 de $x!$

$\displaystyle{ x! = d_0 10^{e_0} + d_1 10^{e_1} + \cdots + d_r 10^{e_r} }$

Los $d_i$ son dígitos enteros del 1 al 9. Los $e_i$ son exponentes enteros no negativos. Como mucho habrá $M$ de estos dígitos no nulos $r \le M$ .

$\displaystyle{ x \ge 10^{M+1}}$ , así que $\displaystyle{10^{M+1}-1}$ divide a $x!$

$\displaystyle{ 10^{M+1} \equiv 1, 10^e_i = 10^{s_i (M+1)} 10^{e^\prime_i} \equiv 10^{e^\prime_i} \pmod {10^{M+1}-1}}$ , con los $e^\prime_i$ enteros con $0 \le e^\prime_i \le M$ , así que reescribo $x!$ como

$\displaystyle{ x! \equiv 0 \equiv d_0 10^{e^\prime _0} + d_1 10^{e^\prime _1} + \cdots + d_r 10^{e^\prime _r} \pmod {10^{M+1}-1} }$ , $0 \le e^\prime_i \le M$ , $1 \le d_i \le 9$

$\displaystyle{ d_0 10^{e^\prime _0} + d_1 10^{e^\prime _1} + \cdots + d_r 10^{e^\prime _r} = 999\cdots999 t}$ , $M+1$ nueves multiplicado por un entero $t$ .

Se puede ver intuitivamente que no existen $d_i$ y $e^\prime_i$ que cumplan esta ecuación, con lo que llego a la contradicción que demostraría que $N(x!)$ si tiende a infinito. Lo que pasa es que no tengo perfectamente formalizada la demostración de que no hay soluciones de esa ecuación.

La intuición viene de que hay $M+1$ nueves en la parte derecha y solo $r < M+1$ digitos y exponentes en la parte derecha. Siempre queda algún nueve sin igualar si $d_i = 9$ y los exponentes son todos diferentes. Si uno intenta hacer que varios varios de los exponentes sean iguales, todavía será peor porque quedarán muchos nueves sin igualar. Probando con $M$ pequeños se ve enseguida
fede | 4 de November de 2008 | 21:51

Si se demuestra que, si s(n) es la suma de los digitos de n, s(a)+s(b)+… >= s(a+b+…),
resulta, creo, que la suma de los dígitos de un múltiplo de 9….9 (h nueves) es mayor o igual que 9h.
Gulliver | 4 de November de 2008 | 21:59

Parece que Hernan y yo hemos ido por el mismo camino, pero el lo explica de un modo más intuitivo.

La clave está en suponer que $\displaystyle{ x > 10^M}$ , con lo cual $\displaystyle{ 10^M-1}$ divide a $x!$ .

Después se agrupan los digitos de $x!$ en bloques de M dígitos y la suma de estos bloques es divisible por $\displaystyle{ 10^M-1}$ . Lo único que falta es demostrar formalmente que estas suposiciones implican que al menos hay $M$ dígitos no nulos.

Para el caso de tres cifras, M=3 es fácil.
hernan | 4 de November de 2008 | 22:01

Yo también caí (numéricamente) en la conjetura de fede, pero no sé cómo demostrarla ni estoy seguro de que sea cierta.
Claro es que de ser cierta el problema sale de inmediato.
fede | 4 de November de 2008 | 22:33

Hernán, si por ejemplo abc…z es la representación decimal de un múltiplo de 999, resulta que
abc + def + … = a’b'c’…h’ es multiplo de 999 y que
a’b'c + d’e'f’ + …. = a”b”c”… es múltiplo de 999, y así hasta que llegamos a un resultado de 3 digitos que será 999.
Supongamos a”b”c” = 999.
Usando s(a+b) <= s(a)+s(b) tenemos que 27=s(999) <= s(a’b'c’) + s(d’e'f’) +… =
s(a’b'c’…h’) <= s(abc) + s(def) + …. = s(abc…z).
M | 5 de November de 2008 | 00:09

Muy bien, hernan, gulliver, fede. Buena puntería!

Manuel, efectivamente, el problema estaba referido a base decimal.
M | 5 de November de 2008 | 00:20

Efectivamente la cosa estaba en notar que si un número es múltiplo de un $10^M-1$ entonces la suma de sus dígitos es mayor o igual que $M$ . Y de ahí que $s(x!)\geq \lfloor log x\rfloor$
Samy | 5 de November de 2008 | 11:03

Veamos, esto se ve divertido…. Así de primera mano se me ocurre lo siguiente…

Por demostar:

$S = \sum_{n=1}^{\infty}a_{n} \mbox{ diverge a } \infty$

$\mbox{ donde } a_{n}=\mbox{ suma de los digitos de n! }$

Veamos tenemos 3 posibilidades:

i) S diverge
ii) S converge condicionalmente
iii) S converge absolutamente

Resulta importante el entender que al tratarse de una suma de infinitos términos estamos hablando de un límite y no de una suma de términos común y corriente. En efecto

$S = \lim_{k \rightarrow \infty} \sum_{n=1}^{k}a_{n}$

(Un paréntisis: Esta última aclaración no tiene mucha importancia en mi argumento pero no está de más, porque, eso implica que por ejemplo, en el caso ii) la suma de los términos puede convergir a cualquier número real con un correcto reordenamiento de los términos, luego, cuando trabajamos con series infinitas hemos de tener cuidado al mover términos o agrupar)

Ok, en este caso dado que $a_{n}$ se define como suma de dígitos, sabemos que será siempre no negativo, y por ende ii) es equivalente a iii) (Repito, en este caso).

Observando las sumas parciales para $a_{n}$ , tenemos …
$\sum_{n=1}^{k}a_{n} = (1)+(2)+(6)+(2+4)+(1+2+0)+(7+2+0)+(5+0+4+0)+(4+0+3+2+0)+ \cdots +a_{k}$
Notaremos que $a_{n}=9p \mbox{ }\forall n \geq 9$ donde p es una constante natural distinta de 0 que depende del término $a_{n}$ . Esto se cumple porque desde 9! en adelante todos los n! son multiplos de 9, y por ende la suma de sus cifras también lo será.

Ahora, para que se cumplan ii) (y/o iii, pues ya los asumimos equivalentes) es condición necesaria, aunque no suficiente, que …

$\lim_{n \rightarrow \infty} a_{n} = 0$

Pero dado que ii) implica no-i) , también podemos decir que,

$\mbox{ Para que i) (Que la serie diverja) es suficiente que } \lim_{n \rightarrow \infty} a_{n} \neq 0$

Pero ya dijimos que para n lo suficientemente grande $a_{n}=9p$ por lo tanto ese límite nos queda…
$\lim_{n \rightarrow \infty} a_{n}= \lim_{n \rightarrow \infty} 9p = 9p \neq 0$

Vale decir “No importa cuan grande hagamos n, siempre la suma de las cifras de n! será un múltiplo de 9″

Luego, por ese simple critertio de divergencia, S diverge (Se cumple i) ). Y como además, todos sus términos son positivos, S diverge a $\infty$ , que es lo que queríamos demostrar.

Bueno, espero no tener errores, y si lo tengo, no me cabe duda que alguien podrá aclarármelos.

Saludos!
hernan | 5 de November de 2008 | 12:52

M: gracias, pero sin embargo no veo que hayamos logrado demostrar que “si un número es múltiplo de un $10^M-1$ entonces la suma de sus dígitos es mayor o igual que M”

Samy: está mal, no se trata de analizar el límite de la serie (suma de $a_n$ ) sino de la secuencia ( $a_n$ ).
Si de la serie se tratara, es trivial, no hace falta ver que son múltiplos de 9, basta con ver que $a_n \geq 1$ y ya está. También está mal escribir ese límite $\lim_{n \rightarrow \infty} a_{n}= \lim_{n \rightarrow \infty} 9p = 9p$ , todo lo que mostraste es que el término es multiplo de 9, o sea, $a_n= 9 k$ , pero no que tenga un límite.
Gulliver | 5 de November de 2008 | 13:49

En realidad el método ya está y solo quedaban algunos detalles.

Para demostrar que $S(a+b) \le S(a) + S(b)$ hay que seguir el proceso de la suma de dos números. Para cada dígito o bien el dígito de la suma es la suma de dígitos, o bien hay que restar 10 y sumar 1 al siguiente dígito.

Se sigue con $S(a+b+c) \le S(a+b) + S(c) \le S(a) + S(b) + S(c)$ , etcétera

Luego el procedimiento de Fede se generaliza y se llega a $S(n!) \le S(b)$ , donde b es un número de M dígitos que divide a $\displaystyle{ 10^M-1}$ y por tanto $\displaystyle{ b = 10^M-1}$
Gulliver | 5 de November de 2008 | 13:55

Quería decir $S(n!) \ge S(b)$
Gulliver | 5 de November de 2008 | 14:03

Para demostrar que $S(a+b) \le S(a) + S(b)$ hay que seguir el proceso de la suma de dos números. Para cada dígito o bien el dígito de la suma es la suma de dígitos más el posible acarreo del dígito anterior (ya descontado), o bien hay que restar 10 y sumar 1 al siguiente dígito. En el primer caso la operación individual conserva la suma de dígitos, en el segundo está restando 9 a la suma de dígitos.
fede | 5 de November de 2008 | 14:05

Cierto Gulliver,la suma de los dígitos de un múltiplo de $10^M - 1$ es mayor o igual que 9M.
(Por cierto en el esbozo de demostración que puse para M=3, los grupos de 3 digitos han de tomarse desde la derecha…)
Samy | 5 de November de 2008 | 18:38

Gracias hernan. Se me hacía raro que fuera “tan fácil”. Bueno, si planteé mal lo que había que demostrar, supongo que está todo mal.

Por lo demás, analizando mi razonamiento me doy cuenta de que lo que trataba de demostrar era trivial (Disculpa, que lo hice como a las 5 de la mañana acá en Chile xD).

Respecto a lo del límite, entiendo el error, pero a mi parecer es más bien un error de formalismo. Lo que pretendía decir es lo que escribí después de eso “No importa cuan grande (…) “.

Como sea, retiro lo dicho xD, veré si más tarde puedo estudiar el problema.
Manuel | 5 de November de 2008 | 19:05

Vale.

Y ahora… ¿lo podéis generalizar a cualquier base? Es que un resultado tan particular resta belleza al problema.
hernan | 5 de November de 2008 | 19:25

Samy: es verdad que el error del límite es de escritura, se entiende lo que querías decir.

Gulliver, fede, M: De acuerdo, ya está demostrado.

A modo de pasada en limpio/recopilación:
————————————————————–
Lema 1: Sea $A$ un entero positivo, cuya representación en base decimal imaginamos particionada en dos grupos de dígitos $A_1 A_2$ , sea $s(A)$ la sumatoria de los dígitos de A en esa base. Entonces $s(A) = s( A_1 A_2 ) = s(A_1) + s (A_2) \geq s(A_1 + A_2)$

(Gulliver | 5 de Noviembre de 2008 | 14:03)

Ejemplos:
$15 = s(18411) \geq s( 18 + 411) = 15$ ,
$17 = s(287) \geq s(28 + 7) = 8$

Obviamente, esto es generalizable a particiones múltiples o sucesivas.
————————————————————–
Lema 2: Si $N$ esmúltiplo de $10^M -1$ entonces $s(N) \geq 9 M$

(fede | 4 de Noviembre de 2008 | 22:33)

Ejemplo/demostración: Con M=4.
Entonces N es múltiplo de 999. Generalizando el criterio de divisibilidad del 9 en base 10, resulta que si consideramos los “superdígitos” de N agrupados de a 3 (o sea: tomando base $10^M$ ), estos deben sumar 999. Y el mismo proceso puede aplicarse al número resutante, todas las veces que sea necesario, hasta llegar al 999.
Juntando esto con el lema anterior, tenemos que $s(N) \geq s(999) = 3\times9$

————————————————————–
Finalmente, $n!$ es múltiplo de 999 para $n \geq 999$ , y entonces en ese rango $s(n!) \geq 3\times 9$ En general, $s(n!) \geq k \times 9$ donde k es la parte entera de $log_{10}(n)$ .
Con lo cual demostramos que $\lim_{n \rightarrow \infty} s(n!) = \infty$

Y es claro también que esto es generalizable a cualquier base no decimal.
hernan | 5 de November de 2008 | 19:27

Lema 2: Ejemplo con M=3, debería decir
Gulliver | 5 de November de 2008 | 20:30

Si $S_b(x)$ es la suma de los digitos de x en base b, entonces $\displaystyle{ S_b(n!) \ge (b-1) [log_b(n)] }$
Gulliver | 5 de November de 2008 | 20:48

$\displaystyle{ S_b(n!) < (b-1)n log_b(n) }$ asintóticamente, a partir de la aproximación de Stirling
Gulliver | 5 de November de 2008 | 20:56

¿Cual es la mejor aproximación que se conoce a $S_b(n!)$ ?
hernan | 5 de November de 2008 | 20:59

Está bueno, Gulliver… ahora solo nos queda encontrar la distribución asintótica de frecuencia de los dígitos
Manuel | 6 de November de 2008 | 11:24

Gulliver: por tanto en base 2 la suma de los dígitos es finita.. ¿no?
Gulliver | 6 de November de 2008 | 12:13

No, Manuel, en base dos tampoco es finita. $\displaystyle{ S_2(n!) \ge [log_2(n)] }$

Asintóticamente $S_2(n!)$ tiene $\displaystyle{ n (\log_2 n - \log_2 e)}$ dígitos, de los cuales $n$ son ceros a la derecha. Suponiendo que el resto de ceros y unos son aleatorios, $S_2(n!)$ iría como $\displaystyle{ \frac{n}{2} (\log_2 n - \log_2 e - 1)}$ y he visto empíricamente que se ajusta perfectamente al menos hasta $n = 2000$ .

$S_{10}(n!)$ va como $\displaystyle{ \frac{9n}{2} (\log_{10} n - \log_{10} e - 1/4)}$
Trackback | 6 Nov, 2008

Suma de los dígitos de n! (base 10) « Pensamientos irracionales
hernan | 6 de November de 2008 | 13:06

Esa forma asintótica implica que los dígitos (excepto los últimos ceros) son equiprobables, ¿no? ¿Es cosa empírica?
Gulliver | 6 de November de 2008 | 13:47

Sí, empíricamente se ajusta bien a esa suposición. Pero no he ido más allá de las comprobaciones empíricas.
Marko | 9 de November de 2008 | 07:21

Y como se puede demostrar que si n tiende a infinito ; la suma de sus cifras tiende a infinito? Igual no es que converga sino como que luego se cae al pasar a tener un montón de ceros. Que es converger, que lio, jaja. Se supone que cuando algo converge no deberia moverse a medida que se aproxima al infinito?. saludos de un neofito.
Tobar | 9 de November de 2008 | 20:46

Mas alla de lo matematico, tal vez, la intuicion nos puede dar la seguridad que necesitamos para solidificar la idea: la sumatoria de un conjunto de terminos que esta creciendo indefinidamente hasta n, es la idea, pero ¿ cual es n ?, ¿es acaso 1, 2, 3, ….1001, 110005589, ….. ?.no me dicen que sea precisamente eso. es n. si n fuera un cuerpo real objetivo y univoco, seguro que el conjunto sumatoria de su factorial tiende a un limite L . de lo contrario ”n” no esta definido y crece indefinidamente y por lo tanto la sumatoria del conjunto factorial lo hace al mismo ritmo armonico, que es una conclusion valida.

perdon por ignorar la utilizacion de simbolos; soy nuevo en el foro.
Marko | 10 de November de 2008 | 06:05

Sorry no habia leido, pero la de Hernan me parece que es estupenda. Que bakan. A proposito; y si n tiende a infinito; supongo que la seria va subiendo y bajando 0001 a 0002 a 9999 a 10000, etc; lo que no me queda claro es que se diria de la suma de digitos de n, -algo básico supongo-: cual es lo apropiado, que diverge o que converge?
Naka Cristo | 12 de November de 2008 | 12:56

Marko, la suma de los dígitos de $n$ oscila de forma no acotada

en.wikipedia.org/wiki/Limit_of_a_sequence
en.wikipedia.org/wiki/Oscillation_(mathematics)