Anti-tau Numbers

I was familiar with what a tau number was, the definition being that it is an integer divisible by its number of its divisors.  Tau is the divisor function and returns the number of divisors of an integer e.g. \( \tau(6)=4\) because 6 has four divisors (1, 2, 3 and 6). However, 6 is not a tau number because 4 does not divide 6 without remainder.

In general, we can say that a number \(n\) is a tau number if \( \tau(n)|n\). 12 is a tau number because \( \tau(12) =6\) and \(6|12=2\). An alternative term, refactorable number, can be used for tau numbers (see Wikipedia entry). What then is an anti-tau number? Well, it turns out to be a number \(n\) such that \( \text{gcd}(n,\tau(n))=1\). These numbers comprise OEIS A046642.

A046642

Numbers \(k\) such that \(k\) and number of divisors \( \text{d}(k)\) are relatively prime.

Note that \( \text{d}(k)\) is sometimes used in place of \( \tau(k) \). All odd prime numbers will be anti-tau numbers because they have two divisors and 2 does not divide them. An example of an anti-tau number is 15 because it has four divisors (1, 3, 5 and 15) and gcd(15, 4) = 1. These numbers are quite frequent. There are 18080 in the range up to 40,000, representing over 45% of all the numbers in the range. The initial members are:

1, 3, 4, 5, 7, 11, 13, 15, 16, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 100, 101, 103, 105, 107, 109, 111, 113, 115, 119, 121, 123, 125, 127, 129, 131

Notice that all even anti-tau numbers are square numbers (4, 16, 64, 100, 196, 256, 484, 676, 784, 1024 etc.) of the form \(4k^2\) where \(k\) is a positive even integer. However, not all even values of \(k\) produce anti-tau numbers. The initial values of \(k\) are 2, 4, 8, 10, 14, 16,  22, ...

By contrast, tau numbers are less common. In the range up to 100,000, there are 5257 of them representing 5.257% of the range. The anti-tau numbers were brought to my attention by one of the properties of the number representing my diurnal age, 26895, qualifying it for membership of OEIS A341780:

A341780

Starts of runs of 3 consecutive anti-tau numbers (A046642).

Let's look at 26895, 26896 and 26897 to confirm that this is true:

• \(26895 = 3 \times 5 \times 11 \times 163\) with 16 divisors and 16 is relatively prime to it
• \(26896 = 2^4 \times 41^2\) with 15 divisors and 15 is relatively prime to it
• \(26897 = 13 \times 2069\) with 4 divisors and 4 is relatively prime to it

Despite how common anti-tau numbers are, these runs of three (the maximum possible) are not that frequent. The problem is that the runs are of the form odd-even-odd and the even numbers must be of the form \(4k^2\) as mentioned earlier. It is these relatively sparse even anti-tau numbers that make these runs less common than might be expected. Notice how \(26896 = 4 \times 82^2\). There are only 69 such numbers in the range up to 100,000. Here is the list:

3, 15, 195, 255, 483, 783, 1023, 1155, 1295, 1443, 1599, 2703, 3363, 4623, 4899, 5183, 6399, 6723, 7395, 7743, 8463, 8835, 10815, 11235, 11663, 12099, 12543, 15375, 16383, 16899, 17955, 18495, 20163, 24963, 25599, 26895, 27555, 31683, 33855, 35343, 36099, 37635, 38415, 40803, 44943, 45795, 46655, 47523, 52899, 53823, 55695, 56643, 61503, 62499, 64515, 65535, 70755, 71823, 73983, 80655, 81795, 82943, 85263, 87615, 88803, 91203, 92415, 94863, 96099

Here is a permalink that will confirm all the above results.

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

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).$$

Aliquot Sequences

My attention was drawn to aliquot sequences today, day 25098, because the number is a member of four aliquot sequences (as shown below):

From any starting point, it's easy enough to calculate the next member in the sequence by using the divisor function \(\sigma_1 \). For example, the second term in the sequence starting with 138 is \(\sigma_1 (138) -138=150\). Many sequences lead to a prime number and then terminate because \(\sigma_1 (\text{prime number}) -\text{prime number}=1\) and \(\sigma_1(1) -1=0\). The sequence beginning with 138 (OEIS A008888) has 178 members and ends in 59, 1, 0. OEIS A008889 is really the same as OEIS A008888 except for the starting point (150 instead of 138)

Aliquot sequence OEIS A008890 is different however, and starts with 168 but the second term is 312 which is the fifth term in OEIS A008888. Aliquot sequence OEIS A074907 starts with 570 but after a few terms reaches 19434 which again is a term in the OEIS A08888 sequence.

Not all aliquot sequences end. To quote from Wikipedia:

There are a variety of ways in which an aliquot sequence might not terminate:

• A perfect number has a repeating aliquot sequence of period 1. The aliquot sequence of 6, for example, is 6, 6, 6, 6, ... 

• An amicable number has a repeating aliquot sequence of period 2. For instance, the aliquot sequence of 220 is 220, 284, 220, 284, ... 

• A sociable number has a repeating aliquot sequence of period 3 or greater. (Sometimes the term sociable number is used to encompass amicable numbers as well.) For instance, the aliquot sequence of 1264460 is 1264460, 1547860, 1727636, 1305184, 1264460, ... 

• Some numbers have an aliquot sequence which is eventually periodic, but the number itself is not perfect, amicable, or sociable. For instance, the aliquot sequence of 95 is 95, 25, 6, 6, 6, 6, ... . Numbers like 95 that are not perfect, but have an eventually repeating aliquot sequence of period 1 are called aspiring numbers (OEIS  A063769).

Numbers whose Aliquot sequence is not known to be finite or eventually periodic are:

276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... (sequence A131884 in the OEIS) 

ADDENDUM: 17th July 2020

Today, I turned 26038 days old and I revisited OEIS A008888 (Aliquot sequence starting at 138) because this number is a member of the sequence and appears very near the end. Here is the full sequence:

138, 150, 222, 234, 312, 528, 960, 2088, 3762, 5598, 6570, 10746, 13254, 13830, 19434, 20886, 21606, 25098, 26742, 26754, 40446, 63234, 77406, 110754, 171486, 253458, 295740, 647748, 1077612, 1467588, 1956812, 2109796, 1889486, 953914, 668966, 353578, 176792, 254128, 308832, 502104, 753216, 1240176, 2422288, 2697920, 3727264, 3655076, 2760844, 2100740, 2310856, 2455544, 3212776, 3751064, 3282196, 2723020, 3035684, 2299240, 2988440, 5297320, 8325080, 11222920, 15359480, 19199440, 28875608, 25266172, 19406148, 26552604, 40541052, 54202884, 72270540, 147793668, 228408732, 348957876, 508132204, 404465636, 303708376, 290504024, 312058216, 294959384, 290622016, 286081174, 151737434, 75868720, 108199856, 101437396, 76247552, 76099654, 42387146, 21679318, 12752594, 7278382, 3660794, 1855066, 927536, 932464, 1013592, 1546008, 2425752, 5084088, 8436192, 13709064, 20563656, 33082104, 57142536, 99483384, 245978376, 487384824, 745600776, 1118401224, 1677601896, 2538372504, 4119772776, 8030724504, 14097017496, 21148436904, 40381357656, 60572036544, 100039354704, 179931895322, 94685963278, 51399021218, 28358080762, 18046051430, 17396081338, 8698040672, 8426226964, 6319670230, 5422685354, 3217383766, 1739126474, 996366646, 636221402, 318217798, 195756362, 101900794, 54202694, 49799866, 24930374, 17971642, 11130830, 8904682, 4913018, 3126502, 1574810, 1473382, 736694, 541162, 312470, 249994, 127286, 69898, 34952, 34708, 26038, 13994, 7000, 11720, 14740, 19532, 16588, 18692, 14026, 7016, 6154, 3674, 2374, 1190, 1402, 704, 820, 944, 916, 694, 350, 394, 200, 265, 59, 1, 0.

This is not the last time I'll encounter OEIS A008888 because in a couple of years time, I'll meet 26742 and 26754 (assuming I'm still alive).