Pseudocomposti

Sequenze  Teoria dei numeri 

Per analogia con gli pseudoprimi, numeri composti che superano un esame di primalità passato da tutti i numeri primi e da relativamente pochi numeri composti, propongo di chiamare “pseudocomposti” i numeri composti che superano un esame passato da tutti i numeri composti e da relativamente pochi numeri primi.

 

L’unica categoria nota è definita dalla sequenza .

I termini a_2n e a_{2n + 1} sono entrambi multipli di n, quindi anche tutti i termini successivi lo sono, pertanto a_n è multiplo di . Se n è composto e maggiore di 4, tutti i suoi fattori che sono primi o loro potenze non superano  e sono tra i termini del fattoriale, quindi a_n è multiplo di n.

Nel 2020 Davide Oliveri osservò che se n è primo, a_n sembra essere multiplo di n in pochi casi e quelle rare eccezioni meritano l’appellativo di “pseudocomposti”.

 

L’esame di primalità basato sulla sequenza mostrata non ha alcun valore pratico: non si conosce alcun modo efficiente per calcolare x_n e y_n e stabilire se un numero è primo in questo modo è enormemente meno veloce che utilizzando altri metodi ben noti (v. numeri primi).

 

Riscrivendo la sequenza come a_2n = n(a_{2n – 1} + a_{2n – 2}) e a_{2n + 1} = n(a_2n + a_{2n – 1}), si dimostra che , dove le due sequenze x_n e y_n sono così definite:

• x₀ = 1, x₁ = 0, x_2n = x_{2n – 1} + x_{2n – 2}, x_{2n + 1} = nx_2n + x_{2n – 1};
• y₀ = 0, y₁ = 1, y_2n = y_{2n – 1} + y_{2n – 2}, y_{2n + 1} = ny_2n + y_{2n – 1}.

 

La tabella seguente mostra i valori di x_n e y_n, per n fino a 20.

n	xn	yn
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	5	8
6	7	11
7	26	41
8	33	52
9	158	249
10	191	301
11	1113	1754
12	1304	2055
13	8937	14084
14	10241	16139
15	80624	127057
16	90865	143196
17	807544	1272625
18	898409	1415821
19	8893225	14015014
20	9791634	15430835

 

Se p è primo, il fattoriale non è multiplo di p, pertanto p è pseudocomposto se e solo se x_na₀ + y_na₁ è multiplo di p. I resti modulo p si ripetono con periodo p, quindi ha senso considerare solo i valori di a₀ e a₁ da 0 a p – 1, escludendo il caso in cui siano entrambi nulli modulo p.

In generale, possono esserci quattro casi:

• x_p e y_p sono entrambi multipli di p, nel qual caso p è pseudocomposto per qualsiasi scelta di a₀ e a₁ e potremmo definirlo “pseudocomposto assoluto”;
• x_p è multiplo di p e y_p no, nel qual caso p è pseudocomposto per qualsiasi scelta di a₀ e a₁ = 0, quindi per p – 1 combinazioni;
• y_p è multiplo di p e x_p no, nel qual caso p è pseudocomposto per qualsiasi scelta di a₁ e a₀ = 0, quindi per p – 1 combinazioni;
• né x_p né y_p sono multipli di p, nel qual caso per ogni scelta di a₀ diverso da 0 esiste un solo valore di a₁ che rende p pseudocomposto, ossia  e per ogni scelta di a₁ diverso da 0 esiste un solo valore di a₀ che rende p pseudocomposto, ossia ; anche in questo caso le combinazioni sono p – 1.

Quindi, escludendo gli eventuali pseudocomposti assoluti, ogni numero primo è pseudocomposto rispetto a esattamente p – 1 combinazioni di a₀ e a₁.

Perché allora gli pseudocomposti sono rari? Per un primo p le combinazioni differenti di a₀ e a₁ modulo p sono p² – 1 (essendo esclusa la combinazione in cui a₀ e a₁ sono multipli di p), quindi ogni primo p è pseudocomposto per una frazione  delle combinazioni.

Se non esistessero pseudocomposti assoluti, ci attenderemmo di trovare in media asintoticamente circa loglogn + 1 pseudocomposti tra i primi minori di n. Si tratta di un numero molto piccolo: in media circa 3.89 pseudocomposti inferiori a 10⁹. Questo non ci dice nulla però sull’effettiva distribuzione del numero di pseudocomposti rispetto alle varie coppie di valori di a₀ e a₁; come notò lo stesso Oliveri, non sembrano essercene per alcune combinazioni, ma probabilmente dipende solo dal numero limitato di primi esaminati.

 

Per trovare una coppia di valori di a₀ e a₁ rispetto ai quali un primo p è pseudocomposto bisogna calcolare x_p e y_p, dopodichè:

• se x_p e y_p sono entrambi multipli di p, qualsiasi scelta di a₀ e a₁ va bene, perché p è pseudocomposto assoluto;
• se x_p non è multiplo di p, si sceglie a₁ a piacere non multiplo di p e si calcola ;
• se y_p non è multiplo di p, si sceglie a₀ a piacere non multiplo di p e si calcola .

Se né x_p né y_p sono multipli di un primo p, e p è pseudocomposto rispetto alla coppia (a₀, a₁), lo è anche rispetto alle coppie e  per ogni intero n (facendo variare n le due sequenze generano le stesse coppie, in ordine differente).

 

Esistono pseudocomposti assoluti? Se i valori di x_p e y_p fossero casuali, ci sarebbe una probabilità  che p divida ciascuno di essi e se le probabilità fossero indipendenti, la probabilità che un primo sia pseudocomposto assoluto sarebbe . Se le probabilità fossero indipendenti per i vari primi, dato che  è minore di 1, ci si potrebbe attendere che non ne esistano o che ne esista solo un numero finito. Le ipotesi alla base di questo calcolo però non sono verificate e l’esistenza o meno di pseudocomposti assoluti è un problema aperto.

Se esistono, sono maggiori di 10⁷ (M. Fiorentini, 2021).

Tabelle numeriche

I valori di x_n e y_n, per n fino a 1000 (1.2 Mbyte).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.