Search for a tool
Pólya Conjecture

Tool (algorithm) to invalidate the Polya conjecture. Polya's conjecture suggests that the majority of the prime factor numbers of numbers less than a precise integer is odd.

Results

Pólya Conjecture -

Tag(s) : Arithmetics, Algorithm

Share dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Pólya Conjecture' tool, so feel free to write! Thank you!

# Pólya Conjecture

## Statement of the Conjecture

In number theory, Pólya's conjecture, proposed by the Hungarian mathematician George Pólya in 1919, states that for any integer $N$, in the decomposition into prime factors of all natural integers less than $N$, there are more decompositions with an odd number of factors than decompositions with an even number of factors.

This conjecture is false, the first counterexample is $N = 906150257$

### How to prove the Polya conjecture?

To prove that a conjecture is true, a rigorous mathematical proof is needed. To prove that the conjecture is false, it is enough to give one counter-example.

Example: For $N = 10$, there are 5 decompositions with an odd number of factors: $8, 7, 5, 3, 2$, and 4 decompositions with an even number of factors: $9, 6, 4, 1$. Since $5 > 4$, the conjecture is true for $N = 10$, but this does not mean that it is true for all $N$.

### What is the first counterexample?

The Polya conjecture was refuted in 1958, so it is false. The smallest counterexample is the number $906150257$.

### What is the Polya check algorithm?

The algorithm corresponding to the verification of the conjecture is similar to the following:// Javascriptvar even = 1;var odd = 0;var d = new Array();for (i = 2; i < 4000000000; i++) { d = prime_factor_decomposition(i); // return a table with all factors if (d.length % 2) odd++; else even++; if (even > odd) { alert(i); break;}

## Source code

dCode retains ownership of the online "Pólya Conjecture" tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any "Pólya Conjecture" algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any "Pólya Conjecture" function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for "Pólya Conjecture" will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!