Recursion involving the Divisor Function

Interesting results arise when we consider the following iterative process involving a starting number \(n\):$$ \begin{align} n&=\frac{n}{\sigma(n,0)} \text{    if } n \equiv 0  \! \! \! \mod \sigma(n,0)\\ n&=n+\sigma(n,0) \text{    if } n \not \equiv 0 \! \! \! \mod \sigma(n,0) \end{align}$$This has the effect of quickly reducing the size of the number when it is divisible by the number of its divisors and increasing the number slightly in the case where it is not divisible before trying again.

Let's consider what happens to the number 42 under this recursive process:

• 42 has 8 divisors [1, 2, 3, 6, 7, 14, 21, 42]
  42 isn't divisible by 8, so 42 --> 42 + 8 = 50
  
  
• 50 has 6 divisors [1, 2, 5, 10, 25, 50]
  50 isn't divisible by 6 so 50 --> 50 + 6 = 56
  
  
• 56 has 8 divisors [1, 2, 4, 7, 8, 14, 28, 56]
  8 does divide into 56 to give 7
  
  
• 7 has 2 divisors [1, 7]
  7 isn't divisible by 2 so 7 --> 7 + 2 = 9
  
  
• 9 has 3 divisors [1, 3, 9]
  3 does divide into 9 to give 3
  
  
• 3 has 2 divisors [1, 3]
  3 isn't divisible by 2 so 3 --> 3 + 2 = 5
  
  
• 5 has 2 divisors [1, 5]
  5 isn't divisible by 2 and so 5 --> 5 + 2 = 7

Thus the trajectory of 42 ends in a loop because 5 takes us back to 7. The trajectory is thus 42, 50, 56, 7, 9, 3, 5. All trajectories end in this loop as far as I can determine. In this case, the number of steps is 6 and the trajectory has 7 members when including the starting number.

As usual, it's interesting to look for those numbers that have trajectories of record length. What I found in the range up to 30,000 was the following (SageMathCell permalink):

1, 2, 3, 4, 6, 11, 27, 216, 224, 227, 425, 815, 1641, 13244, 19305, 19317 

These numbers corresponded to trajectories of the following lengths:

1, 2, 4, 5, 8, 16, 75, 77, 78, 105, 275, 282, 951, 952, 1393, 1396

Figure 1 shows these results in tabular format. 

Figure 1

What's surprising is that a relatively small number like 19317 can have a trajectory length of 1396. It's interesting to look at the trajectory of this number. Figure 2 is a plot of the trajectory lengths.

Figure 2

Looking at Figure 2, we see how there is steady buildup until a number (27252) that is divisible by its number of divisors (18) and then there is a precipitous drop to 1514 and the same process is repeated on a smaller scale for what looks like two more times. 

We can see the same process at work a little more clearly for 27 that has a record length of 75. See Figure 3.

Figure 3

Here is the full trajectory of 27 that ends in the 7, 9, 3, 5 loop:

27, 31, 33, 37, 39, 43, 45, 51, 55, 59, 61, 63, 69, 73, 75, 81, 86, 90, 102, 110, 118, 122, 126, 138, 146, 150, 162, 172, 178, 182, 190, 198, 210, 226, 230, 238, 246, 254, 258, 266, 274, 278, 282, 290, 298, 302, 306, 318, 326, 330, 346, 350, 362, 366, 374, 382, 386, 390, 406, 414, 426, 434, 442, 450, 25, 28, 34, 38, 42, 50, 56, 7, 9, 3, 5