Números amigos P65796

Una vez, Beremiz le explicó al califa de Bagdad:

“Consideremos los números 220 y 284. Los divisores de 220 positivos y menores que 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110, y su suma es 284. Los divisores de 284 positivos y menores que 284 son 1, 2, 4, 71 y 142, y su suma es 220. De esta relación los matemáticos llegaron a la conclusión de que 220 y 284 son amigos, porque cada uno de ellos parece honrar al otro.”

Entrada

La entrada consiste en como mucho 10⁴ números naturales n entre 1 y 10⁸.

Salida

Para cada natural n, sea s(n) la suma de los divisores positivos de n que son menores que ‍n. Consideremos la sucesión n, s(n), s(s(n)), s(s(s(n))), … Si n tiene un amigo, la sucesión es cíclica de periodo 2 desde su inicio. Por ejemplo, para n = 220 tenemos 220, 284, 220, … Si ‍n es perfecto, la sucesión es cíclica de periodo 1 desde su inicio. Por ejemplo, para n = 6 tenemos 6, 6, …

Generalizando, éstas son las tres situaciones posibles: (i) La secuencia alcanza un ciclo (de periodo 1, 2 o mayor) después de cero o más pasos. (ii) La secuencia llega al número 1. Teniendo en cuenta que s(1) = 0, paramos la secuencia. (iii) La secuencia crece mucho, hasta el punto de no saber si alcanzará un ciclo en algún momento, o si tiende a infinito. En este problema, arbitrariamente pararemos la secuencia si en algún momento se supera el número 10⁸.

Para cada n dado, escribid una línea con los primeros términos de su secuencia, parando cuando se repetiría algún número, cuando se llegue a 1, o cuando se pase de 10⁸.