Números amigos P65796


Statement
 

pdf   zip

thehtml

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 104 números naturales n entre 1 y 108.

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 108.

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 108.

Public test cases
  • Input

    220
    284
    6
    1
    9
    105086
    115560
    100000000
    

    Output

    220 284
    284 220
    6
    1
    9 4 3 1
    105086 52546 36158 18922 9464 12496 14288 15472 14536 14264
    115560 273240 763560 2174040 5928120 15671880 44615160 100385280
    100000000 149511591
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++