Di nuovo irriducibili (Editoriale)

Il numero di frazioni proprie irriducibili $p/n$ (con denominatore $n$) è uguale al numero di numeri naturali $p$ tali che p < n e $p$ è coprimo con $n$. Tale numero di valori $p$ è uguale alla funzione di Eulero $\phi (n)$.

Consideriamo l'insieme di tutte le frazioni proprie con denominatore $12$:

Dopo aver ridotto le frazioni alla forma irriducibile otteniamo:

Ora raggruppiamo queste frazioni in base ai loro denominatori:

Tra questi denominatori compare ogni divisore $d$ del numero $12$ insieme a tutti i $\varphi (d)$ numeratori coprimi con $d$. In altre parole, per ogni divisore $d$ del numero $12$ esistono esattamente $\varphi (d)$ frazioni irriducibili con denominatore $d$.

Poiché dopo la riduzione ogni frazione dell'insieme iniziale compare esattamente una volta, otteniamo:

In generale, se partiamo dalla sequenza di frazioni proprie

e riduciamo ogni frazione alla forma irriducibile, otteniamo la seguente identità:

Esempio

Per n = 12 ci sono \varphi(12) = 4 frazioni proprie irriducibili:

Implementazione dell'algoritmo

La funzione euler calcola il valore di $\phi (n)$.

int euler(int n)
{
  int i, result = n;
  for (i = 2; i * i <= n; i++)
  {
    if (n % i == 0) result -= result / i;
    while (n % i == 0) n /= i;
  }
  if (n > 1) result -= result / n;
  return result;
}

La parte principale del programma. Leggiamo il valore di input $n$ e stampiamo $\phi (n)$.

while(scanf("%d",&n),n)
  printf("%d\n",euler(n));

Implementazione in Java

import java.util.Scanner;

public class Main
{
  static int euler(int n)
  {
    int result = n;
    for(int i = 2; i * i <= n;i++)
    {
      if (n % i == 0) result -= result / i;
      while (n % i == 0) n /= i;
    }
    if (n > 1) result -= result / n;
    return result;
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      int n = con.nextInt();
      if (n == 0) break;
      System.out.println(euler(n));
    }
    con.close();
  }
}

Implementazione in Python

import math

La funzione euler calcola il valore di $\phi (n)$.

def euler(n):
  result = n
  i = 2
  while i <= math.isqrt(n):
    if n % i == 0:
      result -= result // i
      while n % i == 0: n //= i
    i += 1
  if n > 1: result -= result // n
  return result

La parte principale del programma. Leggiamo il valore di input $n$ e stampiamo $\phi (n)$.

while True:
  n = int(input())
  if n == 0: break
  print(euler(n))