He hecho el siguiente algoritmo para comprobar si dos enteros positivos son amistosos, y me preguntaba si podría devolver algún falso positivo, y si es así, bajo qué condiciones devolverá falsos positivos.
El algoritmo es el siguiente:
Digamos que estamos probando si $a$ y $b$ son números amistosos. Dejemos que $m=\max(a,b)$ y $s=0$ .
Bucle de $i=1$ a $m-1$ inclusive, añadir $i$ a $s$ si $a\pmod i=0$ . Entonces, reste $i$ de $s$ si $b\pmod i=0$ .
Si $|s|=m$ entonces $a$ y $b$ son números amistosos. De lo contrario, no lo son.
Sé que si $a$ y $b$ son números amistosos, entonces se garantiza que $|s|=m$ . He aquí la razón:
Dejemos que $A(n)$ sea la suma alícuota de $n$ . Supongamos que $m=b$ . Entonces el bucle pasará de $i=1$ a $b-1$ incluso.
Una vez finalizado el bucle, desde el $b\pmod i$ condición, un total de $A(b)$ se restará de $s$ y del $a\pmod i$ condición, un total de $A(a)+a$ se añadirá a $s$ . Porque $A(a)=b$ y $A(b)=a$ (por definición de números amigables), tenemos que $s=A(a)+a-A(b)=b+a-a=b$ , lo que significa que $|s|=b=m$ .
Del mismo modo, si $m=a$ , entonces después de que el bucle termine, tenemos que $s=A(a)-A(b)-b=b-a-b=-a$ , lo que significa que $|s|=a=m$ .
Tomando su contrapositivo, podemos decir que: Si $|s|\ne m$ entonces $a$ y $b$ se garantiza que no son números amistosos. Así se garantiza que no haya falsos negativos.
Pero me preguntaba: ¿Qué podemos decir si $|s|=m$ ? ¿Es posible que haya falsos positivos?
