Divisibility of Integers by their Totients

I got to thinking about the conditions for a number to be divisible by its totient. It didn't take too long to see the pattern. Figure 1 shows the results for numbers up to 1024.

Figure 1: permalink

Clearly condition is that the numbers must by of the form \(2^p. 3^q\) where \(p>0\) and \(q \geq 0\). There are only 35 numbers in this range and, if we extend the range to 10 million, there are still only 178 numbers that satisfy.

These numbers form OEIS A007694:

A007694

Numbers \(k\) such that \( \phi(k) \) divides \(k\).

The initial members of the sequence are:

1, 2, 4, 6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96, 108, 128, 144, 162, 192, 216, 256, 288, 324, 384, 432, 486, 512, 576, 648, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8192, 8748, 9216

The numbers must be even, that is they must contain a power of 2. If the numbers are only powers of 3 then the dividend is 1.5. Figure 2 shows the results in the range up to one million. All numbers are of the form \(3^p\) where \(p>0\).

Figure 2: permalink

What sort of numbers will produce a dividend of 2.5? Well, as it turns out, numbers of the form \(2^p.5^q\) where \(p>1\) and \(q>1\). See Figure 3 for the numbers in the range up to one thousand.

Figure 3: permalink

A dividend of 3.5 is produced by numbers of the from \(2^p.3^q.7^r \) where \(p>0\), \(q>0\) and \(r>0\). See Figure 4 for the numbers in the range up to one thousand.

Figure 4: permalink

Numbers involving 11 as a factor appear if the dividend is 2.2 where numbers are of the form \(2^p.11^q\) where \(p>0\) and \(q>0\). See Figure 5 where the range is up to ten thousand.

Figure 5: permalink

Numbers of the from \(2^p.11^q.23^q\) with \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 2.3. See Figure 6 where the range is up to 100,000.

Figure 6: permalink

Numbers of the form \(2^p.3^q.31^r\) where \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 3.1. Figure 7 shows the range up to ten thousand.

Figure 7: permalink

Numbers of the form \(2^p.3^q.11^r\) where \(p>0\), \(q>0\) and \(r>0\) produce a dividend of 3.3. See Figure 8 for numbers in the range up to one thousand.

Figure 8: permalink

More numbers emerge when we consider dividends like 3.25 and 3.75 but I'll stop there even though there is clearly room for further study of this topic. The following is a summary of what I found so far:

• \( \dfrac{n}{\phi(n)}=k\) where \(k>0\) if numbers of form \(2^p.3^q\) with \(p>0\) and \(q \geq 0\)
• \( \dfrac{n}{\phi(n)}=1.5\) if numbers of form  \(3^p\) with \(p>0\)
• \( \dfrac{n}{\phi(n)}=2.2\) if numbers of form  \(2^p.11^q\) where \(p>0\) and \(q>0\)
• \( \dfrac{n}{\phi(n)}=2.3\) if numbers of form \(2^p.11^q.23^q\) with \(p>0\), \(q>0\) and \(r>0\)
• \( \dfrac{n}{\phi(n)}=2.5\) if numbers of form \(2^p.5^q\) with \(p>0\) and \(q>0\)
• \( \dfrac{n}{\phi(n)}=3.1\) if numbers of form \(2^p.3^q.31^r\) where \(p>0\), \(q>0\) and \(r>0\)
• \( \dfrac{n}{\phi(n)}=3.3\) if numbers of form \(2^p.3^q.11^r\) where \(p>0\), \(q>0\) and \(r>0\)
• \( \dfrac{n}{\phi(n)}=3.5\) if numbers of form \(2^p.3^q.7^r \) with \(p>0\), \(q>0\) and \(r>0\)

Numbers and Matrices

Suppose we have a number with distinct, non-zero digits. The number associated with my diurnal age, 26918, is one such number. Let's now consider a 3 x 3 matrix with the numbers 1 to 9 positioned as shown in Figure 1:

Figure 1

Let's apply two rules to the digits in the matrix:

1. if a matrix digit does occur in the number then it is left unchanged 
2. if the matrix digit does not occur in the number then it is changed to a zero

See Figure 2 for the application of these two rules using 26918 as the number.

Figure 2: determinant is \(-\)48

Using this method, all permutations of the digits of a number will produce the same matrix e.g. 81962 (the reverse of 26918). Next find the determinant of the matrix. In the case of 26918, the determinant is \(-\)48. Does the determinant divide the number? Since 26918 factorises to 2 x 43 x 313, clearly it does not. 

However, there are numbers for which the determinant of its associated matrix does divide the number. Take for example 27468. It produces the matrix shown in Figure 3.

Figure 3: determinant is 84

This matrix has a determinant of 84 and this number appears in the divisors of 27468:

1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 109, 126, 218, 252, 327, 436, 654, 763, 981, 1308, 1526, 1962, 2289, 3052, 3924, 4578, 6867, 9156, 13734, 27468

How many numbers between 1 and 100,000 satisfy this divisibility rule? Well, not many. It turns out that there are only 256 numbers representing a mere 0.265% of the total range. The low number is not surprising as the number must firstly contain distinct non-zero digits and secondly the determinant of its associated matrix must divide the number. Here is the list of the numbers that pass the test:

384, 672, 735, 816, 1395, 1935, 1968, 3168, 3195, 3276, 3648, 3675, 3915, 4392, 6972, 9135, 9168, 9315, 9432, 12384, 12864, 13248, 13824, 13968, 14895, 14985, 15648, 17325, 17568, 17856, 18375, 18432, 18495, 18576, 18624, 18945, 19485, 19845, 21648, 21735, 21756, 24816, 27468, 28416, 28476, 29736, 31584, 31968, 34578, 34587, 34758, 34785, 34857, 34875, 35478, 35487, 35748, 35784, 35847, 35874, 36792, 37248, 37296, 37458, 37485, 37548, 37584, 37695, 37824, 37845, 37854, 38457, 38475, 38496, 38547, 38574, 38745, 38754, 39168, 39648, 41568, 41856, 41895, 41985, 42735, 42756, 42816, 43578, 43587, 43758, 43785, 43857, 43872, 43875, 43968, 45168, 45276, 45378, 45387, 45738, 45783, 45792, 45837, 45873, 46128, 46872, 47328, 47358, 47385, 47538, 47583, 47592, 47628, 47835, 47853, 47952, 48195, 48357, 48375, 48537, 48573, 48735, 48753, 48915, 49185, 49752, 49815, 51648, 53184, 53478, 53487, 53748, 53784, 53847, 53874, 54378, 54387, 54738, 54783, 54792, 54816, 54837, 54873, 57168, 57348, 57384, 57438, 57483, 57624, 57834, 57843, 58176, 58347, 58374, 58416, 58437, 58473, 58734, 58743, 59472, 61248, 61572, 61584, 61824, 62748, 64128, 65184, 67284, 67452, 67935, 71568, 71652, 71856, 72135, 72156, 72345, 72384, 73185, 73248, 73458, 73485, 73548, 73584, 73815, 73824, 73845, 73854, 74235, 74256, 74358, 74385, 74538, 74583, 74592, 74835, 74853, 74952, 75168, 75264, 75348, 75384, 75438, 75483, 75834, 75843, 76524, 78345, 78354, 78432, 78435, 78453, 78534, 78543, 78624, 79632, 81264, 81375, 81456, 81495, 81936, 81945, 82416, 83457, 83475, 83547, 83574, 83745, 83754, 84195, 84357, 84375, 84537, 84573, 84672, 84735, 84753, 84915, 85347, 85374, 85437, 85473, 85734, 85743, 87345, 87354, 87435, 87453, 87534, 87543, 89136, 89145, 89415, 91485, 91845, 92736, 93168, 93765, 94185, 94368, 94752, 94815, 95472, 96384, 98145, 98415

Here is the permalink to these results. This line of investigation was provoked by my inability to find much of interest about the number associated with my diurnal age, 26918. Most of what I found in the OEIS related to obscure properties connected with matrices. Ironically, I was then led to matrices anyway. Unfortunately, my number didn't qualify. 

To my delight however, I discovered that if I took the totient of 26918, which is 13104, then the determinant did divide it. The divisors of 13104 are listed below and it can be seen that 48 is a divisor:

1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 18, 21, 24, 26, 28, 36, 39, 42, 48, 52, 56, 63, 72, 78, 84, 91, 104, 112, 117, 126, 144, 156, 168, 182, 208, 234, 252, 273, 312, 336, 364, 468, 504, 546, 624, 728, 819, 936, 1008, 1092, 1456, 1638, 1872, 2184, 3276, 4368, 6552, 13104

Our previous number, 27468, that was divisible by the determinant of its associated matrix,  has a totient of 7776 and this number is not divisible by the determinant. If we investigate how many numbers have their totients divisible by the determinant then, in the range up to 100,000, there are 2514 numbers that satisfy representing 2.514%. This is about ten times the number for divisibility of the number itself by the determinant. I won't list all the numbers but here is the permalink to the calculation. In the narrow range between 26900 and 27100, there are only two numbers that qualify: 26918 and 26957. 

While we are are considering totients, we may as well consider the sum of the divisors of the number. How many numbers have their sum of divisors divisible by their associated matrix's determinant. Well in the range, up to 100,000, there are 2864 such numbers, a little more than for the totients. Here is the permalink to the calculation. In the narrow range between 26900 and 27100, there are only five such numbers: 26937, 26945, 26974, 26975, 26978.

We can reduce these largish numbers (2514 for totients and 2864 for sum of divisors) by restricting our choice of numbers to primes. In that case, the totient will be one less than the prime number (and thus always composite) and the sum of divisors will be one more than the prime number (and thus always composite). For example, 23 has a totient of 22 and its sum of divisors is 24. 

Applying this restriction, we find that there are 66 prime numbers up to 100,000 that have their sum of divisors divisible by the determinant. This determinant must be non-zero and this is often not the case because even in five digit numbers there will be five zeroes in the matrix (and more in smaller numbers). In summary then, these numbers are not common because they must:

• be prime
• have no repeating digits
• contain no zeroes
• have a non-zero determinant
• have a determinant that divides their sum of digits

The numbers are:

1259, 2687, 8543, 13859, 14759, 14783, 15749, 18539, 23687, 25367, 26879, 28439, 29567, 31859, 35279, 37589, 41579, 41759, 42839, 45179, 48239, 49823, 51479, 51749, 51839, 51869, 53189, 53819, 56237, 56891, 57149, 57329, 58169, 58379, 58943, 61487, 61583, 65183, 65981, 68351, 68543, 71549, 74159, 75149, 75389, 78539, 78623, 81359, 81569, 81647, 82463, 83579, 84239, 85439, 85619, 85691, 86351, 86951, 87359, 89561, 89627, 92567, 94823, 96581, 96851, 98561

Let's take 1259 as an example. Its sum of divisors in 1260 which has the following divisors:

1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 28, 30, 35, 36, 42, 45, 60, 63, 70, 84, 90, 105, 126, 140, 180, 210, 252, 315, 420, 630, 1260

The matrix associated with this number has a determinant of 45 and this is one of the divisors. 

For the totients, there are only 50 prime numbers up to 100,000 that have their totients divisible by the determinant. Once again, in summary, these numbers are not common because they must:

• be prime
• have no repeating digits
• contain no zeroes
• have a non-zero determinant
• have a determinant that divides their totient

The numbers are:

3571, 4591, 4951, 6217, 6481, 7351, 7681, 8641, 13249, 21673, 24697, 25849, 26497, 26713, 31249, 31489, 34129, 39241, 39841, 42193, 42697, 45289, 47269, 47629, 48193, 48673, 49681, 52489, 59671, 62497, 63841, 65731, 67429, 72469, 72649, 73681, 76249, 79561, 81649, 82561, 82657, 83617, 83761, 84673, 84961, 93241, 94321, 97561, 97651, 98641

Let's take 98641 as an example. The associated matrix determinant is \(-\)48 and the totient is 98640 with divisors shown below (amongst which is the determinant):

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 137, 144, 180, 240, 274, 360, 411, 548, 685, 720, 822, 1096, 1233, 1370, 1644, 2055, 2192, 2466, 2740, 3288, 4110, 4932, 5480, 6165, 6576, 8220, 9864, 10960, 12330, 16440, 19728, 24660, 32880, 49320, 98640

I've added the three sequences (without the prime stipulation) to my Bespoken for Sequences on Google Docs (Figure 4, Figure 5 and Figure 6):

Figure 4: link

Figure 5: link

Figure 6: link

While these sequences may seem somewhat contrived they pale before some of the bizarre entries in the OEIS. Hence I'm emboldened to describe them here, although I have no intention of submitting them for approval by the venomous OEIS vetting committee. 

THE CIRCULANT MATRIX

If we want to get on a more mainstream connection between numbers and matrices, we need go no further than the circulant matrix which is a square matrix in which each row vector is rotated one element to the right relative to the preceding row vector. Thus a number like 26933 has this associated circulant matrix (see Figure 7):

Figure 7

What's interesting about this particular number is that its determinant is equal to the number itself. Numbers of this sort form OEIS A219324:

A219324

Positive integers n that are equal to the determinant of the circulant matrix formed by the decimal digits of n.

The initial members of the sequence are (permalink for numbers in the range up to 40,000):

1, 2, 3, 4, 5, 6, 7, 8, 9, 247, 370, 378, 407, 481, 518, 592, 629, 1360, 3075, 26027, 26933, 45018, 69781, 80487, 154791, 1920261, 2137616, 2716713, 3100883, 3480140, 3934896, 4179451, 4830936, 5218958, 11955168, 80651025, 95738203, 257059332, 278945612, 456790123, 469135802, 493827160, 494376160

I couldn't help broadening this criterion a little to accommodate the situation in which the determinant does not need to be equal to the number whose digits appear in the first row of the matrix but could be in any row. 25203 is such a number. Let's look at its circulant matrix (see Figure 8):

Figure 8

The determinant of this matrix is 3252 and this number, with a leading zero, appears in the second row. In the range up to 40,000, there are 69 numbers that satisfy including all 21 of the members of OEIS  A219324 in that range (marked in red and here is a permalink):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 84, 100, 148, 185, 247, 259, 296, 370, 378, 407, 472, 481, 518, 592, 629, 703, 724, 740, 783, 814, 837, 851, 925, 962, 1000, 1360, 3075, 3150, 4002, 5031, 5071, 5471, 6013, 7150, 7154, 7530, 10000, 12054, 14063, 16072, 16978, 18450, 20325, 20541, 20596, 21607, 23035, 25203, 26027, 26933, 27260, 30352, 31406, 32520, 32693, 33269, 33604, 35230, 36043

Let's take one more example, this time 33269 with a circulant matrix as shown in Figure 9.

Figure 9

The determinant of this matrix is 26933 and looking at the matrix more closely we see that it is the same as the matrix shown in Figure 7 except that the top row has now moved to the bottom.  Thus it can be seen that, according to my new criterion, every row number is a member of the sequence in a circulant matrix where any one row number equals the derterminant. Thus 33269 is in the sequence and so too will be 69332 and 93326 (although I've only shown numbers up to 40,000).

Recursion involving the Totient Function

With plenty of time on my hands and my mind being lately obsessed with recursive processes, I contemplated what might happen if I took a number and added its totient plus one to it, repeating the process with the new number and only terminating when a prime number was reached. Put mathematically and applied to a number \(n\), we have:$$n \rightarrow n+\phi(n)+1$$The first thing to realise is that for any prime number \(p\), this process will yield:$$p \rightarrow p+\phi(p)+1=p+p-1+1=2p$$and so any prime is initially doubled by this process. Remember the totient \( \phi(n) \) of \(n\) is the number of coprime integers less than \(n\), including 1.

Using SageMathCell, I was able to quickly determine the trajectories for all numbers up to 6000  and the distribution is shown in Figure 1. The vertical axis shows the trajectory length while the horizontal axis shows the number. Some of the record trajectories are shown in Figure 1 as well e.g. (97, 152) indicates that the number 97 sets a new trajectory record length of 152.

Figure 1: permalink

Below are shown the numbers that produce trajectories of record length, together with those lengths:

•       1  has a trajectory of record length      1
•       2  has a trajectory of record length      2
•       3  has a trajectory of record length      8
•     31  has a trajectory of record length     10
•     42  has a trajectory of record length     31
•     97  has a trajectory of record length   152
•  1907  has a trajectory of record length   166
•  2130  has a trajectory of record length   217
•  3067  has a trajectory of record length   224
•  5243  has a trajectory of record length   232
•  7355  has a trajectory of record length   302
•  7604  has a trajectory of record length   307
• 10956 has a trajectory of record length >344

SageMathCell timed out for 10956 because the composite numbers were becoming unwieldingly large. See Figure 2.

Figure 2

The final number is the list shown in Figure 2 is:

128273423043384555138014803867139463949464184741011497767099217473602278 

It was at this point that SageMathCell gave up. Presumably the trajectory of 10956 does terminate but so far I've not been able to determine its exact length, although we know it's larger than 344. The average number of iterations is slightly over 14 in the range up to 6000.

I may have more to add on this recursive process at a later date.

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