Es bien conocido y fácil de demostrar que el factor primo más pequeño de un número entero $n$ es como máximo igual a $\sqrt n$ . ¿Qué se puede decir de la más grande factor primario de $n$ , denotado por $P_1(n)$ ? En particular:
¿Cuál es la probabilidad de que $P_1(n)>\sqrt n$ ?
En términos más generales, ¿cuál es el valor esperado del tamaño de $P_1(n)$ , medido por $\frac{\log P_1(n)}{\log n}$ ?
Tomemos la negación y esta es una pregunta muy conocida: ¿cuál es la probabilidad de que todos los factores primos de $n$ son $\le \sqrt{n}$ ? La respuesta se conoce de forma bastante general: para cualquier $u\ge 1$ la probabilidad de que los factores primos de $n$ son $\le n^{1/u}$ viene dada por el Dickman-de Bruijn rho, definida por una ecuación diferencial con retardo. Para $u=2$ tenemos $\rho(u) = 1-\log 2$ como en la respuesta de Ross Millikan, pero hay un cálculo muy fácil que da este caso particular:
$$\#\{n \le x: P_1(n) > \sqrt{n}\} = \sum_{p} \#\{n \le x, n < p^2: p \mid n\} = \sum_{p\le \sqrt{x}} (p-1) + \sum_{p > \sqrt{x}} \lfloor x/p \rfloor \\ = x \log 2 + O(x/\log x),$$
donde el término principal proviene del teorema de Mertens sobre $\sum_p {1/p}$ y los términos de error pueden deducirse del teorema de los números primos (o de la cota superior de Chebyshev en $\pi(x)$ ).
Aquí, por convención, $p$ se supone que sólo toma valores primos. La razón por la que esto es tan simple es que ningún $n$ aquí puede tener más de un factor primo $> \sqrt{n}$ .
La respuesta a su segunda pregunta se conoce como Constante de Golomb-Dickman . Wikipedia lo indica como $0.62433$ pero dudo que se sepa algo sobre su racionalidad, digamos.
En Hans Riesel, Números primos y métodos informáticos de factorización En la página 157, da algunas aproximaciones al factor primo más grande y al segundo más grande. En las páginas 157-158, da una heurística para una factorización "típica", que sugiere que el mayor da $$ \log P_1 / \log n \approx 1 - 1/e \approx 0.6321, $$ $$ \log P_2 / \log n \approx (1 - 1/e) / e \approx 0.2325. $$ En la página 161 menciona que Knuth y Trabb-Pardo consiguen $0.624, \; \; 0.210$ con un argumento más riguroso. Esto es 1976, Theoretical Computer Science, volumen 3, páginas 321-348. Análisis de un algoritmo de factorización simple . Así que yo diría que quieres conseguir una copia de Knuth y Trabb-Pardo, que se reproduce, con comentarios posteriores, en KNUTH
A continuación, presenta el teorema de Erdos-Kac en las páginas 158-159 y, por último, da las curvas de distribución de probabilidad para los tres factores primos más grandes en la página 163. Estos gráficos serían lo que yo llamo "funciones de distribución acumulativa", siendo la integral de la "función de distribución de probabilidad". También están tomadas de Knuth y Trabb -Pardo. Déjame hacer un jpeg.
NOTA: La tabla de la página 163 de $\rho_1(\alpha)$ coincide exactamente con la tabla de $\rho(u)$ en el enlace de Erick sobre la función Dickman-de Bruijn. Por lo tanto, creo que tienes un ganador.
\=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
\=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
En Mathworld afirma que la probabilidad de que $P_1(n) \gt \sqrt n$ es $\log 2$ . Los primeros números aproximados se dan en OEIS A064052 pero no hay referencias.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
