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

Indice

  1. 1. Pagina principale
  2. 2. Formule
  3. 3. Valori
  4. 4. Progressioni aritmetiche di interi con lo stesso valore della funzione φ
  5. 5. Iterazioni della funzione

Per n > 2, φ(n) < n, quindi applicando ripetutamente la funzione al valore prodotto, si raggiunge 1 in un numero finito di passi.

Se c(n) è il numero di passi necessari per arrivare a 1 o 2 a partire da n, Harold Shapiro dimostrò nel 1943 che:

  • c(xy) = c(x) + c(y), se almeno uno tra x e y è dispari;

  • c(xy) = c(x) + c(y) + 1, se x e y sono entrambi pari;

  • il massimo intero pari m per il quale c(m) = n è 2 • 3n;

  • il tre massimi interi dispari m per il quale c(m) = n sono, in ordine decrescente, 3n, 7 • 3n – 2 e 19 • 3n – 3;

  • il minimo intero dispari m per il quale c(m) = n è maggiore di 2n;

  • il minimo intero pari m per il quale c(m) = n è 2n + 1;

  • se c(n) < log(2) / log(3), n è pari, ma non multiplo di 8;

  • non esistono interi dispari n tali che 7 • 3c(n) – 2 < n < 3c(n);

  • non esistono interi dispari n tali che 19 • 3c(n) – 3 < n < 7 • 3c(n) – 2;

  • per p primo e diverso da 5, p > 43 • 3c(p) – 4 se e solo se p = 2 • 3c(p) – 1 + 1;

  • per p primo 5, 43 • 3c(p) – 4 > p > 39 • 3c(p) – 4 se e solo se p = 2 • 7 · 3c(p) – 3 + 1;

  • c(2n + 1) = n se e solo se 2n + 1 è un primo di Fermat.

 

Shapiro avanzò la congettura che per ogni valore di k, il minimo intero n tale che c(n) = k sia un numero primo, ma W.H. Mills dimostrò nel 1943 che in vari casi n è composto.

P.A. Catlin dimostrò nel 1970 che se M è l’insieme di tali minimi e n è dispari e appartiene a M, tutti i fattori primi di n appartengono a M.

 

Il numero di passi w(n) necessari per arrivare a 1 iterando la funzione φ è c(n) + 1 per n > 1.

S.S. Pillai dimostrò nel 1929  che Limiti inferiore e superiore per w(n).

La tabella seguente mostra i valori di w(n), per n fino a 20.

n

w(n)

1

0

2

1

3

2

4

2

5

3

6

2

7

3

8

3

9

3

10

3

11

4

12

3

13

4

14

3

15

4

16

4

17

5

18

3

19

4

20

4

 

La tabella seguente mostra i minimi interi per i quali il valori di w(n) sia uguale a k, per k fino a 20 (Pepijn van Erp e David W. Wilson, The Online Encyclopedia of Integer Sequences http://oeis.org).

w(n)

Minimo intero

0

1

1

2

2

3

3

5

4

11

5

17

6

41

7

83

8

137

9

257

10

641

11

1097

12

2329

13

4369

14

10537

15

17477

16

35209

17

65537

18

140417

19

281929

20

557057

 

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • De Koninck, Jean-Marie;  Those Fascinating Numbers, American Mathematical Society, 2009 -

    Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
  • Surányi, János;  Topics in the Theory of Numbers, Springer, 2003.
  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

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