Contare i primi contando i composti. L’algoritmo di Legendre.

L’idea di base è abbastanza semplice e rientra nella categoria dell’uovo di Colombo: prendiamo, ad esempio, il campo di numeri da 1 a 210; quanti sono i composti multipli di 2? Ovviamente 210/2. E quanti sono i multipli di 3? Ovviamente 210/3. Se sommo questi due risultati, ho i composti multipli di 2 e di 3. Ma quante volte ho contato doppio un composto multiplo di 2 o multiplo di 3 nella somma risultante? Semplice! 210/(2*3) che vado a sottrarre alla somma. Se ripeto l’esercizio per tutte le coppie di combinazioni di numeri primi (2-3, 2-5, 2-7, 2-11, 2-13, 3-5, …, 11-13, 13-13), ho il numero di composti tra i cui fattori ci sono singoli numeri primi o coppie di numeri primi. Ma non ho ancora considerato i composti formati da tre numeri primi come fattori. Allora comincio a sommare, al risultato precedente, 210/(2*3*7) e poi 210/(2*3*11) e poi ancora 210/(2*3*13) e così via per tutte le combinazioni di triplette di numeri primi. Consideriamo, solo ad esempio, le due triplette iniziali: quante volte ho contato doppio un composto dei tre fattori nelle due combinazioni utilizzate? Semplice; 210/(2*3*7*11). Quindi vado a sottrarre questo risultato. E così via per tutte le combinazioni di primi. Morale della storia? Quando il conteggio dei composti è effettuato dividendo un solo numero primo, oppure tre numeri primi, oppure cinque numeri primi, ovvero un numero di numeri primi dispari, il risultato della divisione deve essere sommato: a questa somma deve essere sottratto il risultato di tutte le divisioni in cui la combinazione di fattori primi al divisore è pari ovvero le coppie di numeri primi, le quadruple di numeri primi, le sestuple, etcetera. Alla fine, al calcolo dei “non primi” bisogna aggiungere il numero speciale “1” mentre bisogna sottrarre 1 per ogni numero primo considerato (nel campo 1-210 vedremo perché i numeri primi considerati vanno da 2 a 13). Rimane solo da stabilire quanti numeri primi bisogna includere nelle combinazioni del calcolo: come nei recenti crivelli di tendenza, la radice quadrata di 210 (pari a 14,49) rappresenta il limite dei numeri primi da considerare; il numero primo prossimo inferiore a 14 è pari a 13. Infatti 13*13=169 che è dentro il campo mentre 17*17=289 che è fuori dal campo. Ma questo vuol dire che tutti i multipli di 17 sono tutti fuori dal campo 1-210? Ovviamente no ma li abbiamo gia conteggiati nei composti di 2, così come nei composti di 3 e nei composti di 2*3, etcetera! Quindi il 17 non deve essere considerato nelle combinazioni dei fattori così come il 19 e tutti i numeri primi superiori a 13. Perchè possiamo affermare che tutti i composti nel campo 1-210 hanno almeno un fattore primo che va da 2 a 13. Nel campo 1-210 non esiste un composto che abbia un fattore primo maggiore di 13 ma che non abbia, contemporaneamente, un altro fattore primo inferiore o pari a 13. Utilizzando, nel calcolo, tutte le combinazioni di composti con fattori che vanno da 2 a 13, abbiamo quindi incluso nel calcolo tutti i composti presenti nel campo 1-210.
Per inciso, il numero di primi nel campo 1-210 è pari a 46. Se volete comprendere, con una grafica colorata, come funziona l’algoritmo, potrete scaricare un foglio .pdf dal seguente link …
http://www.vincs.it/upfiles/HowManyPrimesCalculatingComposites%20-%2020160709%20-%20EN.pdf

Se volete calcolare con precisione il numero di primi in qualunque campo di numeri da 1 fino a 10000000 (dieci milioni) potete scaricare la calcolatrice ad uso gratuito VincSCalc ed utilizzare le funzioni πc (pigreco calcolo), in basso a destra nella tastiera, dopo aver scelto da menù CalcSettings/DataType/BigInt …
http://www.vincs.it/VincSCalc

Se invece volete scoprire il mondo dei numeri primi ed in particolare un nuovo teorema originale da cui scaturisce un test di primalità ed il suo crivello, visitate il mio sito http://www.vincs.it/ Grazie a tutti i visitatori.

Pubblicità

Legendre’s primes counting algorithm

A tricky algorithm to calculate the total amount of prime numbers in a certain range was invented by Legendre (Prime-counting function – Wikipedia). The implementation of this algorithm is featured in the free calculator software VincSCalc  (since the earliest published versions) which demonstrates its full potential in terms of efficiency. In short terms, the algorithm calculates the amount of prime numbers by calculating the total amount of composite numbers.

The basic idea is quite simple and is part of the Columbus’s egg category: let’s take, for example, the range of numbers from 1 to 210; how many are there composite numbers multiples of 2? Obviously 210/2. And how many multiples of 3? Obviously 210/3. If we sum these two results, we’ll get the total amount of composite numbers of 2 and 3. But how many times I counted twice a multiple composed of 2 or a multiple composed of 3 in the resulting sum? Quite easy! 210/(2*3) that I’m going to subtract the sum. If I repeat the exercise for all pairs of combinations of prime numbers (2-3, 2-5, 2-7, 2-11, 2-13, 3-5, …, 11-13, 13-13), I will get the total amount of composites, among which factors there are individual prime numbers or pairs of prime numbers. But I have not yet considered the composites consisting of three prime numbers as factors. Then let’s go on to add, to the previous result, 210/(2*3*7) and then 210/(2*3*11) and then again 210/(2*3*13) and so on for all the combinations of triplets of prime numbers.

Let’s consider, just for example, the two initial triplets: how many times did I count twice a composite number of the three factors in the initials two combinations used? Again quite easy; 210/(2*3*7*11).
So I’m going to subtract this result to the total amount of composite numbers. And so on for all the combinations of prime numbers taken three by three. Moral of the story? When the count of the composite numbers is carried out by dividing a single prime number, or three prime numbers, or five prime  numbers, or any odd combination number prime numbers, the result of the division must be added: this total amount of composite numbers must be subtracted by the result of all divisions in which the combination of the factors equals pairs of prime numbers, quadruple of prime numbers, sextuple of prime numbers, then any even combination of prime numbers.

At the end, to the calculation of “non-prime-numbers” we must add the special number “1” and also to subtract 1 for every prime number considered (in the field 1-210 we will see why the prime numbers considered are in the range from 2 to 13). It only remains to determine how many prime numbers must be included in the calculation of combinations: as in the recent trend of sieves, the square root of 210 (around 14,49) is the limit of the prime numbers to consider; the closest prime number less than 14 is equal to 13. In fact, 13 * 13 = 169 which is inside the given range while 17*17 = 289 which is off the range. But does this mean that all multiples of 17 are all out of the range 1-210? Of course not, but we have already them counted in all composite numbers of 2, as well as in all composite numbers of 3 and all composite numbers of 2*3, etcetera!

Then 17 should not be considered in any combinations of factors as well as 19 and all prime numbers greater than 13. Because, for sure, we can say that all of the composite numbers  in the range 1-210 have at least a prime factor which is in the range from 2 to 13. In the field 1-210 does not exist a composite number having a prime factor greater than 13 that has not, at the same time, another prime factor lower or equal to 13. By using, in the calculation, all the combinations of prime factors ranging from 2 to 13, we therefore included in the calculation of all the composite numbers present in the range 1-210.

By the way, the number of primes in the field 1-210 is equal to 46. If you want to understand, with colorful graphics, how the algorithm works, you can download a .pdf sheet from the following link …
http://www.vincs.it/upfiles/HowManyPrimesCalculatingComposites%20-%2020160709%20-%20EN.pdf

If you want to accurately calculate the number of primes in any range of numbers from 1 to 10,000,000 (ten million) you can download the free to use calculator VincSCalc and use the πc functions (pi calculations), at bottom right of the keyboard, after having choose by menu CalcSettings / DataType / BigInt …

You can download VincSCalc from http://www.vincs.it/VincSCalc