Computing the first $n$ values of the Liouville function in linear time Is it possible to compute the first $n$ values of the Liouville function in linear time?  Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out is something like $O(n \cdot \log{\log{n}})$: fill an array of size $n$ with ones, and for each prime power $p^a$, negate the value at the index of each of its multiples.  I think it is possible to identify the prime powers as we count up using another table of $O(n)$ bits, essentially the sieve of Eratosthenes counting powers too, but there are still $\sum_{p^a \le n}{\frac{n}{p^a}} = n \cdot \log{\log{n}} + O(n)$ negation operations.   Is it possible to do better than this?
 A: Your problem is related to the problem of finding all the primes up to $n$, and it can be solved by similar means.
Although the traditional sieve of Eratosthenes has complexity $O(n \log \log n)$, there are improved versions, which work in $O(n)$ time. It is achieved by crossing out each composite number exactly once. For the purpose of finding primes, these algorithms can even be optimized to $O(n /\log \log n)$ time by the so-called wheel optimization. You can find details in e.g. this paper.
In order to solve your problem, you have to calculate the least prime factor function (denoted by $lpf$) during sieving, not only the primes. When the $lpf$ function is ready, you can compute completely multiplicative functions  in $O(n)$ easily by dynamic programming, e.g.:
$$
  \lambda(x) = 
  \begin{cases}
    -1 & x = lpf(x) \\
    -\lambda \left( \frac{x}{lpf(x)} \right) & \text{otherwise}
  \end{cases}
$$
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 $y$ 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)$ sieve, at least for the purpose of finding primes. I guess your approach would also be faster, especially with bitsets.
If you are interested in practical acceleration of your algorithm, you'd better think about memory/cache optimization, instead of improving asymptotic complexity by a double-log factor =)
A: I know this question was posed 5 months ago but I thought I would add something.
Not sure if this will increase computing time but,
$\lambda(n)=i^{\tau(n^{2})-1}$,
where $\tau(n)$ is the divisor function and $i$ is the imaginary unit. From this of course the summatory Liouville function is $L(n)=\sum_{j=1}^{n}i^{\tau(j^{2})-1}$. Perhaps the divisor function can be calculated in less time.
A: Actually this cannot be true because you can't get the prime (power)s in $O(n)$:
The sieve of eratosthenes takes at least $O(nloglogn)$ Operations.
Assume we have a list of all the primes up to $n$ given. Then checking each $k$ for membership in the list takes at least (if we only check the first $\pi(\sqrt{k})$ elements) $\pi(\sqrt{k})$ operations each, which amounts to more than $O(1)$ so that's out. Then we could check each number for primality but the fastest known primality test runs in $O(log(n)^6)$, also more than $O(1)$. Since for each number we either have to run it against a list or check it by hand that amounts to all possibilites and we conclude it's impossible to calculate the value for all $k \leq n$ in $O(n)$
