Tool and algorithm to disprove the Polya conjecture. The Polya conjecture proposes that the majority of values of the prime factor count among numbers less than a specific integer are odd.
Pólya Conjecture - dCode
Tag(s) : Arithmetics, Algorithm
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!
Pólya Conjecture
Statement of the Conjecture
In number theory, the Polya conjecture, proposed by the Hungarian mathematician George Polya in 1919, states: For any integer $ N > 1 $, the set of prime factorization of positive natural numbers less than $ N $ consists of more factorizations with an odd number of factors than of factorizations with an even number of factors.
This conjecture is false, the first counterexample is $ N = 906150257 $. Since the smallest counterexample is quite large, it is often used to show that a conjecture can be verified several million times while still being false.
Answers to Questions (FAQ)
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 $.
The number 1 has no prime factors, so 0 factor, its decomposition is considered even.
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:// Javascript
var even = 1; // number 1
var odd = 0;
var factors = [];
for (i = 2; i < 1000000000; i++) {
factors = prime_factors(i); // return [factor1, factor2, ...]
if (factors.length % 2) odd++;
else even++;
if (even > odd) {
alert(i);
break;
}
}
Source code
dCode retains ownership of the "Pólya Conjecture" source code. Except explicit open source licence (indicated Creative Commons / free), the "Pólya Conjecture" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Pólya Conjecture" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Pólya Conjecture" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.
Cite dCode
The copy-paste of the page "Pólya Conjecture" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Pólya Conjecture on dCode.fr [online website], retrieved on 2024-12-21,
