Don't take life too seriously: it's just a temporary situation

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 Formula per la definizione della sequenza.

I termini a2n e a2n + 1 sono entrambi multipli di n, quindi anche tutti i termini successivi lo sono, pertanto an è multiplo di Fattoriale della parte intera di n / 2. Se n è composto e maggiore di 4, tutti i suoi fattori che sono primi o loro potenze non superano Parte intera di n / 2 e sono tra i termini del fattoriale, quindi an è multiplo di n.

Nel 2020 Davide Oliveri osservò che se n è primo, an 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 xn e yn 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 a2n = n(a2n – 1 + a2n – 2) e a2n + 1 = n(a2n + a2n – 1), si dimostra che Formula per il calcolo di a(n), dove le due sequenze xn e yn sono così definite:

  • x0 = 1, x1 = 0, x2n = x2n – 1 + x2n – 2, x2n + 1 = nx2n + x2n – 1;
  • y0 = 0, y1 = 1, y2n = y2n – 1 + y2n – 2, y2n + 1 = ny2n + y2n – 1.

 

La tabella seguente mostra i valori di xn e yn, 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 xna0 + yna1 è multiplo di p. I resti modulo p si ripetono con periodo p, quindi ha senso considerare solo i valori di a0 e a1 da 0 a p – 1, escludendo il caso in cui siano entrambi nulli modulo p.

In generale, possono esserci quattro casi:

  • xp e yp sono entrambi multipli di p, nel qual caso p è pseudocomposto per qualsiasi scelta di a0 e a1 e potremmo definirlo “pseudocomposto assoluto”;
  • xp è multiplo di p e yp no, nel qual caso p è pseudocomposto per qualsiasi scelta di a0 e a1 = 0, quindi per p – 1 combinazioni;
  • yp è multiplo di p e xp no, nel qual caso p è pseudocomposto per qualsiasi scelta di a1 e a0 = 0, quindi per p – 1 combinazioni;
  • xpyp sono multipli di p, nel qual caso per ogni scelta di a0 diverso da 0 esiste un solo valore di a1 che rende p pseudocomposto, ossia a(1) = –x(p) * a(0) * y(p)^(–1) mod p e per ogni scelta di a1 diverso da 0 esiste un solo valore di a0 che rende p pseudocomposto, ossia a(0) = –y(p) * a(1) * x(p)^(–1) mod p; 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 a0 e a1.

Perché allora gli pseudocomposti sono rari? Per un primo p le combinazioni differenti di a0 e a1 modulo p sono p2 – 1 (essendo esclusa la combinazione in cui a0 e a1 sono multipli di p), quindi ogni primo p è pseudocomposto per una frazione 1 / (p + 1) 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 109. Questo non ci dice nulla però sull’effettiva distribuzione del numero di pseudocomposti rispetto alle varie coppie di valori di a0 e a1; 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 a0 e a1 rispetto ai quali un primo p è pseudocomposto bisogna calcolare xp e yp, dopodichè:

  • se xp e yp sono entrambi multipli di p, qualsiasi scelta di a0 e a1 va bene, perché p è pseudocomposto assoluto;
  • se xp non è multiplo di p, si sceglie a1 a piacere non multiplo di p e si calcola a(0) = –a(1) * x(p)^(–1) * y(p) mod p;
  • se yp non è multiplo di p, si sceglie a0 a piacere non multiplo di p e si calcola a(1) = –a(0) * x(p) * y(p)^(–1) mod p.

Se né xpyp sono multipli di un primo p, e p è pseudocomposto rispetto alla coppia (a0, a1), lo è anche rispetto alle coppie ((a(0) + n) mod p, (a(1) – n * a(0) * a(1)^(–1)) mod p)((a(0) – n * a(0)^(–1) * a(1)) mod p, (a(1) + n) mod p) per ogni intero n (facendo variare n le due sequenze generano le stesse coppie, in ordine differente).

 

Esistono pseudocomposti assoluti? Se i valori di xp e yp fossero casuali, ci sarebbe una probabilità 1 / p che p divida ciascuno di essi e se le probabilità fossero indipendenti, la probabilità che un primo sia pseudocomposto assoluto sarebbe 1 / p^2. Se le probabilità fossero indipendenti per i vari primi, dato che Somma dei reciproci dei quadrati dei primi è 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 107 (M. Fiorentini, 2021).

Contattami

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