La función totiente de Euler, también conocida como función phi de Euler (\(\phi(n)\)), es una función aritmética fundamental en la teoría de números. Calcula la cantidad de enteros positivos menores o iguales a n que son coprimos con n. A menudo, surge la necesidad de calcular esta función para un rango de números, por ejemplo, entre 10000 y 100000, de manera eficiente.
Definición de la Función Totiente de Euler
La fórmula para calcular \(\phi(n)\) se basa en la descomposición en factores primos de n. Si \( p_1,p_2,...,p_k \) son todos los divisores primos distintos de n, entonces la función se define como:
\(\phi(n) = n*\displaystyle\prod_{i=1}^{k}{(1-\displaystyle\frac{1}{p_i})}\)
Es importante notar que el número 1 no se considera primo en esta fórmula.
El Desafío de Optimización en la Implementación
Al implementar esta función para un rango extenso de números, un problema recurrente es la necesidad de determinar si un número es primo repetidamente. Un enfoque ineficiente sería recalcular la primalidad de los números cada vez que se invoca la función \(\phi(n)\). La idea principal es evitar este cálculo repetitivo. La preocupación inicial era cómo hacer que un arreglo que guarde un 1 o un 0 en cada posición, indicando si el número de esa posición es primo, sea accesible globalmente sin tener que calcularlo cada vez dentro de la función \(\phi\).
Lea también: IVA 21% Excel
Solución Propuesta: Arreglo Global y Criba de Eratóstenes
Para resolver el problema de eficiencia, la estrategia adoptada fue simplemente declarar el arreglo `primos` "afuera" de cualquier función, haciéndolo global, y construirlo en la función `main`. Esta solución funcionó satisfactoriamente desde el principio. La Criba de Eratóstenes se utiliza para precalcular todos los números primos hasta un límite (en este caso, 100000) y almacenarlos en este arreglo global. De esta manera, la información de primalidad es instantáneamente accesible para la función `phi()` sin necesidad de recálculos.
Implementación en C de la Función Totiente de Euler
A continuación se presenta el código C que implementa esta lógica para calcular la función totiente y encontrar el número de 5 cifras con el cociente \( n/\phi(n) \) máximo:
#include <stdio.h>char primos[100001]; // Declaración global del arreglo para almacenar la primalidadint phi(int x); // Prototipo de la función phiint main(){ int i, j, k, m; float max[2]; float cociente; max[0]=max[1]=0; primos[0]=primos[1]=0; // 0 y 1 no son primos // Criba de Eratóstenes para precalcular primos for(i=2; i<=100000; ++i) primos[i]=1; // Asumimos que todos son primos inicialmente for(j=2; j*j<=100000; ++j) { if(primos[j]) { // Si j es primo for(k=j*j; k<=100000; k=k+j) { primos[k]=0; // Marcamos sus múltiplos como no primos } } } // Busca el número de 5 cifras con el máximo cociente n/phi(n) for(m=10000; m<100000; ++m){ cociente = m / (float)phi(m); if(cociente > max[1]){ max[0] = m; max[1] = cociente; } } printf("Numero: %.0f\t Cociente: %f\n", max[0], max[1]); return 0;}int phi(int x){ int i, c=x, phi_val=x; // Se usa phi_val para evitar conflicto de nombre if(x==2) return 1; if(primos[x]) return x-1; // Fórmula para los primos: phi(p) = p-1 // Cálculo de phi(x) para números compuestos for(i=2; i*i<=c; ++i){ // Iteramos hasta la raíz cuadrada de c if(primos[i] && c % i == 0){ // Si i es primo y un divisor de c phi_val = phi_val / i * (i-1); // Aplicamos el factor (1 - 1/p) while(c % i == 0){ // Dividimos c por i hasta que ya no sea divisible c /= i; } } } if(c > 1){ // Si queda un factor primo mayor que la raíz cuadrada phi_val = phi_val / c * (c-1); } return phi_val;}Análisis del Código Implementado
Función main()
- Declaración Global: El arreglo `primos` se declara globalmente como `char primos[100001]`, lo que permite su acceso y uso desde cualquier parte del programa, incluyendo la función `phi()`.
- Inicialización de la Criba: La Criba de Eratóstenes se ejecuta una única vez al inicio del programa para inicializar el arreglo `primos`. Primero, se asume que todos los números son primos, y luego se marcan los múltiplos de cada primo como no primos (`0`).
- Búsqueda del Cociente Máximo: Un bucle principal itera a través de los números de 5 cifras (desde 10000 hasta 99999). Para cada número, calcula el cociente \(n/\phi(n)\) y actualiza las variables `max[0]` y `max[1]` si encuentra un cociente mayor.
- Salida: Finalmente, imprime el número que produjo el cociente máximo y el valor de dicho cociente.
Función phi(int x)
- Casos Base: Maneja el caso especial para `x=2`, que devuelve 1. Además, utiliza el arreglo `primos` para determinar si `x` es un número primo; si lo es, aplica la fórmula simplificada \(\phi(p) = p-1\).
- Factorización y Cálculo: Para números compuestos, la función factoriza `x` para encontrar sus divisores primos. Para cada factor primo `p_i` encontrado, aplica el factor \((1 - 1/p_i)\) a `phi_val` (que inicialmente es `x`). La variable `c` se usa como una copia modificable de `x` para la factorización.
- Optimización de Factorización: La factorización se optimiza iterando solo hasta la raíz cuadrada de `c`. Si después de este bucle `c` aún es mayor que 1, significa que el valor restante es un factor primo grande, y se aplica el factor correspondiente.
Consideraciones Matemáticas para la Optimización del Cociente
El ejercicio planteaba encontrar el número "n" de 5 cifras para el cual el cociente \( \displaystyle\frac{n}{\phi(n)} \) es máximo.
Es posible observar que \( \displaystyle\frac{n}{\phi(n)}=\prod_{i=1}^k \frac{p_i}{p_i - 1} \), donde \( \displaystyle n = \prod_{i=1}^k p_i^{\alpha_i} \) es la descomposición en primos de n.
De esta relación, se puede deducir que, dado que \( \frac{p_i}{p_i-1}>1 \), para maximizar el cociente \( n/\phi(n) \), conviene que el número n tenga muchos primos diferentes en su descomposición. Además, como la restricción es buscar números de 5 cifras y un primo que aparece varias veces en la factorización aporta solo una vez al cociente, se prioriza que no haya factores primos repetidos.
Lea también: Guía IVA reducido
Adicionalmente, se cumple que si \( p < q \Longrightarrow \frac{p}{p-1} > \frac{q}{q-1} \), lo que implica que conviene que en la descomposición de n aparezcan la mayor cantidad de números primos chicos posibles para maximizar el cociente.
Con todas estas consideraciones, una forma de enfocar el problema es empezar a multiplicar los primos más pequeños (2, 3, 5, 7, 11, etc.) hasta obtener el mayor número de cinco dígitos posible. Por ejemplo, el producto de los primeros primos 2*3*5*7*11*13*17 = 510510, que excede el límite de 5 cifras. Sin embargo, si se toman los primos 2*3*5*7*11*13 = 30030, se obtiene un número de 5 cifras que tiene una gran cantidad de primos pequeños distintos.
Lea también: ¿Cómo localizar tus XML del SAT?