Iterated sum-of-divisors function

Introduction

Many sequences in the OEIS are dedicated iterations of the sum-of-divisors function sigma = A000203,

$\sigma (n)=\sum _{d|n}d~,$

special case of

$\sigma _{k}(n)=\sum _{d|n}d^{k},$  multiplicative with  $\sigma _{k}(p^{e})={\frac {p^{k(e+1)}-1}{p^{k}-1}}~(=e+1{\text{ for }}k=0)~.$

In particular, $~\sigma _{0}=d=\tau =$ A000005 is the number-of-divisors function,

$\sigma _{-k}(n)=\sum _{d|n}1/d^{k}=\sigma _{k}(n)/n^{k},$  and

$\sigma (2^{n}\,m)=(2^{n+1}-1)\,\sigma (m)$  if m is odd.

Main motivation and starting points for considering this are the papers On the normal behavior of the iterates of some arithmetic functions by Erdős, Granville, Pomerance & Spiro (1990) and Iterating the sum-of-divisors function by Cohen & te Riele (1996).

Following these authors, we define

$\sigma ^{m}(n)=\sigma (\sigma ^{m-1}(n))$  for m > 0, with  $\sigma ^{0}(n)=n$

for the m-fold iterate of the sigma function.

(m,k)-perfect numbers

Let us also recall that perfect numbers (A000396) are such that $\sigma (n)=2\,n$. This is the special case k = 2 of more general k-perfect numbers such that $\sigma (n)=k\,n$. We will consider the even more general (m,k)-perfect numbers such that

$\sigma ^{m}(n)=k\,n$.

As we will see in the sequel, any n is an (m,k)-perfect number for some integers m and k. In the following we will find the smallest such m.

Iterated sigma is a multiple of the starting value

In particular, we are interested in the first m > 0 such that, for given n, $\sigma ^{m}(n)$ is again divisible by n. We have in the OEIS the following related sequences:

m(n) = number of iterations of sigma required to reach a multiple of n when starting with n:

A019294 = (1, 2, 4, 2, 5, 1, 5, 2, 7, 4, 15, 3, 13, 3, 2, 2, 13, 4, 12, 5, 2, 13, 16, 2, 17, 4, 9, 1, 78, ...)

k(n) = ratio sigma(sigma(...(sigma(n))...) / n, where sigma is iterated until a multiple of n is reached, i.e., m(n) = A019294(n) times:

A019295 = (1, 2, 5, 2, 24, 2, 24, 3, 168, 12, 1834560, 10, 84480, 12, 4, 2, 92520, 20, 62720, 84, 3, 49920, 6516224, ...)

Megaperfect numbers: numbers n where m(n) = A019294(n) increases to a new record value:

A019276 = (1, 2, 3, 5, 9, 11, 23, 25, 29, 59, 67, 101, 131, 173, 202, 239, 353, 389, 401, 461, 659, 1319, 1579, 1847, 2309, 2797, ...)

Record values of m(n) = A019294(n):

A019277 = (1, 2, 4, 5, 7, 15, 16, 17, 78, 97, 101, 120, 174, 214, 239, 261, 263, 296, 380, 557, 1287, 1524, 1722, 1911, 2023, 2373, ...)

In general one finds that the iterates of the sigma function grow quite fast. As a consequence, although the record values of A019294 (listed in A019277) grow only moderately, as do the indices (a.k.a. megaperfect numbers A019276) where these record occur, this is not the case for the corresponding ratios k = A019295(A019276),

A331035 = (1, 2, 5, 24, 168, 1834560, 6516224, 881280, 517517500266693633076805172570524811961093324800, ...)

the next terms have 65, 67, 80, 127, 161, 185 and 205 digits!

See also

• ...

Authorship

M. F. Hasler, Iterated sum-of-divisors function.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Iterated_sum-of-divisors_function], Initial version written Jan 15 2020