Aliquot sequence

From FMNWiki
Jump to: navigation, search

Constructing an aliquot sequence is simple:

  1. s_0=n\in\N
  2. sn = σ1(sn − 1) − sn − 1

where σx is the sum of divisors function.

Here's an example, starting with 12: 

12
σ(12) − 12 = (1 + 2 + 3 + 4 + 6 + 12) − 12 = 16
σ(16) − 16 = (1 + 2 + 4 + 8 + 16) − 16 = 15
σ(15) − 15 = (1 + 3 + 5 + 15) − 15 = 9
σ(9) − 9 = (1 + 3 + 9) − 9 = 4
σ(4) − 4 = (1 + 2 + 4) − 4 = 3
σ(3) − 3 = (1 + 3) − 3 = 1
σ(1) − 1 = (1) − 1 = 0

Most of these sequences end in 0; some end in a repeating pattern (of one, two, three, or more numbers).

Perfect numbers repeat themselves: 

6, 6, ...

Amicable numbers repeat in pairs: 

220, 284, 220, ...

Sociable numbers repeat larger sequences: 

1264460, 1547860, 1727636, 1305184, 1264460, ...

12496, 14288, 15472, 14536, 14264, 12496, ...

14316, 19116, 31704, 47616, 83328, 177792, 295488, 629072, 589786, 294896, \
358336, 418904, 366556, 274924, 275444, 243760, 376736, 381028, 285778, 152990, \
122410, 97946, 48976, 45946, 22976, 22744, 19916, 17716, 14316, ...

Aspiring numbers start as one and "devolve" into one of the above: 

95, 25, 6, 6, ...

The Catalan Conjecture states that every aliquot sequence ends like the above, but there are several numbers with sequences that have not been fully determined.

The Next Number

The fundamental theorem of arithmetic states n=\prod_{i=0}^r p_i^{a_i}

where p is the set of prime factors of n and a is the set of their multiplicities (e.g. for 12, p = 2,3, a = 2,1). σx(n) can then be calculated as follows:

\sigma_x(n)=\prod_{i=0}^r {{p_i^{(a_i+1)x}-1} \over {p_i^x-1}}

This is much faster than checking every number d between 1 and n to see if d | n.

The reason work on some sequences is slow is that factoring numbers is difficult, and the full factorization of a number must be known to calculate the next number in the sequence. As I write this, the 1720th number in the sequence starting with 276 has a known divisor of a 162-(decimal)-digit number, 1262158219...7, but its divisors are currently not known. It is estimated that factoring this number, even with the fastest known factorization method (GNFS), would take approximately a month using a standard desktop computer.

Retrieved from "http://www.findingmyname.com/wiki/index.php/Aliquot_sequence"
Personal tools