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.

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*!

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 $

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.

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 **Polya conjecture** was refuted in 1958, so it is false. The smallest counterexample is the number $ 906150257 $.

The algorithm corresponding to the verification of the conjecture is similar to the following:`// Javascript`

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

}

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

Please, check our community Discord for help requests!

polya,prime,factor,decomposition,odd,even,906150257

Source : https://www.dcode.fr/polya-conjecture

© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲