Si hay una función f (n) = g (n) / n para todos los enteros positivos ‘n’, donde g (n) es el número de ceros factorial n! termina con cuando se escribe en base ‘n’, ¿cuál es el valor máximo de f (n)?

Answer 1

¿Cuál es el poder más alto de [matemáticas] n [/ matemáticas] que divide [matemáticas] n! [/ Matemáticas]? Bueno, obviamente cuando [math] n [/ math] es primo es 1. En general, la potencia más alta de un primer divisor [math] n! [/ Math] es

[matemáticas] \ lfloor n / p \ rfloor + \ lfloor n / p ^ 2 \ rfloor + \ lfloor n / p ^ 3 \ rfloor +… [/ math]

Para que un número termine con [matemática] k [/ matemática] base de ceros [matemática] n [/ matemática], debe ser divisible por [matemática] n ^ k [/ matemática], y por lo tanto por [matemática] p ^ k [/ math] para cada primo [math] p \ mid n [/ math]. La fórmula anterior es obviamente máxima cuando [math] p [/ math] es lo más pequeño posible, por lo que los valores máximos de [math] g (n) [/ math] se encuentran con potencias de 2.

[matemática] g (2) = 1 [/ matemática], entonces [matemática] f (2) = 1/2 [/ matemática]

La potencia más alta de [matemáticas] 2 [/ matemáticas] que divide [matemáticas] 4! [/ Matemáticas] es [matemáticas] 2 + 1 = 3 [/ matemáticas], por lo que la potencia más alta de 4 es [matemáticas] 1 [/ matemáticas]. Así

[matemática] g (2 ^ 2) = 1 [/ matemática], entonces [matemática] f (4) = 1/4 [/ matemática]

En general, la potencia más alta de 2 en [matemáticas] 2 ^ k! [/ Matemáticas] será [matemáticas] 2 ^ {k-1} + 2 ^ {k-2} + 2 ^ {k-3} +… + 1 = 2 ^ k – 1 [/ matemáticas]. Eso significa que la potencia más alta de [matemáticas] 2 ^ k [/ matemáticas] en [matemáticas] 2 ^ k! [/ Matemáticas] es [matemáticas] \ lfloor (2 ^ k-1) / k \ rfloor [/ matemáticas]

Comprobación: [matemáticas] 8 ^ 2 | 8! [/ Matemáticas]. [matemáticas] 16 ^ 3 | 16! [/ Math], ya que [math] 2 ^ {15} | 16! [/ Matemáticas]. [matemáticas] 32 ^ 6 | 32! [/ Math], ya que [math] 2 ^ {31} | 32! [/ Matemáticas]

Entonces, [matemáticas] g (2 ^ k) = \ lfloor (2 ^ k-1) / k \ rfloor [/ math]. [matemáticas] f (2 ^ k) =
\ lfloor (2 ^ k-1) / k \ rfloor / 2 ^ k [/ math] Pero [math] (2 ^ k-1) / k [/ math] obviamente crece más lentamente que [math] 2 ^ k [ / math], por lo que el primer valor será el más alto.

Por lo tanto, el valor máximo de [math] f (x) [/ math] está en [math] f (2) = 1/2 [/ math].

Answer 2

Primero, necesitamos una forma de calcular [matemáticas] g (n) [/ matemáticas].

El número de ceros en un número es igual a la mayor potencia de 10 que divide el número. En otras palabras, [matemáticas] g (n) = \ max \ {k \ in \ mathbb {N}: 10 ^ k \ mid n! \}[/matemáticas].

¡Dado que 10 = 2 * 5, podemos considerar el menor de [math] \ max \ {k \ in \ mathbb {N}: 5 ^ k \ mid n! \} [/ math] y [math] \ max \ {k \ in \ mathbb {N}: 2 ^ k \ mid n! \} [/ math], ya que si [math] 2 ^ k \ mid n! [/ math] y [math] 5 ^ k \ mid n! [/ math], entonces [math] 10 ^ k \ mid n! [/matemáticas].

Como 2 es menor que 5, [math] \ max \ {k \ in \ mathbb {N}: 2 ^ k \ mid n! \} [/ math] siempre será mayor que [math] \ max \ {k \ in \ mathbb {N}: 5 ^ k \ mid n! \}[/matemáticas]. ¡Entonces estamos interesados ​​en [math] \ max \ {k \ in \ mathbb {N}: 5 ^ k \ mid n! \}[/matemáticas].

Afortunadamente, podemos calcular esto. El número de veces que 5 divide n! es igual al número de múltiplos de 5 menor o igual a n más los múltiplos de 25 menor o igual a n más los múltiplos de 125 menor o igual a n más …

Esto se debe a que cada múltiplo de 5 debajo de n agrega uno al valor de g (n). Cada múltiplo de 25 agrega dos al conteo, pero como ya lo contamos una vez (también es un múltiplo de 5), solo necesitamos agregar uno más. Un argumento similar es válido para cada potencia de 5. Finalmente, llegamos a una potencia de 5 mayor que n y podemos dejar de contar. Entonces obtenemos la fórmula:

[matemáticas] g (n) = \ sum_ {j = 1} ^ \ infty \ left \ lfloor {\ frac {n} {5 ^ j}} \ right \ rfloor [/ math]

Si dejamos caer al operador de piso, obtenemos:

[matemáticas] g (n) = \ sum_ {j = 1} ^ \ infty \ frac {n} {5 ^ j} [/ matemáticas]

Si dividimos esto por n, obtenemos una serie geométrica, y el cálculo de introducción nos dice que es igual a [matemáticas] \ frac {1} {5} * \ frac {1} {1 – \ frac {1} {5 }} = \ frac {1} {5} * \ frac {5} {4} = \ frac {1} {4} [/ matemáticas].

Entonces, si ignoramos el piso, el valor de n no importa. Lo que encontrará es que a medida que n se hace más y más grande, se acercará a este valor (0.25). Entonces el valor supremum es 0.25, pero no hay un valor máximo. En otras palabras, la función se acerca a 0.25 cuando n va al infinito, pero nunca alcanza ese valor.

Podemos ver esto porque si [matemáticas] 5 ^ k \ mid n [/ matemáticas], entonces [matemáticas] \ left \ lfloor {\ frac {n} {5 ^ k}} \ right \ rfloor = \ frac {n} {5 ^ k} [/ matemáticas]. Si [math] 5 ^ k> n [/ math], entonces [math] \ left \ lfloor {\ frac {n} {5 ^ k}} \ right \ rfloor = 0 [/ math]. Entonces, si comenzamos n = 1, cada vez que lo multiplicamos por 5, f (n) se acerca un poco más a [math] \ frac {1} {4} [/ math].

Incluso podemos definirlo recursivamente: [matemáticas] f (5 ^ 1) = 1 [/ matemáticas] y [matemáticas] f (5 ^ {k + 1} = f (5 ^ k) + \ frac {1} { 5 ^ {k + 1}} [/ matemática]. En otras palabras, [matemática] f (5 ^ k) = \ sum_ {j = 1} ^ k \ frac {1} {5 ^ j} = \ frac { 1} {5} * \ frac {1 – 5 ^ {- (k + 1)}} {1 – \ frac {1} {5}} = \ frac {1} {4} * (1 – 5 ^ { – (k + 1)}) [/ matemáticas]