Verificatore di superprimo

Un superprimo, detto anche superprimo o primo di indice primo, è un numero primo la cui posizione nella successione di tutti i primi è a sua volta un primo. I primi ordinati cominciano da due, tre, cinque, sette, undici, tredici e diciassette; i loro indici (a partire da uno) vanno da uno a sette. Gli indici due, tre, cinque e sette sono primi, quindi tre, cinque, undici e diciassette sono superprimi, mentre due (indice uno) e sette (indice quattro) sono solo primi ordinari. Questo verificatore accetta un unico intero n. Quando n è primo la risposta restituisce l'indice di n e se tale indice è primo. L'algoritmo è un crivello deterministico, senza rete, casualità o orologio.

Che cosa è un superprimo e come è formulato il verdetto

Un superprimo si definisce con due condizioni di primalità innestate. Primo, n deve essere primo: non ha divisori positivi diversi da uno e da se stesso. Secondo, se n è il k-esimo primo nella successione crescente abituale —p uno vale due, p due vale tre, p tre vale cinque, p quattro vale sette, p cinque vale undici, e così via—, allora anche k deve essere primo.

L'indice k è esattamente il valore della funzione di conteggio dei primi π(n) ogni volta che n è primo, perché π(n) conta quanti primi sono minori o uguali a n, e n occupa quell'ultimo posto. La successione dei superprimi comincia quindi da tre, cinque, undici, diciassette, trentuno, quarantuno, cinquantanove, sessantasette, ottantatre, centonove: sono i primi agli indici primi due, tre, cinque, sette, undici, tredici, diciassette, diciannove, ventitre e ventinove.

Si noti che due, uguale a p uno, è escluso perché uno non è un indice primo, e che sette, uguale a p quattro, è escluso perché quattro è composto.

Contratto di ingresso, limiti e come si calcola l'indice

Dopo aver accettato l'intero, il motore verifica prima se n è primo con la divisione per tentativi su una ruota a sei passi. Se quel test fallisce, la richiesta viene rifiutata con un messaggio che n non è primo; tali fallimenti non vengono fatturati. Se n è primo, il motore esegue il crivello di Eratostene sull'intervallo da zero a n, conta quanti interi non marcati stanno in n o sotto n e tratta quel conteggio come l'indice k a partire da uno.

Un secondo test per tentativi decide poi se k è primo. Preferisca un verificatore di primalità dedicato quando serve solo un sì o no su n, e un calcolatore dell'n-esimo primo quando conosce già l'indice e vuole il primo stesso. Questa pagina risponde alla domanda combinata: dato un primo, il suo indice è anch'esso primo?

Dove un verificatore di superprimo dà il suo valore

Aule e allenatori di gare usano un verificatore di superprimo perché chi studia classifichi i primi di indice primo senza costruire a mano un crivello e senza fidarsi di un elenco opaco in rete. I generatori di prove hanno bisogno di un oracolo deterministico che segni i composti come ingresso non valido invece di restituire false in silenzio, perché un correttore difettoso potrebbe trattare quella bandiera come classificazione riuscita di un non primo.

I taccuini che filtrano una colonna di primi candidati fino ai superprimi possono chiamare il contratto una volta per cella e conservare l'indice restituito per una colonna di audit. Abbini questo strumento a un verificatore di primalità quando vuole classificare i composti invece di rifiutarli, e a un calcolatore dell'n-esimo primo quando vuole percorrere la successione per indice piuttosto che provare un candidato già in mano.