PROBLEM STATEMENT
For a number n, we define s(n) to be the sum of the aliquot parts of n, i.e.,
the sum of the positive divisors of n, excluding n itself: so, for example,
s(8)=1+2+4=7, and s(12)=1+2+3+4+6=16. If we start at some number, say 15, and
apply s repeatedly, we will form a sequence: s(15)=1+3+5=9, s(9)=1+3=4,
s(4)=1+2=3, s(3)=1, s(1)=0. This sequence - 15,9,4,3,1,0 - is called an aliquot
sequence of a number 15.
The scientists distinguish four possibilities for the behavior of aliquot
sequences:
1. It can terminate at 0 like the example above.
2. It can terminate at a fixed number. For example, s(25)=6, s(6)=6, and so on.
(Note: 6 is called a PERFECT number and 25 is called an ASPIRING number).
3. It can fall into a cycle. For example, s(220)=284, s(284)=220, and so on.
(Note: strictly speaking the first and the second possibilities are cycles of
length 1, but they are considered separate for historical reasons. Numbers 220
and 284 are called an AMICABLE PAIR.).
4. It can grow without bound and approach infinity. (Note: many mathematicians
are trying to prove Catalan's conjecture that no number belongs to case 4; but
this is remains unproved. The smallest number for which the aliquot sequence
isn't known to terminate or fall into a cycle is 276)
Your task is, given an integer, calculate the next 35 elements of its aliquot
sequence and describe the behavior of the sequence. In more detail, you will
output two numbers. The first number will indicate the index of an element of
the sequence at which it terminates at zero or another number, or the first
occurence of a number from a cycle. The second number will be the actual
element of the sequence with the index given by the first number. If the
sequence doesn't terminate at 0 or another number, or doesn't fall into a cycle
judging by its first 36 elements (the input number plus the next 35 elements),
return {-1, -1}.
NOTES
- the input number is considered to be the zeroth element of the sequence, you
need to calculate 35 more elements of the sequence
- the long data type is a 64-bit signed integer. Note for C++ coders: The long
data type is specific to the gcc compiler
- TopCoder guarantees that all the return values will, in fact, fit inside the
int type
- a number k is a divisor of N if k is a positive integer and there exists a
positive integer m such that k*m = N
- if the number N>1 is a square of some number k: N = k*k, then k is a divisor
of N. The number k should be included once in the sum of the divisors.
DEFINITION
Class: Aliquot
Method: behavior
Parameters: int
Returns: int[]
Method signature (be sure your method is public): int[] behavior(int num);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- num is between 1 and 1000 inclusive
EXAMPLES:
1. num = 17, s(17)=1, s(1)=0, the aliquot sequence for 17 is {17, 1, 0, 0,
...}, return {2,0}
2. num = 25, s(25)=6, s(6) = 6, the aliquot sequence for 25 is {25, 6, 6, 6,
...}return {1,6}
3. num = 220, the aliquot sequence for 220 is {220, 284, 220, 284, ...} return
{0,220}
4. num = 840, return {-1,-1}
5. num = 15, s(15)=9, s(9)=4, s(4)=3, s(3)=1, s(1)=0, the aliquot sequence for
15 is {15, 9, 4, 3, 1, 0, 0,...}, return {5,0}