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

φ*(n)

Funzioni 

φ*(n) è il numero di interi positivi minori di n che non hanno divisori unitari (di n) in comune con n. Un divisore d di n si dice unitario se dn / d non hanno divisori comuni maggiori di 1.

Per convenzione si conta sempre l’unità, pertanto φ*(1) = 1 e φ*(p) = p – 1 se p è primo o potenza di un primo.

Di conseguenza, se n non è multiplo di quadrati, φ*(n) = φ(n) e in generale n > φ*(n) ≥ φ(n).

 

La funzione è moltiplicativa e può essere calcolata a partire dalla scomposizione in fattori primi dell’argomento, sapendo che se p è primo, φ*(pk) = pk – 1: se Scomposizione di n in fattori primi è la scomposizione di n in fattori primi, Calcolo di φ*(n) a partire dalla scomposizione di n in fattori primi.

 

Come la funzione φ(n), φ*(n) è molto irregolare, ma la somma dei valori ha un comportamento asintotico semplice: Limite asintotico cui tende la somma dei valori di φ*(n) divisa per n^2.

Alla voce frazioni continue si trova un’ottima approssimazione di Prodotto di 1 – 1 / (p * (p + 1)) calcolato su tutti i primi p.

 

La tabella seguente riporta i valori di φ*(n) per n fino a 20.

n

φ*(n)

1

1

2

1

3

2

4

3

5

4

6

2

7

6

8

7

9

8

10

4

11

10

12

6

13

12

14

6

15

8

16

15

17

16

18

8

19

18

20

12

 

Per n > 2, φ*(n) < n, quindi applicando ripetutamente la funzione al valore prodotto, si raggiunge 1 in un numero finito di passi 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

3

5

4

6

2

7

3

8

4

9

5

10

4

11

5

12

3

13

4

14

3

15

5

16

6

17

7

18

5

19

6

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

4

4

5

5

9

6

16

7

17

8

41

9

83

10

113

11

137

12

257

13

773

14

977

15

1657

16

2048

17

2313

18

4001

19

5725

20

7129

 

Vedi anche

Funzione φ, Funzione φ#.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.

Contattami

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