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

Permutazioni prime (numero di)

Matematica combinatoria 

Data una permutazione P degli interi da 0 a n, indichiamo con P(k) la posizione nella sequenza occupata da k; per esempio, nella permutazione { 0, 3, 1, 2 } degli interi fino a 3, P(1) = 2, perché 1 va in posizione 2, iniziando a contare da zero.

Si chiamano “permutazioni prime” di n le permutazioni di n nelle quali k + P(k) è un numero primo per tutti i valori di k da 0 a n.

 

Si può dimostrare che con questa definizione esistono permutazioni prime degli interi da 0 a n per qualsiasi valore di n maggiore di 1. La dimostrazione è costruttiva e si basa su quattro semplici passi.

  • Se n = p con p primo, { n, n – 1, n – 2, n – 3, …, 2, 1, 0 } è una permutazione prima di n; per esempio, una permutazione prima di 7 è { 7, 6, 5, 4, 3, 2, 1, 0 }. In particolare esistono permutazioni prime di 2 e 3.

  • Se n = p + 1 = q – 1 con p e q primi, { 2, n, n – 1, n – 2, n – 3, …, 4, 3, 0, 1 } è una permutazione prima di n; per esempio, una permutazione prima di 12 è { 2, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 0, 1 }.

  • Se esiste una permutazione prima di m, n > m e n + m = p – 1 con p primo, allora esiste una permutazione prima di n: basta concatenare alla permutazione di m gli elementi { n, n – 1, n – 2, … m + 2, m + 1 }. Per esempio, una permutazione prima di 4 è { 2, 4, 3, 0, 1 } e prendendo n = 6 abbiamo la permutazione { 2, 4, 3, 0, 1, 6, 5 }.

  • Se esistono permutazioni prime degli interi da 2 a p, dato che per il postulato di Bertrand esiste un primo q tale che p < q < 2p, allora esistono permutazioni prime per tutti gli interi n superiori fino a q – 2. Infatti, prendendo m = q – 1 – n, abbiamo che m > q – 1 – (q – 2) = 3 e m < q – 1 – p < p < n, quindi m < n e sono soddisfatte le condizioni del punto precedente.

La dimostrazione procede per induzione, aggiungendo nuovi interi all’insieme di quelli per i quali esiste una permutazione prima grazie al punto 4, tranne nel casi di due primi gemelli, nel qual caso si ricorre al punto 2.

 

Le permutazioni prime costruite come indicato sopra non sono le uniche possibili; non si conosce alcun modo per determinare il numero di permutazioni prime di un intero, se non esaminando le varie possibilità.

 

La tabella seguente mostra il numero di permutazioni prime di n, per n sino a 20 (M. Fiorentini, 2014).

n

Numero di permutazioni prime

0

0

1

0

2

1

3

3

4

5

5

11

6

13

7

93

8

76

9

472

10

1076

11

10016

12

14848

13

147024

14

99556

15

1275524

16

2060004

17

33578889

18

23893165

19

492341932

20

335098688

Il termine successivo è maggiore di 109.

 

Le permutazioni prime furono esaminate da Benjamin L. Schwartz, che propose il termine per le permutazioni degli interi da 1 a n, nelle quali k + P(k) è un numero primo per tutti i valori di k da 1 a n, contando le posizioni a partire da 1. Per esempio, una permutazione del genere degli interi da 1 a 10 è { 6, 5, 4, 3, 2, 1, 10, 9, 8, 7 }.

Per analogia con le permutazioni quadrate trovo però più corretto chiamare “permutazioni prime positive” le permutazioni di questo tipo.

 

Con una dimostrazione analoga a quella mostrata sopra, Schwartz dimostrò nel 1978 che esistono permutazioni prime positive degli interi da 1 a n per qualsiasi valore di n maggiore di zero.

 

La tabella seguente mostra il numero di permutazioni prime positive di n, per n sino a 21 (M. Fiorentini, 2014).

n

Numero di permutazioni prime positive

1

1

2

1

3

1

4

4

5

1

6

9

7

4

8

36

9

36

10

676

11

400

12

9216

13

3600

14

44100

15

36100

16

1223236

17

583696

18

14130081

19

5461569

20

158180929

21

96275344

Il termine successivo è maggiore di 109.

Bibliografia

  • Schwartz, Benjamin L.;  "Square Permutations" in Mathematics Magazine, The Mathematical Association of America, vol. 51, n. 1, gennaio 1978, pag. 64 – 66.

Contattami

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