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

Admirable Numbers and Compatible Numbers

Yesterday I turned 25446 days and this number was identified by Numbers Aplenty as an admirable number, defined as a number \(n\) for which there exists a divisor \(d\) of \(n\) such that \(2n = \sigma(n)-2d\). In other words, \(n\) is equal to the sum of its proper divisors, where one of them has a minus sign.

For 25446, the divisors are: 1, 2, 3, 6, 4241, 8482, 12723, 25446 and the sum of these divisors is 50904. However, 50904 - 2 x 6 = 50892 = 2 x 25446 and here the divisor 6 has been assigned the minus sign. The modified divisors (1, 2, 3, -6, 4241, 8482, 12723) now add to 25446. The previously mentioned website goes on to say that:

Clearly, admirable numbers are a subset of abundant numbers and they are infinite because, for example, all the numbers 6\(p\), with \(p\)>3 prime, are admirable. The largest number that cannot be written as a sum of admirable numbers is 1003. Pairs of consecutive admirable numbers are rarer than pairs of consecutive abundant numbers. Up to \(10^{12}\), there are only two such pairs, namely 29691198404, 29691198405 and 478012798575, 478012798576.

On the other hand, pairs of admirable numbers that differ by two are more common but still sparse. There are 72 such pairs up to 27000.

 

The smallest 3 x 3 magic square made up of admirable numbers is shown in Figure 1.

Figure 1: smallest possible magic square
made from admirable numbers

OEIS A111592 lists the initial admirable numbers:

12, 20, 24, 30, 40, 42, 54, 56, 66, 70, 78, 84, 88, 102, 104, 114, 120, 138, 140, 174, 186, 222, 224, 234, 246, 258, 270, 282, 308, 318, 354, 364, 366, 368, 402, 426, 438, 464, 474, 476, 498, 532, 534, 582, 606, 618, 642, 644, 650, 654, 672, 678, 762, 786, 812, ...

These numbers are related to Zumkellar, Half-Zumkellar and pseudoperfect numbers in that they all involve the divisors of the number. See my blog post on these sorts of numbers.

In the OEIS comments, we read that "the concept of admirable numbers was developed by educator Jerome Michael Sachs (1914-2012) for a television in-service training course in mathematics for elementary school teachers." Here is the link to the article that he wrote in The Arithmetic Teacher, Vol. 7, No. 6 (1960), pp. 293-295. However, in that article he allows more than one of the divisors of a number to be negative. For example, he writes 24 as being equal to the following algebraic sum of its divisors: 4+6+8+12-1-2-3. However, this is the same as 1+2+3+4+8+12-6 so it's not clear whether a sum involving multiple negative divisors is always equivalent to another sum involving a single negative divisor.

Sachs also introduces the notion of a compatible number pair as an extension or relaxation of the concept of an amicable number pair. For example, 220 and 284 are an amicable pair because the proper divisors of each add to the other number. The proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 and these add to 284. The proper divisors of 284 are 1, 2, 4, 71 and 142 and these add to 220. In such cases, the smaller number is abundant and the larger number deficient.

Sach's proposal for a compatible number pair is two numbers such that the algebraic sums of their divisors each leads to the other number. For example:

• 30 has divisors of 1, 2, 3, 5, 6, 10, 15
• 40 has divisors of 1, 2, 4, 5, 8, 10 and 20
• 40 = 2 + 3 + 5 + 6 + 10 + 15 - 1
• 30 = 1 + 2 + 4 + 5 + 8 + 20 - 10

So he defines 30 and 40 as compatible numbers.

The smaller members of such pairs are listed in OEIS A109797 while the larger members are listed in OEIS A109798.

Here is the SageMath code to generate the admirable numbers between 25000 and 26000

Duffinian Numbers

Duffinian numbers are defined as numbers that are composite and relatively prime to the sum of their divisors. The first such number is 4 because it is composite and the sum of its divisors (1, 2 and 4) is 7 and relatively prime to 4. The next composite number is 6 whose sum of divisors (1, 2, 3 and 6) is 12. However, since 12 and 6 are not relatively prime it is not Duffinian. The next composite number is 8 with divisors 1, 2, 4 and 8 whose sum is 15 and thus relatively prime to 8. Thus the first two Duffinian numbers are 4 and 8.

The first Duffinian numbers up to 247 are:

4, 8, 9, 16, 21, 25, 27, 32, 35, 36, 39, 49, 50, 55, 57, 63, 64, 65, 75, 77, 81, 85, 93, 98, 100, 111, 115, 119, 121, 125, 128, 129, 133, 143, 144, 155, 161, 169, 171, 175, 183, 185, 187, 189, 201, 203, 205, 209, 215, 217, 219, 221, 225, 235, 237, 242, 243, 245, 247

Since there are 59 numbers listed above, their density is 59/247 or nearly 24%. Thus they are more common than the prime numbers that occur with a frequency of around 18% in the same interval. There is an infinity of such numbers. As explained in Numbers Aplenty:

Any number of the form  \( p^k \)  where  \( p \)  is prime and  \( k \ge 2 \)  is Duffinian, since  \( \sigma(p^k)=1+p+p^2+\cdots+p^k \)  cannot be divisible by \(p \).

Of course, every prime \( p \) is relatively prime to the sum of its divisors \( p+1 \) but by definition the prime numbers are excluded. However, OEIS A014567 lists numbers \(n \) such that \( n \) and \( \sigma(n) \) are relatively prime, without \( n \) needing to be composite. Such numbers are sometimes called sigma primes and of course include all the primes. OEIS A003624 lists the Duffinian numbers.

Numbers Aplenty goes on to say that:

P. Heichelheim proved that there exists a run of five consecutive Duffinian numbers starting at 202605639573839041, and that there cannot exist a longer such run. 

Rose Mary Zbiek has proved that every even Duffinian number is either a square or twice a square. 

The smallest 3 × 3 magic square whose entries are consecutive Duffinian numbers is:

It's a simple enough matter in SAGE to determine whether or not a number is Duffinian. Here is the code (with "gcd" standing for "greatest common divisor"):

number=25387
if gcd(number,sigma(number,1))==1:
    print number, "is Duffinian"
else:
    print number, "is not Duffinian"

The input 25387 produces the output: 25387 is Duffinian

Sums of Cubes and Squares of Sums

Today I turned 25321 days old, a prime number of days, and a prime with the property that the sum of the cubes of its digits equals the square of the sum of its digits. In other words:$$2^3+5^3+3^3+2^3+1^3 = (2+5+3+2+1)^2 = 169$$This prime is a member of OEIS A225567: Primes with nonzero digits such that sum of cubes of digits equal to square of sums. It's initial members are:$$1423, 2143, 2341, 4231, 12253, 21523, 22153, 22531, 23251, 25321, ...$$Serendipitously I then rediscovered the old and famous connection between the sum of the cubes of the first n natural numbers and the square of the sum of these some numbers, specifically:$$ \sum_1^n i^3=\big (\sum_1^n i \big)^2$$It's easy to see why the first four members of the sequence (1423, 2143, 2341 and 4231 are members) because these are simply instances of:$$1^3+2^3+3^3+4^3=(1+2+3+4)^2$$I also discovered a similar relationship involving the divisors \(d_i \) of any natural number with \(n\) divisors, namely that:$$ \sum_1^n (\sigma_0(d_i))^3=\big(\sum_1^n \sigma_0(d_i) \big) ^2$$The previous looks more difficult than it actually is and a simple example will assist. Let's consider the number 10. It has four divisors 1, 2, 5 and 10. Each of these divisors has 1, 2, 2 and 4 divisors respectively. We find that:$$1^3+2^3+2^3+4^3=(1+2+2+4)^2 = 81$$It's as simple as that and it applies to every natural number. Of course 1224 and permutations of these digits can be found in OEIS A227073: Positive numbers without the digit 0 such that sum of cubes of the digits equals the square of the sum of the digits. The initial members of this sequence are:$$ 1, 12, 21, 22, 123, 132, 213, 231, 312, 321, 333, 1224, ...$$

Number of Divisors

I came across this formula for calculating the number of divisors of a given number:$$ \sigma_0(n)=\prod_{i=1}^r(a^i+1)$$ where \(r\) is the number of distinct prime factors and \(a^i\) are their coefficients. For example, $$\sigma_0(24)=\prod_{i=1}^2(a^i+1)=(3+1)(1+1)=8$$where \(r\) = 2 because there are two distinct prime factors (2 and 3) with indices of 3 and 1 respectively.

There are indeed eight factors of \( 24: 1, 2, 4, 8, 3, 6, 12, 24 \) so this is a quick and easy way to calculate the number of factors based on prime factors of a number and the degrees to which each of them are raised. It's similar to the formula for calculating the number of ways in which a number can be written as the sum of two squares viz.:

The fundamental theorem on sums of two squares is:

Let \(n=2^kp_1^{a_1} \dots p_r^{a_r}q_1^{b_1} \dots q_s^{b_s}\) , where the \( p_i  \) are distinct primes with \( p_i \equiv 1 \pmod{4} \) and the \( q_i \) are distinct primes with \( q_j \equiv 3 \pmod{4} \). Then \(n \) is the sum of two squares if and only if all the \( b_j \) are even. In that case, the number of distinct solutions is $$ \lceil \frac{\scriptstyle{1}}{\scriptstyle{2}} (a_1+1)(a_2+1) \dots (a_r+1) \rceil $$ where \( \lceil x \rceil \) is the ceiling function, the smallest integer greater than or equal to \( x \).

Of course by this rule, \(24\) cannot be written as a sum of two squares because it has a \(4k+3\) factor (\(3\)), raised to an odd power (\(1\)). However, \(25=5^2 \) has no \(4k+3 \) factors and its \(4k+1\) factor (\(5\)) is raised to the \(2nd\) power. This means that it can be written as the sum of two squares in two distinct ways because \( \lceil \frac{1}{2}(2+1) \rceil =2 \). The two ways are \( 5^2+0^2 \) and \(4^2+3^2 \).

Getting back to the number of divisors however, the formula quoted is actually part of a more general formula (as explained in Wikipedia):

The divisor function is multiplicative, but not completely multiplicative.  The consequence of this is that, if we write $$n = \prod_{i=1}^r p_i^{a_i}$$ where \( r=\omega (n) \) is the number of distinct prime factors of \(n \), \(p_i \) is the \(i\)th prime factor, and \(a_i \) is the maximum power of \(p_i \) by which \(n\) is divisible, then we have $$\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}$$ which is equivalent to the useful formula:$$ \sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} =
\prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}).$$ It follows (by setting \(x = 0 \)) that \(d(n) \) is: $$\sigma_0(n)=\prod_{i=1}^r (a_i+1).$$

Deficient Numbers

Sometimes it's easy to forget the basics, such as what defines a deficient number. For example, today's number 25137 has the following entry in OEIS: deficient numbers n having a companion m > n such that sigma(n)/n = sigma(m)/m. The initial numbers in this sequence are shown below:

135, 3375, 1485, 2295, 2565, 3105, 3915, 4185, 4995, 5535, 5805, 6345, 25137, 7155, 7965, 8235, 9045, 9585, 9855, 10665, 11205, 12015, 13095, 13635, 13905, 14445, 14715, 43875, 15255, 16335, 17145, 17685, 18495, 18765, 57375, 20115, 20385, 21195, 64125

These numbers are listed in the order that their companions were found. All these numbers appear to have only one companion, which appear in A212609. The initial entries in this sequence are shown below with the 13th entry marked, namely 40131, because 25137 is the 13th entry in the previous set of numbers:

819, 6975, 9009, 13923, 15561, 18837, 23751, 25389, 30303, 33579, 35217, 38493, 40131, 43407, 48321, 49959, 54873, 58149, 59787, 64701, 67977, 72891, 79443, 82719, 84357, 87633, 89271, 90675, 92547, 99099, 104013, 107289, 112203, 113841, 118575, 122031

So the companion for 25137 is 40131 and checking we find that: $$ \frac {\sigma(25137)}{25137}=\frac{\sigma(40131)}{40131} \approx 1.81406 $$However, just to remind myself about the distinction between deficient, perfect and abundant numbers, I've included the following graphic:

By now the sigma function has begun to sink into my long term memory along with the Euler totient function or phi function as it's sometimes known.

Abundant Numbers

Today's numbered day is 24762 and one of its claims to fame, according the OEIS, is its membership in A228964: smallest sets of 7 consecutive abundant numbers in arithmetic progression. The initial abundant number is listed. The abundant numbers forming this arithmetic sequence are 24762 | 24768 | 24774 | 24780 | 24786 | 24792 | 24798. The next abundant number is 24800 which breaks the pattern.

It might be appropriate in this post to remind myself what constitutes an abundant number and to list some interesting facts about them. To begin, a definition from Wikipedia:

In number theory, an abundant number or excessive number is a number for which the sum of its proper divisors is greater than the number itself. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. The amount by which the sum exceeds the number is the abundance. The number 12 has an abundance of 4, for example. 

Definition: a number \(n\) for which the sum of divisors \(\sigma(n)>2n \), or, equivalently, the sum of proper divisors (or aliquot sum) \( \text{s}(n)>n\). 

Abundance is the value \( \sigma(n)-2n\) (or \( \text{s}(n)-n\)).

Some of the interesting facts about abundant numbers are:

• the smallest odd abundant number is 945
• The smallest abundant number not divisible by 2 or by 3 is 5391411025
• infinitely many even and odd abundant numbers exist
• every integer greater than 20161 can be written as the sum of two abundant numbers 
• every multiple (beyond 1) of a perfect number is abundant
• every multiple of an abundant number is abundant
• an abundant number with abundance 1 is called a quasiperfect number, although none have yet been found

ADDENDUM: Friday, June 12th 2020

I came across some further interesting facts about abundant numbers on this site. Here is what was mentioned:

• There are at least 10000 pairs of known consecutive abundant integers.
  See A096399 and this file by T. D. Noe.
  
• The triple 171078830, 171078831, 171078832 was apparently found by Laurent Hodges and Michael Reid in 1995.
  
• There are at least 1000 triples of consecutive abundant numbers.
  See A096536 and this file by Donovan Johnson.
  
• The starting term of the smallest consecutive 4-tuple of abundant numbers is at most:
  141363708067871564084949719820472453374 (39 digits)
  by Bruno Mishutka, November 1st 2007. See A094628.

Counterbalanced Numbers

 

Today's daily count turned up counterbalanced numbers that apparently have the property that:$$ \frac{\phi(n)}{\sigma(n)-n}$$is an integer. Of course, this prompted me to revisit the phi and sigma functions because I'm regularly forgetting what they signify. To recapitulate, the phi function is the Euler totient function defined by WolframAlpha as:

The totient function \(\phi(n) \), also called Euler's totient function, is defined as the number of positive integers \(\leq n\) that are relatively prime to (i.e., do not contain any factor in common with) \(n\), where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function \(\phi(n)\) can be simply defined as the number of totatives of \(n\). For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so \( \phi(24)=8\).

In this case, \( \phi(24307)=23976\). The sigma function gives the number of divisors of a number and in this case \( \sigma(24307)=24640\). Thus:$$ \sigma(24307)-24307=24640-24307=333 \text{ and }\\ \frac{\phi(24307)}{333}=\frac{23976}{333}=72$$Actually the sigma function is a little more complicated because technically is comes with a subscript that can have any integer value, positive or negative. Let's say the subscript is \(k\), then the sigma function represents the sum of the \(k^{th}\) powers of the divisors. Thus when \(k=0\), it returns the number of divisors because the \(0^{th}\) powers of the divisors are 1. When \(k=1\), it returns the sum of the divisors and so it really is the \(k=1\) case that the sigma function is being used above.

on July 5th 2021