Dados los primeros N enteros, ¿cuántos factores primos grandes puedo desestimar y que aún quede la mitad del conjunto?

Question

Conjetura:
Para $N$ suficientemente grande, tomar el conjunto de enteros positivos hasta $N$ . A continuación, elimine todos los números que tengan un factor primo mayor que $\sqrt{N}$ . Más de la mitad del conjunto permanecerá.

Ejemplo:

Supongamos que tengo el conjunto de enteros del 1 al 37. Ahora mantengo sólo los múltiplos de 2, 3 y 5, descartando cualquier factor primo mayor. Termino con el siguiente conjunto. $$\{2,3,4,5,6,8,9,10,12,15,16,18,20,24, 25,27,30,32,36\} $$

Algo más de la mitad del conjunto $19/37 = .\overline{513}$ restos.

¿Son ciertas mis conjeturas?

Answer 1

No es una respuesta, pero sí un progreso: Como un número que tiene un factor mayor que $\sqrt N$ no puede tener ningún otro factor, cada primo de interés elimina un subconjunto disjunto. El número eliminado es entonces $$\sum_{\substack{p \text { prime} \\ p \gt \sqrt N}}\left \lfloor \frac Np \right \rfloor$$ Queremos demostrar que esta suma es menor que $\frac N2$ . Dos cosas naturales son: 1) ignorar la función suelo y 2) suponer que los primos están "distribuidos aleatoriamente" y que cada número $n$ tiene $\frac 1{\log n}$ posibilidad de ser primo. Entonces cambiamos la suma por una integral y obtenemos $$\sum_{\substack{p \text { prime} \\ p \gt \sqrt N}}\left \lfloor \frac Np \right \rfloor\approx N\int_{\sqrt N}^N\frac {dn}{n \log n}=N\left. \frac 1{\log(\log(n))}\right |_{\sqrt N}^N=N\log 2$$ que falla mucho, por lo que parece que ignorar el suelo es demasiado grueso. Sólo haciendo una prueba numérica en Alpha de $$\sum _{n=\sqrt N}^N \left \lfloor \frac N{n \log n}\right \rfloor$$ para $N=10000$ dio $3954$ Así que sospecho que el teorema de los números primos puede demostrarlo para grandes $N$ . Entonces, una búsqueda informática despejará las pequeñas $N$

Answer 2

La conjetura es errónea. Asintóticamente, la proporción de números eliminados es, como Ross Millikan encontrado , $\log 2$ .

Podemos verlo también de otra manera: Para $k < \sqrt{N}$ eliminamos los números $k\cdot p$ para todos los primos $\sqrt{N} < p \leqslant \frac{N}{k}$ y como ningún número $\leqslant N$ puede tener dos factores primos $> \sqrt{N}$ , no contamos ningún número varias veces. Así que el recuento de los números eliminados es

$$\sum_{k=1}^\sqrt{N} \left(\pi\left(\frac{N}{k}\right) - \pi(\sqrt{N})\right) \approx \sum_{k=1}^\sqrt{N} \pi\left(\frac{N}{k}\right) - \sqrt{N}\pi(\sqrt{N}).$$

$\sqrt{N}\pi(\sqrt{N}) \approx \frac{2N}{\log N}$ que para los pequeños $N$ es una proporción considerable de los números $\leqslant N$ pero para los grandes $N$ se vuelve insignificante.

Para la suma, subestimamos $\pi(x)$ utilizando $\frac{x}{\log x}$ Así que

$$\begin{align} \sum_{k=1}^\sqrt{N} \pi\left(\frac{N}{k}\right) &\geqslant \sum_{k=1}^\sqrt{N} \frac{N}{k(\log N - \log k)}\\ &\sim N\int_1^{\sqrt{N}} \frac{dt}{t(\log N - \log t)}\\ &= N\cdot\log 2. \end{align}$$

Generalmente, si para $1 \geqslant\alpha \geqslant \frac12$ eliminamos los múltiplos de todos los primos $> N^\alpha$ el mismo argumento muestra que la cuenta de los números eliminados es

$$\sum_{k=1}^{N^{1-\alpha}} \left(\pi\left(\frac{N}{k}\right) - \pi(N^\alpha)\right) \approx \sum_{k=1}^{N^{1-\alpha}}\pi\left(\frac{N}{k}\right) - N^{1-\alpha}\pi(N^\alpha) \approx \sum_{k=1}^{N^{1-\alpha}}\pi\left(\frac{N}{k}\right) - \frac{N}{\alpha\log N},$$

y la suma es asintótica

$$\sum_{k=1}^{N^{1-\alpha}}\pi\left(\frac{N}{k}\right) \sim N\int_1^{N^{1-\alpha}} \frac{dt}{t(\log N - \log t)} = N \int_0^{1-\alpha} \frac{dv}{1-v} = N\cdot\log \frac1\alpha,$$

así que para mantener la mitad de los números $\leqslant N$ debemos elegir $\alpha \geqslant e^{-1/2}$ .