If you are not familiar with Polya's conjecture you may want to read this.

This conjecture was proven false for n=906,316,571 fifty years ago. This means that they did not have fancy computers.

Assume this is ProjectEuler problem (finding the counter-example), what is the solution that you propose ? I prefer that it does not use much memory and running time.

## About Polya's conjecture.

- Marcus_Andrews
- Administrator
**Posts:**1473**Joined:**Wed Nov 09, 2011 5:23 pm

### Re: About Polya's conjecture.

Here is a way to find the first counterexample $906150257$ in C++ (about 40 seconds on my machine):

The Liouville value $\lambda(n)$ is defined as $\lambda(n) = (-1)^{\Omega(n)}$ where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity. If the summatory Liouville function $L = \sum_{i=1}^{k} \lambda(i)$ is greater than $0$ for some $k$, then we have found a counterexample to the Pólya conjecture.

Moving onto the main program (using $n = 10^9$):

We can use a modified Sieve of Eratosthenes algorithm to calculate a prime divisor (which we'll denote $D(i)$) for each $i$ over $2 \leq i \leq n$.

After initializing the summatory value $L = 1$, we iterate from $i=2$ upwards and calculate $\lambda(i) = -\lambda(i / D(i))$. As we calculate each Liouville value, we add it to $L$. Once $L>0$, we have found our counterexample, and we stop.

Overall, the sieve requires $O(n)$ space and $O(n \log \log n)$ time, and then finding the counterexample can be done in $O(n)$ time.

There are ways to improve this, but I leave that as an exercise to the reader.

The Liouville value $\lambda(n)$ is defined as $\lambda(n) = (-1)^{\Omega(n)}$ where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity. If the summatory Liouville function $L = \sum_{i=1}^{k} \lambda(i)$ is greater than $0$ for some $k$, then we have found a counterexample to the Pólya conjecture.

Moving onto the main program (using $n = 10^9$):

We can use a modified Sieve of Eratosthenes algorithm to calculate a prime divisor (which we'll denote $D(i)$) for each $i$ over $2 \leq i \leq n$.

After initializing the summatory value $L = 1$, we iterate from $i=2$ upwards and calculate $\lambda(i) = -\lambda(i / D(i))$. As we calculate each Liouville value, we add it to $L$. Once $L>0$, we have found our counterexample, and we stop.

Overall, the sieve requires $O(n)$ space and $O(n \log \log n)$ time, and then finding the counterexample can be done in $O(n)$ time.

Code: Select all

```
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
long long polya(long long n){
long long L = 1, sqrtN;
vector<long long> D(n+1); //prime divisors
vector<int> lambda(n+1); //Liouville values
lambda[1] = 1;
for (long long i = 0; i<=n; ++i) D[i] = i; //D = [0,1,2,...,n]
sqrtN = sqrt(n);
for (long long i = 2; i <= sqrtN; ++i) //Sieve of Eratosthenes
if (D[i] == i) //i is prime
for (long long j = i*i; j<=n; j+=i)
D[j] = i; //i is a prime divisor of j
for (long long i = 2; i<= n; ++i){ //look for counterexample
lambda[i] = -lambda[i/D[i]];
L += lambda[i];
if (L>0) return i; //counterexample found
}
return 0; //no counterexample found
}
int main(){
long long n = 1000000000LL;
cout << polya(n) << endl;
return 0;
}
```

### Re: About Polya's conjecture.

Isn't the summatory Liouville function just the sum of the Mertens function at [n/(d^2)] for 1<= (d^2)<=n ?

There's a way of calculating the Mertens function in O(n^(2/3+e)) (by Lehman, the same Lehman named on the page you linked to.) And on PE there are dozens of questions on the topic of 'sum the multiplicative function' where there's a O(n^(3/4)) or better solution - the method has attained an almost legendary status here and I don't want to give away any clues

There's a way of calculating the Mertens function in O(n^(2/3+e)) (by Lehman, the same Lehman named on the page you linked to.) And on PE there are dozens of questions on the topic of 'sum the multiplicative function' where there's a O(n^(3/4)) or better solution - the method has attained an almost legendary status here and I don't want to give away any clues