El cómputo de la primera $n$ valores de la función de Liouville en el tiempo lineal

Question

Es posible calcular la primera $n$ valores de la función de Liouville en el tiempo lineal? Ya tenemos a la salida de $n$ valores que claramente no puede hacer mejor que el tiempo lineal, pero la mejor que he podido averiguar es algo como $O(n \cdot \log{\log{n}})$: llene una matriz de tamaño $n$ con niños, y para cada potencia principal $p^a$, niegan el valor en el índice de cada uno de sus múltiplos. Creo que es posible identificar el primer poderes como nos cuenta el uso de otra tabla de $O(n)$ bits, esencialmente la criba de Eratóstenes contar poderes demasiado, pero todavía hay $\sum_{p^a \le n}{\frac{n}{p^a}} = n \cdot \log{\log{n}} + O(n)$ negación de las operaciones. Es posible hacer mejor que esto?

Answer 1

Su problema está relacionado con el problema de encontrar todos los números primos hasta el $n$, y puede ser resuelto por medios similares.

Aunque el tradicional criba de Eratóstenes ha complejidad $O(n \log \log n)$, hay versiones mejoradas, que trabajan en $O(n)$ del tiempo. Esto se logra mediante el cruce de la salida de cada número compuesto exactamente una vez. Para el propósito de encontrar los números primos, estos algoritmos pueden incluso ser optimizado para $O(n /\log \log n)$ tiempo por la denominada rueda de optimización. Los detalles se pueden encontrar en, por ejemplo, este papel.

Con el fin de resolver su problema, usted tiene que calcular al menos el primer factor de la función (que se denota por a $lpf$) durante el tamizado, no sólo los números primos. Cuando la $lpf$ función está listo, usted puede calcular completamente multiplicativa funciones en $O(n)$ fácilmente por programación dinámica, por ejemplo: $$ \lambda(x) = \begin{cases} -1 & x = lpf(x) \\ -\lambda \left( \frac{x}{lpf(x)} \right) & \text{otherwise} \end{casos} $$

One of the algorithms which calculates least prime factors in $O(n)$ time is described here. Below you can see its implementation in C++, with primes being a sorted list of all primes found so far, and lpf being an array representing the same-named function.

vector<int> primes;
vector<int> lpf(n, -1);
for (int x = 2; x < n; x++) {
  if (lpf[x] < 0) { //prime found
    lpf[x] = x;
    primes.push_back(x);
  }
  for (int i = 0; i < primes.size(); i++) {
    int p1 = primes[i], y = p1 * x;
    if (p1 > lpf[x] || y >= n)
        break;
    lpf[y] = p1;
  }
}

Consider a number $x$ having least prime factor $p = lpf(x)$. For each prime $p_1 \le p$, it is easy to see that $lpf(p_1 \cdot x) = p_1$. The algorithm simply applies this crossing-out rule for each number $x$ in increasing order. Of course, it needs the sorted list of primes in order to iterate over all the necessary primes $p_1$.

Every composite number $s$ is crossed out exactly once when considering number $x = \frac{y}{lpf(y)}$, so time complexity is $O(n)$. In practice however, it is slower than the traditional $O(n \log \log n)$ tamiz, al menos para el propósito de encontrar números primos. Supongo que su enfoque también sería más rápido, especialmente con bitsets.

Si usted está interesado en la práctica de la aceleración de su algoritmo, es mejor pensar acerca de la memoria/memoria caché de optimización, en lugar de mejorar complejidad asintótica por un doble registro factor =)

Answer 2

En realidad, esto no puede ser verdad porque usted no puede obtener el primer encendido (power)s en $O(n)$:

La criba de eratóstenes toma al menos $O(nloglogn)$ Operaciones.

Supongamos que tenemos una lista de todos los números primos hasta el $n$ dado. A continuación, comprobar a cada una de las $k$ para la membresía en la lista tiene al menos (si sólo nos marque la primera $\pi(\sqrt{k})$ elementos) $\pi(\sqrt{k})$ de las operaciones de cada uno, lo que equivale a más de $O(1)$ por lo que está fuera. Luego pudimos comprobar cada número de primalidad, pero el más rápido que se conoce primalidad de la prueba se ejecuta en $O(log(n)^6)$, también más de $O(1)$. Ya que para cada número que sea necesario ejecutar en contra de una lista o de verificación a mano, que asciende a todas las posibilidades y llegamos a la conclusión de que es imposible calcular el valor de todas las $k \leq n$ $O(n)$