Implementación de algoritmos de teoría de números/Función φ de Euler

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

La función φ de Euler (también llamada función indicatriz de Euler) es una función importante en teoría de números. Si n es un número natural, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n, es decir, formalmente se puede definir como:

donde |·| significa la cantidad de números que cumplen la condición.

El valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si

donde los pj son números primos distintos, entonces

Esta última fórmula es un producto de Euler y a menudo se escribe como

donde los p son los distintos primos que dividen a n.

Descripción formal[editar]

Versión iterativa[editar]

De la definición general,

y tomando por convenio que φ(0)=1, se obtiene la versión iterativa.

función 
  devolver  si 
  
  para  hacer
      si    
  devolver 

Esta versión tiene fácil implementación en una computadora, pero no es eficiente para valores grandes de n.

Versión por factorización[editar]

Se basa en la definición de la función mediante el producto de Euler

y utiliza algún algoritmo de factorización eficiente de propósito general como puede ser la criba general del cuerpo de números (GNFS).

Implementación en Matlab/Octave[editar]

En Matlab/Octave el algoritmo queda como sigue. Esta función gráfica los primeros m valores de la función (solo depende del número m).

function [] = phi(m),
con=0;
l=zeros(m,1);

for i=1:1:m,

	for j=1:1:i,
		if(gcd(i,j) == 1)
			con++;
		endif
	endfor

	l(i)=con;
	con=0;
endfor

plot(1:m,l,'.');

endfunction

Referencias[editar]

  • Octavian Cira, Florentin Smarandache, Solving Diophantine Equations, Infinite Study, ISBN 1599733072, pp:64-68