Método rápido para el número Nth Squarefree (usando mathematica)

Question

Estoy tratando de calcular Nth Números libres utilizando Mathematica. Lo que estoy tratando de utilizar es el SquareFreeQ[i] función.

Esta es mi solución:

NSqFree[N_] := For[n = 1; i = 1, n <= N + 1, If[SquareFreeQ[i], If[n == N, Print[i] ] n++] i++]

Pero yo soy que se supone que debe computar NSqFree[1000000000] pero parece que mi planteamiento es eterno. ¿Algún método más rápido?

Gracias,

AÑADIDO :

Aquí un pregunta de topcoder exactamente idéntica y el editorial correspondiente para el mismo.

Answer 1

Hay que utilizar el principio de Inclusión-Exclusión: supongamos que queremos encontrar el número de números libres cuadrados hasta $N$ , entonces de $N$ hay que restar el número de enteros divisibles por el cuadrado de un primo, pero luego hay que sumar cualquier múltiplo del cuadrado del producto de dos primos discontinuos y así sucesivamente, en las fórmulas el número buscado es $$ N - \sum_{p^2 \le N} \left\lfloor\frac{N}{p^2}\right\rfloor + \sum_{p^2q^2 \le N} \left\lfloor\frac{N}{p^2q^2}\right\rfloor - \sum_{p^2q^2r^2 \le N} \left\lfloor\frac{N}{p^2q^2r^2}\right\rfloor + \cdots -\cdots $$ usando el moebius $\mu$ se puede escribir esta última fórmula como $$ \sum_{n \le \sqrt{N}} \mu(n) \left\lfloor\frac{N}{n^2}\right\rfloor $$ No sé cómo escribir esto en mathematica pero debería tomar una fracción insignificante del tiempo que toma tu método actual.

Answer 2

No soy un experto en algoritmos de teoría de números, pero me parece que se puede emplear el Teorema del Resto Chino para obtener una primera puñalada decente en un algoritmo de "cribado".

• Utilizar varios registros r[p], cada uno de los cuales almacena un residuo módulo p 2 para algún primo p. Definir tal registro para varios primos pequeños p ∈ {2, 3, 5, ... , P} para s , P} para algún primo convenientemente grande P. Los utilizarás para representar un número entero R, tal que R ≡ r[p] (mod p 2 ). No debería necesitar demasiados registros de este tipo para representar fielmente incluso números no negativos razonablemente grandes (los registros pueden determinar de forma única cualquier número entero de 1 a 2 2  × 3 2  × 5 2  × ... × P 2 ).

• Cada vez que desee incrementar R, incremente también cada uno de los registros r[p]. Si R es libre de cuadrados, ninguno de estos registros será cero módulo del cuadrado del primo apropiado. Para números enteros suficientemente pequeños N, incluso se puede caracterizar N como libre de cuadrados si ninguno de estos residuos es cero. Dicho de otro modo, cuantos más registros r[p] mantenga, mayor será el rango de números libres de cuadrados que podrá detectar automáticamente utilizando estos registros.

Supongamos que quieres comprobar la cuadratura hasta un límite superior N. ¿Qué necesitas para comprobar la cuadratura utilizando únicamente registros como los que he descrito? Lo que necesitas es que cualquier número compuesto menor que N tenga un factor primo de la lista de registros que mantienes; es decir, necesitas registros para cada uno de los primos hasta √N.

Si vas a iterar a través de todos los números enteros de todos modos, puedes descubrir la lista de primos que necesitas para caracterizar la cuadratura al mismo tiempo por el Tamiz de Erasthotenes, y construir la lista de residuos modulo cuadrados de los primos a medida que avanzas. Cada vez que encuentres un nuevo primo P, siempre que P 2  < N, añada P a la lista de primos para los que mantiene registros e inicialice un registro para los residuos módulo P 2 .

Como sugiere Ross en su respuesta, se pueden utilizar los resultados sobre la distribución de los números libres de cuadrados para obtener una cota superior para el N th número libre de cuadrados (debería crecer más lentamente que N ln(N) o así, en cualquier caso). Esto te da un límite superior en el número de registros que tienes que mantener mientras buscas enteros libres de cuadrados.

A partir de esto, deberías ser capaz de mostrar un límite superior asintótico de tiempo polinómico en el tiempo de ejecución de tu procedimiento.

Answer 3

Creo que su método puede mejorarse mediante el cribado: si $n$ no es libre de cuadrados, no es necesario comprobar ninguno de sus múltiplos. Empieza con una estimación razonable (como la que dio Ross Millikan) y tamiza como lo harías en una criba de primos.

¿Es esto viable? No lo sé. No sé programar en Mathematica, pero hoy mismo intentaré implementar esto en Python.

Answer 4

No vas a hacer mil millones (si he contado bien los ceros) de bucles a corto plazo, así que necesitas un enfoque mejor. Wikipedia tiene una aproximación bajo la sección Distribución de números libres de cuadrados. Así que se puede empezar con $10^9 \pi^2/6$ y calcular cuántos por debajo de ellos están libres de cuadrados, y luego corregir a partir de ahí. Tendrás que utilizar la inclusión/exclusión, pero sólo hay que tener en cuenta unos 40.000.