Perfect Powers

Firstly a reminder. What is a perfect power?

A perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, \(n\) is a perfect power if there exist natural numbers \(m > 1\), and \(k > 1\) such that \(m^k = n\). In this case, \(n\) may be called a perfect \(k\)-th power. If \(k = 2\) or \(k = 3\), then \(n\) is called a perfect square or perfect cube, respectively. Sometimes 1 is also considered a perfect power (\(1^k = 1\) for any \(k\)).

Today I turned 28188 days old and one of the interesting properties of this number, apart from the digit 8 appearing three times, is that its sum of digits (SOD) and product of digits (POD) are both perfect powers. This is because:$$ \begin{align} \text{SOD}(28188) &= 27 = 3^3\\ \text{POD}(28188) &= 1024 = 2^{10 }\end{align}$$This got me thinking as to how many positive integers in the range up to 40000 have this property. Well, it turns out that there are 217 and here they are (permalink):

4, 8, 9, 18, 22, 44, 81, 88, 144, 224, 242, 333, 414, 422, 441, 448, 484, 844, 999, 1124, 1133, 1142, 1177, 1214, 1224, 1241, 1242, 1313, 1331, 1339, 1393, 1412, 1421, 1422, 1555, 1717, 1771, 1888, 1933, 2114, 2124, 2141, 2142, 2214, 2222, 2241, 2248, 2284, 2411, 2412, 2421, 2428, 2482, 2824, 2842, 3113, 3131, 3139, 3193, 3311, 3319, 3391, 3913, 3931, 4112, 4121, 4122, 4211, 4212, 4221, 4228, 4282, 4444, 4822, 5155, 5515, 5551, 7117, 7171, 7711, 8188, 8224, 8242, 8422, 8818, 8881, 8888, 9133, 9313, 9331, 11114, 11124, 11133, 11141, 11142, 11214, 11222, 11241, 11248, 11284, 11313, 11331, 11411, 11412, 11421, 11428, 11482, 11824, 11842, 12114, 12122, 12141, 12148, 12184, 12212, 12221, 12222, 12411, 12418, 12481, 12814, 12841, 12888, 13113, 13131, 13311, 13399, 13939, 13993, 14111, 14112, 14121, 14128, 14182, 14211, 14218, 14281, 14488, 14812, 14821, 14848, 14884, 18124, 18142, 18214, 18241, 18288, 18412, 18421, 18448, 18484, 18828, 18844, 18882, 19339, 19393, 19933, 21114, 21122, 21141, 21148, 21184, 21212, 21221, 21222, 21411, 21418, 21481, 21814, 21841, 21888, 22112, 22121, 22122, 22211, 22212, 22221, 22228, 22282, 22444, 22822, 24111, 24118, 24181, 24244, 24424, 24442, 24811, 28114, 28141, 28188, 28222, 28411, 28818, 28881, 31113, 31131, 31311, 31399, 31939, 31993, 33111, 33199, 33399, 33919, 33939, 33991, 33993, 39139, 39193, 39319, 39339, 39391, 39393, 39913, 39931, 39933

What about numbers whose sums of divisors are perfect powers? In the range up to 40000, there are only 18 and they are (permalink):

3, 7, 21, 31, 81, 93, 127, 217, 381, 400, 651, 889, 2667, 3937, 8191, 11811, 24573, 27559

Take 21 with divisors of 1, 3, 7 and 21 as an example:$$ \sigma(21)=32=2^5$$What about numbers whose totients are perfect powers? Let's recall that:

The totient of a number, denoted by the Euler's totient function \(\phi(n)\), is the count of positive integers less than or equal to \(n\) that are coprime (relatively prime) to \(n\). Two numbers are coprime if their only common factor is 1.

Numbers of this sort are more frequent with there being 119 in the range up to 40000. They are (permalink):

5, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 51, 60, 64, 68, 80, 85, 96, 102, 120, 128, 136, 160, 170, 192, 204, 240, 255, 256, 257, 272, 320, 340, 384, 408, 480, 510, 512, 514, 544, 640, 680, 768, 771, 816, 960, 1020, 1024, 1028, 1088, 1280, 1285, 1360, 1536, 1542, 1632, 1920, 2040, 2048, 2056, 2176, 2560, 2570, 2720, 3072, 3084, 3264, 3840, 3855, 4080, 4096, 4112, 4352, 4369, 5120, 5140, 5440, 6144, 6168, 6528, 7680, 7710, 8160, 8192, 8224, 8704, 8738, 10240, 10280, 10880, 12288, 12336, 13056, 13107, 15360, 15420, 16320, 16384, 16448, 17408, 17476, 20480, 20560, 21760, 21845, 24576, 24672, 26112, 26214, 30720, 30840, 32640, 32768, 32896, 34816, 34952

Let's take 20 as an example. The numbers that are coprime to 20 are 1, 3, 7, 9, 11, 13, 17, 19 and so we have we have a count of 8:$$ \phi(20)=8=2^3$$Next, let's consider the sum of the anti-divisors of a number. First let's recall what an antidivisor is using Gemini to explain in very clear terms:

An anti-divisor is a number that fails to divide a target integer by the largest possible margin. While a regular divisor divides a number evenly with no remainder, an anti-divisor leaves the most unbiased, centered remainder possible. [1, 2, 3]

The concept was first formalized by mathematician Jon Perry. [1]

Mathematical Rules

An integer \(d\) (where \(1 < d < n\)) is an anti-divisor of \(n\) if it satisfies one of the following rules: [1, 2]

• For even values of \(d\): The number \(d\) divides \(2n\) evenly. Mathematically, we have:$$n \bmod d = \dfrac{d}{2}$$
• For odd values of \(d\): The number \(d\) divides \(2n - 1\) or \(2n + 1\) evenly. Mathematically we have  [1, 2]:$$n \bmod d = \dfrac{d-1}{2}  \text{ or } n \bmod d = \dfrac{d+1}{2}$$

Visual Example: Anti-divisors of 20

To find the anti-divisors of \(20\), you look for numbers between \(2\) and \(19\) that fail to divide \(20\), but cleanly divide \(40\) (twice \(20\)) or \(39\)/\(41\). [1]

• 3 is an odd anti-divisor because \(3 \times 13 = 39\), leaving a gap of \(1\) (since \(\frac{3-1}{2} = 1\), and \(20 \bmod 3 = 2\)).
• 8 is an even anti-divisor because \(8 \times 5 = 40\). It divides \(2 \times 20\) perfectly.
• 13 is an odd anti-divisor because \(13 \times 3 = 39\). [1]

Key Facts

• The number 1 is never an anti-divisor, as it evenly divides all integers.
• The number 2 has no anti-divisors.
• Prime numbers have a limited number of anti-divisors based heavily on multiples of \(2n\). [1, 2, 3]

For a complete look at integer sequences and properties, you can explore the The Anti-Divisor - OEIS catalog. [1]

There are 20 numbers in the range up to 40000 that satisfy and these are (permalink):

6, 8, 9, 14, 36, 89, 96, 221, 541, 576, 740, 778, 1854, 2114, 2571, 10277, 13631, 16160, 16389, 39428

Let's take 39428 as an example. The antidivisors of this number are:

3, 5, 7, 8, 15, 21, 35, 105, 751, 2253, 3755, 5257, 11265, 15771, 26285

The sum of these anti-divisors is \(65536 = 2^{16}\) and so it is perfect power.

Further investigation could target:

• the sum of the proper divisors
• the sum of the non-divisors
• the determinant of the circulant matrix
• the arithmetic derivative

Sum of Divisors Meets the Totient

The number associated with my diurnal age today, \(\textbf{27838}\), has an interesting property that is not so obvious until we look at its sum of divisors and its totient:$$ \begin{align}  \sigma(27838) &= 43200 \\ &= 2^6 \times 3^3 \times 5^2 \\ &\rightarrow 2,3,5 \text{ as distinct prime factors}\\ \phi(27838) &= 13440 \\&= 2^7 \times 3 \times 5 \times 7 \\ &\rightarrow 2,3,5,7 \text{ as distinct prime factors} \end{align}$$For both the sum of divisors and the totient, the prime factors are consecutive. This got me thinking as to how many numbers enjoy this property in the range up to 40000. I wasn't requiring that the smallest factor be 2 for both the sum of divisors and the totient but this is certainly the case at least in the range under consideration. 

In developing my algorithm (permalink), I naturally only considered composite numbers but I also required the sum of divisors and the totient to be composite as well. It turns out that there are 785 such numbers with the smallest being 14:$$ \begin{align}  \sigma(14) &= 24 \\ &= 2^3 \times 3 \\ &\rightarrow 2,3 \text{ as distinct prime factors}\\ \phi(14) &= 6 \\&= 2 \times 3  \\ &\rightarrow 2,3 \text{ as distinct prime factors} \end{align}$$Table 1 shows the numbers between 27838 and 30000.

Table 1: permalink

Here is the full list of the 146 numbers between 27838 and 40000 (permalink):

27838, 27956, 28126, 28215, 28258, 28329, 28340, 28424, 28458, 28614, 28728, 28768, 28782, 28809, 28826, 28985, 29029, 29222, 29260, 29295, 29337, 29393, 29512, 29640, 29667, 29678, 29835, 29848, 30039, 30184, 30240, 30264, 30305, 30381, 30504, 30566, 30760, 30780, 30814, 30888, 30914, 30943, 30956, 30996, 31008, 31027, 31160, 31174, 31283, 31331, 31392, 31416, 31465, 31496, 31529, 31806, 31816, 32103, 32130, 32131, 32298, 32376, 32395, 32589, 32604, 32718, 32802, 32984, 33015, 33176, 33292, 33345, 33383, 33440, 33480, 33495, 33497, 33528, 33572, 33592, 33836, 33885, 33915, 34008, 34162, 34276, 34293, 34317, 34440, 34452, 34573, 34580, 34605, 34782, 34884, 35061, 35074, 35112, 35340, 35343, 35424, 35464, 35530, 35752, 35805, 35910, 35948, 35960, 36366, 36423, 36666, 36828, 36859, 36860, 36890, 36920, 37060, 37128, 37417, 37638, 37719, 37730, 37758, 37772, 37961, 38038, 38152, 38285, 38340, 38368, 38408, 38610, 38745, 38760, 38874, 39032, 39121, 39219, 39270, 39370, 39458, 39501, 39520, 39556, 39576, 39729

If we consider the sum of the \( \textbf{proper} \) divisors of a number together with the totient, we find that only 104 numbers qualify in the range from 1 up to 40000. These are (permalink):

42, 78, 90, 93, 135, 198, 216, 219, 259, 270, 273, 360, 364, 403, 438, 679, 723, 738, 793, 988, 1080, 1299, 1333, 1446, 1683, 1722, 1793, 1818, 1924, 2009, 2044, 2263, 2295, 2623, 2743, 2754, 2970, 3135, 3157, 3162, 3258, 3420, 3589, 3796, 3960, 4284, 4320, 4440, 4453, 4564, 4905, 5187, 5824, 5983, 5995, 6893, 6918, 7320, 7373, 7380, 7392, 7783, 7980, 8928, 8987, 9504, 9720, 9943, 10864, 10920, 11023, 11538, 11653, 11904, 14233, 15613, 15813, 16764, 17593, 18019, 20202, 22625, 24199, 24339, 24613, 25275, 25324, 25792, 27133, 28243, 28564, 30240, 30303, 30623, 31408, 31992, 32283, 32284, 34300, 34393, 34933, 36421, 36720, 39283

Not all the prime factors of the sum of proper divisors begin with 2 as can be seen in Table 2 that shows the details for numbers between 28000 and 40000:

Table 2: permalink

Totient Function: Jagged Versus Rounded Local Minima

If we plot the totients of the natural numbers against the values of the numbers themselves then we typically find an UP-DOWN or DOWN-UP alternation depending on where you start. Figure 1 shows such a plot for numbers in the range between 40 and 60.

Figure 1

Occasionally however, we see a different pattern. Figure 2 shows the totients of numbers plotted against the numbers themselves in the range between 300 and 330.

Figure 2: permalink

Looking at the graph in Figure 2 we see that from 313 to 317 we have an DOWN-DOWN-UP-UP pattern, clearly visible as a rounded rather than a local UP-DOWN-UP minimum. The value of the local minimum is the totient of 315. So where else do these rounded local minima occur. We are looking for numbers \(n\) such that:$$ \phi(n-2)>\phi(n-1)>\phi(n) < \phi(n+1)<\phi(n+2)$$where \( \phi \) represents the totient function. In the case of 315 we have:$$ \begin{align} &\phi(313)>\phi(314)>\phi(315) < \phi(316)<\phi(317) \\ &312 >156>144<156<316 \end{align}$$where it can be seen that 313 and 317 are prime numbers. So where else do these local rounded minima occur in the range from 3 up to 40000? It turns out that there are 238 such minima with 315 being the first (permalink).

315, 525, 735, 1155, 1365, 1575, 1755, 1785, 1815, 1995, 2145, 2415, 2475, 2805, 3045, 3315, 3465, 3885, 4095, 4125, 4305, 4515, 4725, 4935, 5115, 5145, 5355, 5775, 6045, 6195, 6405, 6435, 6615, 6825, 7035, 7095, 7245, 7395, 7455, 7605, 7665, 8085, 8265, 8505, 8715, 8745, 8925, 9135, 9345, 9405, 9555, 9735, 9765, 9975, 10185, 10395, 10455, 10545, 10815, 10965, 11055, 11235, 11385, 11445, 11655, 11865, 12075, 12285, 12495, 12675, 12705, 12915, 13125, 13335, 13545, 13695, 13965, 14025, 14175, 14355, 14385, 14595, 14805, 14835, 15015, 15045, 15225, 15405, 15435, 15645, 15675, 15855, 16005, 16065, 16275, 16335, 16485, 16695, 16905, 17085, 17325, 17355, 17745, 17955, 18135, 18165, 18375, 18585, 18645, 18795, 18975, 19215, 19425, 19635, 19665, 20055, 20265, 20295, 20475, 20625, 20685, 20865, 20895, 21105, 21255, 21315, 21525, 21945, 22365, 22425, 22575, 22605, 22785, 22995, 23205, 23265, 23415, 23595, 23625, 23655, 23835, 23985, 24225, 24255, 24675, 24885, 24915, 25095, 25245, 25305, 25515, 25575, 25725, 25905, 25935, 26145, 26325, 26565, 26775, 26985, 27027, 27195, 27615, 27825, 27885, 28035, 28215, 28245, 28275, 28455, 28665, 28815, 28875, 29055, 29295, 29505, 29865, 29925, 30195, 30345, 30555, 30723, 30765, 30975, 31185, 31365, 31395, 31605, 31815, 32025, 32175, 32235, 32445, 32655, 32835, 32895, 33033, 33075, 33345, 33495, 33705, 33735, 33915, 34125, 34155, 34335, 34485, 34515, 34545, 34755, 34965, 35175, 35385, 35805, 36225, 36435, 36465, 36645, 36795, 36855, 37065, 37275, 37455, 37485, 37695, 37905, 38115, 38535, 38745, 38775, 38955, 39165, 39195, 39375, 39435, 39585, 39765, 39795

These numbers constitute OEIS A076773:

A076773   2-nadirs of phi: numbers k such that phi(k-2) > phi(k-1) > phi(k) < phi(k+1) < phi(k+2).

There are no rounded local maxima in the range up to one million.

Do we find these types of rounded local minima for other functions like the sigma function? 

We do indeed, although in the case of the sigma function there are only two numbers in the range up to 40000 and they are 17254 and 27754 (the first two members of the sequence OEIS A076774: permalink). 

However, rounded local maxima are far more common in the sigma function. In the range up to 40000, there are 267 numbers and they are (permalink):

315, 405, 525, 693, 765, 945, 1125, 1155, 1395, 1575, 1755, 1785, 1845, 1995, 2205, 2475, 2565, 2805, 2835, 3003, 3045, 3285, 3315, 3465, 3645, 3675, 3885, 4095, 4125, 4275, 4347, 4455, 4515, 4725, 4995, 5115, 5355, 5445, 5733, 5775, 5805, 6045, 6195, 6237, 6405, 6435, 6615, 6825, 6885, 7035, 7155, 7245, 7605, 7875, 7995, 8085, 8325, 8415, 8505, 8715, 8775, 8925, 9075, 9135, 9315, 9405, 9555, 9675, 9765, 9975, 10125, 10395, 10773, 11205, 11235, 11385, 11445, 11475, 11655, 12045, 12075, 12285, 12555, 12675, 12705, 12915, 13005, 13125, 13275, 13365, 13545, 13725, 13923, 13965, 14025, 14175, 14355, 14595, 14685, 14805, 15015, 15075, 15435, 15525, 15645, 15675, 15795, 16005, 16065, 16245, 16275, 16335, 16443, 16695, 16875, 16905, 16965, 17325, 17595, 17685, 17745, 17955, 18135, 18315, 18375, 18585, 18765, 18795, 19005, 19035, 19215, 19305, 19575, 19635, 19845, 20475, 20685, 20925, 21105, 21285, 21315, 21483, 21525, 21675, 21945, 22005, 22155, 22275, 22365, 22605, 22869, 22995, 23085, 23205, 23355, 23595, 23625, 23835, 23925, 24045, 24255, 24453, 24525, 24675, 24885, 24915, 25155, 25245, 25515, 25725, 25875, 25935, 26325, 26505, 26565, 26775, 27027, 27195, 27225, 27405, 27531, 27885, 28035, 28125, 28215, 28245, 28275, 28413, 28485, 28665, 28875, 28917, 29295, 29325, 29475, 29835, 29925, 30135, 30195, 30345, 30555, 30723, 30765, 31005, 31185, 31365, 31395, 31515, 31605, 31815, 32025, 32175, 32235, 32445, 32805, 32835, 33075, 33165, 33285, 33345, 33495, 33915, 34125, 34155, 34485, 34515, 34755, 34875, 34965, 35175, 35235, 35325, 35595, 35805, 35955, 36045, 36075, 36135, 36225, 36435, 36645, 36675, 36795, 36855, 37107, 37125, 37275, 37395, 37485, 37845, 38115, 38205, 38475, 38493, 38745, 38955, 39015, 39123, 39165, 39195, 39375, 39435, 39525, 39585, 39627, 39765, 39795

Let's take 405 as an example. It's position at the apex of a rounded local maximum is shown in Figure 3.

Figure 3: permalink

The above numbers constitute OEIS A323380:

A323380   Odd n such that sigma(n) > sigma(n+1) and sigma(n) > sigma(n-1), sigma = A000203.

Overall, these variations on the UP-DOWN or DOWN-UP alternation are an interesting topic to investigate and one that I'd not considered before. 

Properties of Concatenated Numbers

Let's split a number in two parts and then consider the relationship that these two parts bear to the number of which both are a part. Now I've done this before as described in a post titled Energetic Numbers. In THAT post, I looked at numbers that belong to OEIS  A055480:

A055480

Energetic numbers: numbers that can be broken into two or more substrings and expressed as a sum of (possibly different) positive powers of those substrings.

In THIS post I'll be looking at two different types of relationships. Let's consider 27573 and break it into two parts: 275 and 73. It turns out that my diurnal age today (27573) has an interesting property and it involves the totient function, commonly referred to as Euler's phi function or simply the phi function. We find that:$$ \begin{align}  \phi(27573) &= 1440 \\ \phi(275) \times \phi(73) &= 200 \times 72\\ &=1440 \end{align} $$Numbers like this belong to OEIS A147619 :

 A147619             Numbers \(n\)  = \(a \,| \, b\) such that \( \phi(n) = \phi(a) \times \phi(b) \)
                                where the symbol | represents concatenation

The initial members of this sequence are:

78, 780, 897, 918, 1179, 1365, 1776, 2574, 2598, 2967, 3168, 3762, 4758, 5775, 5796, 7800, 7875, 7917, 8217, 8970, 9180, 9576, 11790, 13650, 13662, 13875, 13896, 14391, 17760, 18564, 18858, 19812, 20097, 25740, 25935, 25974, 25980, 27573, 28776, 28779, 29670, 31680, 33165, 35919, 37620

Let's look at the breakdown for the numbers between 27573 and 37620:

• 275 | 73  -->  27573
  
  
•  287 | 76  -->  28776
  
  
•  287 |  79  -->  28779
  
  
•  29 | 670  -->   29670
  
  
•  31 | 680  -->   31680
  
  
•  331 | 65  -->   33165
  
  
•  35 | 919  -->   35919
  
  
•  37 | 620  -->   37620

A similar thing can be done with the sigma function that tallies the sum of the divisors of a number. Once again we break the number into two parts and then use the sigma function to connect those two parts to the whole. There is no OEIS function this time around but the property of the numbers being considered is as follows:

 Numbers \(n\)  = \(a \,| \, b\) such that \( \sigma(n) = \sigma(a) \times \sigma(b) \)
where the symbol | represent concatenation

The 78 numbers satisfying this condition between 27000 and 40000 are (permalink):

27175, 27298, 27418, 27445, 27500, 28018, 28195, 28750, 28798, 28978, 29038, 29058, 29098, 29278, 29395, 29398, 29500, 29875, 29875, 29950, 29950, 29980, 30498, 30775, 30788, 30989, 31750, 31795, 31918, 32595, 33175, 33238, 33298, 33725, 34189, 34555, 34557, 34795, 34975, 35338, 35395, 35578, 35585, 35670, 35818, 35975, 36178, 36238, 36350, 36398, 36426, 36775, 37138, 37241, 37678, 37750, 37798, 38247, 38370, 38518, 38570, 38638, 38750, 38826, 38856, 38877, 38940, 38975, 39118, 39425, 39478, 39500, 39754, 39805, 39898, 39976, 39980, 39992

Table 1 shows the breakdown for numbers between 27000 and 30000:

Table 1

Let's look at the first number 27175 where we break the number into 271 and 75 and we have:$$ \begin{align} \sigma(27175) &= 33728\\ \sigma(271) \times \sigma(75) &= 272 \times 124\\ &= 33728 \end{align}$$There are other possible concatenations involving more than two parts or other functions and properties of numbers so this post is merely a sample.

Finding Fibonacci

The Fibonacci numbers are few and far between. Up to a little over two million, the Fibonacci numbers are:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309

However, we can find Fibonacci numbers in all sorts of places. For example, I recently turned 27034 days old and this number is a member of OEIS A272412:

A272412

Numbers \(n\) such that \( \sigma_1(n)\) is a Fibonacci number.

It so happens that \( \sigma_1(27034) = 46368 \) which is a Fibonacci number. There are only 41 such numbers in the range up to one million. They are (permalink):

1, 2, 7, 9, 66, 70, 94, 115, 119, 2479, 18084, 19180, 19290, 22060, 23156, 23178, 24934, 24956, 25756, 26715, 27034, 28678, 28965, 29578, 30094, 32253, 32793, 34113, 35365, 38635, 39319, 40963, 42493, 44413, 45223, 45653, 322032, 429424, 503175, 624027, 670975

The sum of the aliquot parts of a number is the sum of its proper divisors and so Fibonacci numbers will show up here as well. We have to exclude prime numbers in our search because their only proper divisor is 1 and so they would need to be included. It turns out that there are 175 composite numbers up to one million whose sum of proper divisors are a Fibonacci number. They are:

1, 4, 10, 18, 27, 35, 36, 49, 51, 62, 90, 91, 171, 329, 415, 473, 533, 629, 687, 713, 902, 1119, 1135, 1207, 1214, 1605, 1711, 1927, 2936, 2949, 3436, 6083, 6103, 6845, 7831, 8119, 9487, 10063, 10207, 12367, 12531, 13231, 17069, 18373, 18703, 20283, 20579, 24319, 26843, 28783, 29719, 32743, 33823, 35263, 45443, 53121, 57683, 61573, 66779, 71653, 72803, 80785, 81779, 90949, 95593, 95611, 99937, 109093, 111179, 130153, 134149, 145403, 153779, 156613, 159323, 162083, 167579, 169699, 173353, 194251, 196393, 199883, 200543, 208723, 210649, 215603, 218731, 225923, 227173, 228649, 230053, 233579, 235993, 238643, 240133, 242149, 242495, 243013, 246179, 275603, 287617, 306179, 313043, 325726, 346415, 356963, 364099, 365363, 372359, 378646, 381779, 395723, 401579, 405443, 408883, 411979, 424283, 433403, 435811, 444083, 451043, 456179, 459179, 461243, 464579, 485483, 488443, 503579, 510779, 512749, 525119, 527243, 530419, 535043, 540083, 547403, 549779, 553283, 558815, 573803, 578723, 581579, 587963, 592283, 597203, 602579, 604763, 612779, 617483, 619459, 622163, 628883, 630563, 632579, 633323, 633779, 635123, 635963, 636179, 636683, 646840, 649869, 670171, 686083, 693211, 716179, 724429, 761899, 825143, 830183, 842899, 919651, 935821, 975143, 986179

Take 51 as an example. It's proper divisors are 1, 3 and 17. These add to 21 which is a Fibonacci number. There is no associated OEIS sequence for these numbers.

Let's look at the totients of numbers. The totient of a number \(n\) is a count of how many numbers \(1 \leq k \leq n \) have the property that \( \text{gcd}(n,k)=1\) where gcd stands for greatest common divisor. The totient of 6 is 2 because 1 and 5 have this property. These numbers form OEIS A280592: 

A280592

Numbers \(n\)  such that \( \phi(n)\) is a Fibonacci number.

 Here is the list of the 134 sequence members up to one million.

1, 2, 3, 4, 6, 15, 16, 20, 24, 30, 185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630, 3235, 5176, 6470, 7764, 46843, 47423, 47693, 48053, 50431, 52403, 56231, 57965, 59555, 62855, 67655, 67865, 70735, 72123, 72297, 73473, 75387, 77691, 78819, 81207, 84651, 85869, 86985, 89535, 89655, 89817, 90945, 92744, 93686, 94846, 95288, 95386, 95504, 95632, 96106, 96164, 97964, 100516, 100568, 100862, 101535, 102165, 103588, 103635, 104806, 105092, 108248, 108304, 108584, 108976, 112462, 112868, 113176, 115930, 119110, 119380, 119540, 119756, 125710, 135310, 135380, 135730, 136220, 139116, 139176, 139212, 139248, 141470, 142932, 143256, 143448, 144246, 144594, 145116, 145512, 146946, 147204, 150774, 150852, 155382, 157638, 162372, 162414, 162456, 162876, 163464, 165816, 169302, 169764, 171738, 173970, 174060, 179070, 179310, 179634, 181890, 203070, 204330, 207270

Why are there no numbers from 207271 up to one million that are members of the sequence? If we extend the range to two million, there are some additional members, namely 1040075, 1304859, 1372899, 1739812 and 1830532.

Of course, we don't need to confine ourselves to the Fibonacci numbers. We could consider the Lucas numbers instead which begin with 2, 1 rather than 0, 1 like the Fibonacci. The initial Lucas numbers are:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196

Up to one million, there are only nine numbers that qualify and they are 1, 2, 3, 4, 10, 17, 688, 1075 and 103681.

If we consider the sum of the aliquot parts however, we get 151 in the range up to one million. These are:

4, 8, 9, 21, 48, 72, 92, 115, 129, 146, 165, 187, 205, 289, 493, 965, 999, 1143, 1337, 1417, 1495, 1749, 1957, 2517, 2527, 2722, 3077, 3397, 3401, 5177, 5599, 6437, 6609, 7097, 8201, 8357, 8551, 8777, 9017, 9485, 9701, 9797, 10777, 14239, 15637, 17549, 19639, 24751, 25141, 27199, 31879, 37499, 38359, 38825, 39149, 42319, 46241, 46715, 48946, 50959, 52471, 53627, 53851, 55505, 56137, 56693, 58951, 60031, 65387, 66511, 67159, 67519, 67591, 75605, 76117, 79897, 81581, 102689, 102707, 104341, 109709, 109869, 114109, 119641, 127957, 130721, 133141, 138037, 140377, 144689, 144841, 151661, 154741, 175477, 177097, 186401, 207149, 224593, 248429, 270251, 275789, 283453, 287033, 340513, 344507, 350369, 357101, 362833, 370541, 377249, 390641, 449233, 459709, 470321, 486476, 500893, 535841, 555341, 560509, 577197, 598813, 606989, 613409, 621827, 648569, 658667, 663073, 664481, 670829, 698209, 704737, 708749, 746381, 748753, 758861, 796109, 798869, 802289, 826489, 833069, 851441, 863773, 869041, 869741, 887969, 894029, 931453, 950353, 956509, 962593, 988787

As for totients, there are 21 numbers in the range up to one million whose totient is a member of the Lucas sequence. These numbers are:

1, 2, 3, 4, 5, 6, 8, 10, 12, 19, 27, 38, 54, 2049, 2732, 4098, 5779, 11558, 36717, 48956, 73434

Another approach is to look at the determinant formed by the circulant matrix of a number. For example, 27255 has a circulant matrix as shown in Figure 1.

Figure 1

This matrix has a determinant of 21 which is a Fibonacci number. It turns out that there are 59500 numbers in the range up to one million that have this property (permalink).

Instead of the determinant, the permanent of the matrix could be considered. For example, 19140 has the circulant matrix shown in Figure 2.

Figure 2

In the range up to one million, there are only 68 such numbers (as opposed to the 59500 for the determinant). Here are the numbers:

[1, 2, 3, 5, 8, 10, 11, 12, 21, 22, 23, 32, 35, 53, 58, 85, 100, 101, 110, 200, 1000, 1001, 1021, 1100, 1102, 1120, 1201, 1222, 2011, 2022, 2110, 2122, 2202, 2212, 2220, 2221, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10419, 10941, 11000, 11001, 11010, 11094, 11100, 11490, 14019, 14901, 19104, 19140, 40191, 41109, 41910, 49011, 90114, 91041, 91401, 94110, 100000, 100001, 100100, 110000, 1000000]

Here are the Fibonacci numbers associated with each of these numbers:

1 --> 1

2 --> 2

3 --> 3

5 --> 5

8 --> 8

10 --> 1

11 --> 2

12 --> 5

21 --> 5

22 --> 8

23 --> 13

32 --> 13

35 --> 34

53 --> 34

58 --> 89

85 --> 89

100 --> 1

101 --> 2

110 --> 2

200 --> 8

1000 --> 1

1001 --> 2

1021 --> 34

1100 --> 2

1102 --> 34

1120 --> 34

1201 --> 34

1222 --> 233

2011 --> 34

2022 --> 144

2110 --> 34

2122 --> 233

2202 --> 144

2212 --> 233

2220 --> 144

2221 --> 233

10000 --> 1

10001 --> 2

10010 --> 2

10011 --> 13

10100 --> 2

10101 --> 13

10110 --> 13

10419 --> 75025

10941 --> 75025

11000 --> 2

11001 --> 13

11010 --> 13

11094 --> 75025

11100 --> 13

11490 --> 75025

14019 --> 75025

14901 --> 75025

19104 --> 75025

19140 --> 75025

40191 --> 75025

41109 --> 75025

41910 --> 75025

49011 --> 75025

90114 --> 75025

91041 --> 75025

91401 --> 75025

94110 --> 75025

100000 --> 1

100001 --> 2

100100 --> 8

110000 --> 2

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\)