# Amicable numbers P65796

Statement

thehtml

Once, Beremiz explained to the Caliph of Baghdad:

“Let us consider the numbers 220 and 284. The divisors of 220 that are positive and less than 220 are ‍1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, and their sum is 284. The divisors of 284 that are positive and less than 284 are 1, 2, 4, 71 and 142, and their sum is 220. From this relationship, mathematicians concluded that 220 and 284 are amicable, because each one seems to honor the other.

Input

Input consists of at most 104 natural numbers n between 1 and 108.

Output

For every natural number n, let s(n) be the sum of the positive divisors of n that are less than n. Consider the sequence n, s(n), s(s(n)), s(s(s(n))), … If n is amicable, the sequence is cyclic with period 2 from its beginning. For example, for n = 220 we have 220, 284, 220, … If n is perfect, the sequence is cyclic with period 1 from the beginning. For example, for ‍n = 6 we have 6, 6, …

Generalizing, these are the three possible situations: (i) The sequence reaches a cycle (with period 1, 2 or greater) after zero or more steps. (ii) The sequence reaches 1. Taking into account that s(1) = 0, we stop the sequence. (iii) The sequence grows a lot, to the point of not knowing whether we would reach a cycle sometime or if it tends to infinity. In this problem, we will arbitrarily stop the sequence anytime it exceeds 108.

For every given n, print one line with the first terms of the sequence, stopping when some number would repeat, when we reach 1, or when we reach a number larger than 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