¿Es buena la fórmula de Kamenetsky para el número de dígitos en n-factorial?

Question

En ¡Número de dígitos en n! , ya cerrado, se mencionaba la fórmula de Dmitry Kamenetsky, $[\bigl(\log(2\pi n)/2+n(\log n-\log e)\bigr)/\log 10]+1$ para el número de cifras decimales en $n$ -factorial. Toma, $[x]$ es la parte entera de $x$ . La fórmula aparece en A034886 en la Online Encyclopedia of Integer Sequences, http://oeis.org/A034886 . Mi pregunta es si esta fórmula es exacta para todos los $n$ o está ocasionalmente apagado. En la OEIS no se da ninguna prueba de exactitud, y ningún artículo de Kamenetsky aparece en Math Reviews.

En el otro hilo, mencioné la discusión en el grupo de noticias de Usenet sci.math en enero-febrero, Asunto: Número de dígitos en factorial. Aunque no se encontró ni prueba ni contraejemplo, recomendaría echar un vistazo a esa discusión antes de empezar con esta cuestión.

EDITADO 11 Ago 2011: Observo que la pregunta también ha surgido en m.se: pregunta 8323, 30 oct 2010.

Answer 1

Un contraejemplo es $n_1 := 6561101970383$ con $$\log_{10} \left( (n_1/e)^{n_1} \sqrt{2\pi n_1} \right) = 81244041273652.999999999999995102483 - \phantom; ,$$ pero $$\log_{10} (n_1!) = 81244041273653.000000000000000618508 + \phantom;.$$ Si he calculado bien, $n_1$ es el primer contraejemplo, y el único hasta $10^{13}$ . El cálculo debe alcanzar $10^{15}$ en algún momento de la próxima semana, con una probabilidad de alrededor de $1 - \exp(-\frac16) \sim 15\%$ de encontrar un $n_2$ .

El cálculo (en gp/pari ) necesitó aquí unas 40 horas de CPU, que se redujeron a 4 horas al ejecutarse en paralelo en 10 de los 12 cabezales de alhambra.math.harvard.edu . Esto fue no calculando $\log_{10} (n!)$ con suficiente precisión para cada $n \leq 10^{13}$ lo que habría llevado cientos de veces más tiempo. El problema de encontrar valores casi integrales de $\log_{10} (n!)$ es un caso especial del "dilema del fabricante de mesas" (Wikipedia atribuye esta feliz acuñación a William Kahan); en este caso, la técnica de aproximación lineal sugerida por Lefèvre al final de la página 15 de su diapositivas lleva tiempo $\tilde O(N^{2/3})$ para encontrar todos los ejemplos con $n < N$ . Eso es lo que se está ejecutando en alhambra ahora.

Por el camino aparecieron algunos términos más de la secuencia A177901: $252544447$ , $1430841730$ , $5042264463$ , $31774693500$ , $40752166709$ , $46787073630$ , $129532358256$ , $421559495894$ , $2418277169072$ , $6105111564681$ , y entonces $n_1 = 6561101970383$ que podría incluso convertirse en el último plazo hasta el $10^{15}$ porque $\log_{10} (n_1!)$ está tan cerca de un número entero (aproximadamente $9$ veces más cerca de lo necesario para nuestro propósito). [ EDITAR Es la última legislatura $<10^{14}$ pero no $10^{15}$ ver más abajo]. El término $252544447$ fue reportado en math.se #8323 por Byron Schmuland [ EDITAR y unos meses antes por David Cantrell en sci.math], aunque todavía no se ha publicado en OEIS. Los siguientes parecen ser nuevos, y los publicaré en OEIS en breve.

Kamenetsky tenía razón al sugerir que la aproximación debería fallar a veces: en base 10, esperamos que $n$ sea un contraejemplo con una probabilidad aproximada de $1/cn$ con $c = 12 \log 10$ por lo que, en promedio, cada rango $[N, 10^{12}N]$ debería tener alrededor de uno. Así pues, no es de extrañar que el primero (pasado $n=1!$ ) resulta tener $13$ dígitos. Esta heurística es también la fuente de la estimación $1-\exp(-\frac16)$ para la probabilidad de otro contraejemplo en $[10^{13}, 10^{15}]$ .

ACTUALIZACIÓN El cálculo ya ha pasado $10^{14}$ sin encontrar un nuevo contraejemplo. Sin embargo, sí encontró un nuevo término para la secuencia OEIS un poco más allá de $10^{14}$ : $n=125291661119688$ con $\log_{10}(n!)$ cercano pero justo por debajo del entero más próximo $1711938609606982$ (donde un contraejemplo debe estar un poco por encima), y tampoco tan cerca como $1/(12n)$ - la diferencia es de $1/(8.4n)$ .

Ya que estoy: Debería haber mencionado que el cálculo gp/pari también encontró (en un minuto o dos) todos los términos en $[10^4,10^8]$ de la OEIS, lo que da cierta credibilidad a los nuevos resultados; y agradezco a Gerry Myerson que me llamara la atención sobre esta cuestión con su edición de hace unas dos semanas.

Answer 2

Hola a todos,

Mi fórmula es sólo una aproximación, ya que utiliza la aproximación de Stirling para $n!$ . Espero que la fórmula falle a veces. He aumentado la precisión de mi programa y puedo confirmar que la fórmula no falla para $n\leq5\cdot10^7$ . Haré más pruebas para ver si puedo mejorar este límite. Estad atentos.

Answer 3

Se trata de un cálculo sencillo que utiliza la fórmula asintótica para $\log_{10}(n!)$ . Computación con $\ln$ en su lugar (sólo hay que dividir los resultados por $\ln(10)$ ), Maple da $$\ln{n!} \sim \left(\ln(n)-1\right)n+\ln(\sqrt{2\pi})+\frac{\ln(n)}{2}+\frac{1}{12}n^{-1}-\frac{1}{360}n^{-3}+\frac{1}{260}n^{-5}-\frac{1}{1680}n^{-7}+O(n^{-9})$$ para la versión ampliada de (el logaritmo de) la fórmula de Stirling. Así que mientras 1 sea mayor que el resto después de tomar los 3 primeros términos de la fórmula anterior, la fórmula es bastante buena. Sólo para unos pocos $n$ podría tener problemas.

No me sorprendería que esta pregunta también se cerrara: era demasiado fácil de responder con cualquier CAS.

---

Edición: como ahora entiendo mejor la pregunta, y Noam Elkies ha informado de un nuevo resultado en su búsqueda, he pensado en intentar añadir un término más a la aproximación y ver qué obtengo. Más concretamente, utilice

log10((n/exp(1))^n*sqrt(2*Pi*n)*exp(1/12/n))

(en notación Maple) en lugar de la fórmula original. Para $n=6561101970383$ , esta aproximación da exactamente los mismos dígitos que se muestran en la respuesta de Noam para la respuesta exacta.

En otras palabras, me atrevería a conjeturar que, utilizando esta aproximación concreta, los contraejemplos que pudiera haber serían tan grandes que nunca podríamos exhibirlos. Llámelo una aproximación exacta para ultrafinancieros si quieres.