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

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 distintos lenguajes de programación

editar

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