Primes, divisors, arithmetic, number properties, ...
aziiri
Posts: 1
Joined: Mon Jan 13, 2014 12:10 pm

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.

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

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.

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;
}

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

stimmer
Posts: 10
Joined: Mon Jul 25, 2011 5:56 pm