Números Amigos

A todos nos resulta familiar el conjunto de los números naturales o el conjunto de los números enteros, aunque a algunos niños cueste tanto trabajo dominar cuando se introducen los enteros negativos, en fin, los conjuntos de números más comunes, que conocemos como $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ o $\mathbb{C}$. Pero hay más formas de clasificar a los números, como por ejemplo en números hambrientos, números vampiros, números narcisistas, etc… que cumplen ciertas características que los hacen peculiares (Gaussianos tiene una entrada muy buena sobre estos tipos de números).

Una de estas tantas clasificaciones peculiares son los números amigos. Una pareja de números amigos son dos números enteros positivos a, b tales que a es la suma de divisores propios de b y b es la suma de divisores propios de a, con a diferente de b (cuando a=b se les llama números perfectos o amigos de sí mismos).

La verdad es que de nuevo, me encontré con ellos en un problema de Project Euler, en el cual se dice:

Sea d(n) la suma de divisores propios de n. Si d(a)=b y d(b)=a, donde a≠b, entonces (a,b) es una pareja amigable y tanto a como b se llaman números amigos.

Los números amigos al parecer se conocen desde la época de Pitágoras y desde entonces han sido objeto de estudio de los matemáticos, de los cuales Euler participó en la generalización de una regla para obtenerlos aunque al parecer no funciona para cualquier número y da al menos dos parejas que no son números amigos.

Aún más sutil es el caso de las parejas regulares de números amigos. Sean (a,b) una pareja amigable con a<b y sea w el mayor común divisor de esta pareja tal que a=Aw y b=Bw. Si A y B son primos relativos y libres de cuadrados, producto de i y j factores primos, respectivamente, entonces la pareja (a,b) es regular y se dice que es de tipo (i,j). Si esto no se cumple simplemente se dice que son irregulares.

El ejemplo más sencillo a exponer sería el de la primer pareja de números amigos: (220,284). Usando el enunciado del problema de Project Euler: podemos notar que los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110; así entonces, d(220)=284. Los divisores propios de 284 son 1, 2, 4, 71 y 142; entonces d(284)=220. Además de esto, notamos que el mayor común divisor de ambos es w=4, entonces nota que A=55, B=71, los cuales son primos relativos y libres de cuadrados, producto de 2 y 1 factores primos, A=11$\times$5 y B=71, entonces (a,b)=(${4\times11\times5}$, ${4\times71}$), esto es, la pareja (220,284), es una pareja amigable regular de tipo (2,1). Esta pareja es la más antigua conocida y no hay pareja alguna anterior a ella.

Una forma usada para encontrar números amigos, números perfectos y números sociales es la sucesión alícuota en la que cada término es la suma de los divisores propios del término anterior. Apenas con el advenimiento de las computadoras se ha potencializado la búsqueda de números amigos y ya se conocen millones de ellos.

Bueno pues comparto el enunciado completo del problema de Project Euler y un código en Java que soluciona el problema. No hice nada extraordinario y el programa funciona bien para números amigables debajo de 100,000 tardando a lo mucho 1 minuto.

****¿Puedes realizar un programa que diga cuándo un par amigable es regular y de qué tipo?

Problema 21 (Project Euler):

Sea d(n) la suma de divisores propios de n (números estrictamente menores que n que dividen exactamente a n). Si d(a)=b y d(b)=a, donde a≠b, entonces a y b es una pareja amigable y tanto a como b se llaman números amigos. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110; así entonces, d(220)=284. Los divisores propios de 284 son 1, 2, 4, 71 y 142; entonces d(284)=220. Evalúa la suma de todos los números amigos menores a 10000.

public class euler21
{
  public static void main(String[] asrg)
  {
     final int MAX=100000;
     int a[],i,j,x=0;
     long s1=1,s2=1,t=0;
     a=new int[MAX];
     for(i=6;i<MAX;i++,s1=1,s2=1)
     {
         for(j=2;j<=(i/2);j++)
         { if(i%j==0) {s1+=j;} }
         for(j=2;j<=(s1/2);j++)
         { if(s1%j==0) {s2+=j;} }
         if(s2==i && s2!=s1) {a[x]+=i;x++;}
     }
     System.out.println("Los numeros amigos debajo de "+MAX+" son:");
     for(i=0;a[i]!=0;i++)
     {
         t+=a[i];
         System.out.println(a[i]);
     }
     System.out.println("\nSe encontraron en total "+i+"numeros amigos");
     System.out.println("Y la suma de numeros amigos debajo de "+MAX+" es: "+t);
  }
}