Highly touted number

The totient of a number is defined as , which is also called Euler's Phi function and indicates how many coprime natural numbers there are that are not greater than . ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

In number theory is a hochtotiente number (from the English highly totient number ) is a natural number for which the equation ${\displaystyle n}$

${\displaystyle \varphi (x)=n}$

has more solutions than the equation for any other natural number . ${\displaystyle \varphi (x)=k}$ ${\displaystyle k<n}$

A highly-totient number, which is a prime number, is called a highly-totient prime number . The only highly touted prime number is . ${\displaystyle n=2}$

Examples

• The Totienten , so the number of prime natural numbers , are (for ): ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle x<n}$ ${\displaystyle n=1,2,3,\ldots }$

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, ... (sequence A000010 in OEIS )

Example :

The number is in the 8th position of the list above . The number has coprime numbers that are less than , namely and . Hence actually . ${\displaystyle 4}$ ${\displaystyle n=8}$ ${\displaystyle 4}$ ${\displaystyle n=8}$ ${\displaystyle 1,3,5}$ ${\displaystyle 7}$ ${\displaystyle \varphi (8)=4}$

In the 7th position of the list above is the number . The number is a prime number and thus has relatively prime numbers that are smaller than , namely all numbers from to . So is . ${\displaystyle 6}$ ${\displaystyle n=7}$ ${\displaystyle 6}$ ${\displaystyle n=7}$ ${\displaystyle k=1}$ ${\displaystyle k=6}$ ${\displaystyle \varphi (7)=6}$

• A prime number is only divisible by and itself. Thus it is relatively prime to the numbers to . So is (see calculation of Euler's Phi function ). Thus: ${\displaystyle p}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle \varphi (p)=p-1}$

${\displaystyle \varphi (p)=p-1}$

The totient of every prime number is therefore the same . ${\displaystyle p}$ ${\displaystyle p-1}$

• Be . There are five solutions of the equation , namely , , , and : ${\displaystyle n:=8}$ ${\displaystyle \varphi (x)=8}$ ${\displaystyle x_{1}=15}$ ${\displaystyle x_{2}=16}$ ${\displaystyle x_{3}=20}$ ${\displaystyle x_{4}=24}$ ${\displaystyle x_{5}=30}$

The number is coprime to numbers and prime, so there are eight coprime numbers and that's why it is . So the totient of the number is . ${\displaystyle x_{1}=15}$ ${\displaystyle 1,2,4,7,8,11,13}$ ${\displaystyle 14}$ ${\displaystyle x_{1}=15}$ ${\displaystyle \varphi (15)=8}$ ${\displaystyle x_{1}=15}$ ${\displaystyle 8}$

The number is coprime to numbers and prime, so there are eight coprime numbers and that's why it is . So the totient of the number is . ${\displaystyle x_{2}=16}$ ${\displaystyle 1,3,5,7,9,11,13}$ ${\displaystyle 15}$ ${\displaystyle x_{2}=16}$ ${\displaystyle \varphi (16)=8}$ ${\displaystyle x_{2}=16}$ ${\displaystyle 8}$

The number is coprime to numbers and prime, so there are eight coprime numbers and that's why it is . So the totient of the number is . ${\displaystyle x_{3}=20}$ ${\displaystyle 1,3,7,9,11,13,17}$ ${\displaystyle 19}$ ${\displaystyle x_{3}=20}$ ${\displaystyle \varphi (20)=8}$ ${\displaystyle x_{3}=20}$ ${\displaystyle 8}$

The number is coprime to numbers and prime, so there are eight coprime numbers and that's why it is . So the totient of the number is . ${\displaystyle x_{4}=24}$ ${\displaystyle 1,5,7,11,13,17,19}$ ${\displaystyle 23}$ ${\displaystyle x_{4}=24}$ ${\displaystyle \varphi (24)=8}$ ${\displaystyle x_{4}=24}$ ${\displaystyle 8}$

The number is coprime to numbers and prime, so there are eight coprime numbers and that's why it is . So the totient of the number is . ${\displaystyle x_{4}=30}$ ${\displaystyle 1,7,11,13,17,19,23}$ ${\displaystyle 29}$ ${\displaystyle x_{5}=30}$ ${\displaystyle \varphi (30)=8}$ ${\displaystyle x_{5}=30}$ ${\displaystyle 8}$

There are numbers whose totient is. There is no other natural number less than that for which the equation has five or more solutions. Thus is a highly-totient number. ${\displaystyle 5}$ ${\displaystyle x}$ ${\displaystyle \varphi (x)=8}$ ${\displaystyle k}$ ${\displaystyle n=8}$ ${\displaystyle \varphi (x)=k}$ ${\displaystyle n=8}$

In other words, there are exactly five numbers, namely , , , and whose Totient is. The number of numbers whose totient is must not be greater or equal in each case . Since this is the case, it is a high-totient number. ${\displaystyle x_{1}=15}$ ${\displaystyle x_{2}=16}$ ${\displaystyle x_{3}=20}$ ${\displaystyle x_{4}=24}$ ${\displaystyle x_{5}=30}$ ${\displaystyle n=8}$ ${\displaystyle x}$ ${\displaystyle n<8}$ ${\displaystyle 5}$ ${\displaystyle n=8}$

In fact, the value appears only five times in the above list of totients , namely in the 15th, 16th, 20th, 24th and 30th positions. ${\displaystyle 8}$

• The first highly-totient numbers are the following:

1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640, 11520, 17280, 25920, 30240, 34560, 40320, 51840, 60480, 69120, 80640, 103680, 120960, 161280, 181440, 207360, 241920, 362880, 483840, 725760, 967680, ... (sequence A097942 in OEIS )

By definition, the numbers in this list keep getting bigger (in contrast to the list in the next example).

These upper highly-totient numbers are the totients for numbers (increasing for ): ${\displaystyle k}$ ${\displaystyle k=1,2,3,\ldots }$

2, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54, 72, 98, 126, 129, 176, 178, 247, 276, 281, 331, 359, 399, 441, 454, 525, 558, 692, 718, 734, 764, 1023, 1138, 1485, 1755, 2008, 2166, 2590, 2702, 2733, 3169, 3687, 3802, 4133, 4604, 5025, 5841, 6019, 6311,… (Follow A131934 in OEIS )

Example :

In the 7th position of the first list is the number . The number is in the 7th position of the lower list . This means that there are different numbers whose totient results. No other number is less than the totient of the same number or more than different numbers, which makes a highly-totient number. ${\displaystyle n=48}$ ${\displaystyle k=11}$ ${\displaystyle 11}$ ${\displaystyle n=48}$ ${\displaystyle 48}$ ${\displaystyle 11}$ ${\displaystyle n=48}$

• The next list gives the smallest numbers, which are totients for numbers (ascending for ): ${\displaystyle k}$ ${\displaystyle k=2,3,4\ldots }$

1, 2, 4, 8, 12, 32, 36, 40, 24, 48, 160, 396, 2268, 704, 312, 72, 336, 216, 936, 144, 624, 1056, 1760, 360, 2560, 384, 288, 1320, 3696, 240, 768, 9000, 432, 7128, 4200, 480, 576, 1296, 1200, 15936, 3312, 3072, 3240, 864, 3120, 7344, 3888, 720, 1680, 4992, ... (Follow A007374 in OEIS )

This list is very similar to the previous list of high-totient numbers, but in contrast to the previous list of high-totient numbers, the numbers can also become smaller again.

Example 1 :

In the -th place (when you start counting) is the number . There are thus numbers whose totient is and there is none that would also be totient for numbers. Thus is the smallest value for which there are numbers that all have the same totient, viz . ${\displaystyle k=5}$ ${\displaystyle k=2}$ ${\displaystyle n=8}$ ${\displaystyle 5}$ ${\displaystyle n=8}$ ${\displaystyle n<8}$ ${\displaystyle 5}$ ${\displaystyle n=8}$ ${\displaystyle 5}$ ${\displaystyle n=8}$

Example 2 :

In the -th place (when you start counting) is the number . There are thus numbers whose totient is and there is none that would also be totient for numbers. Thus is the smallest value for which there are numbers that all have the same totient, viz . ${\displaystyle k=7}$ ${\displaystyle k=2}$ ${\displaystyle n=32}$ ${\displaystyle 7}$ ${\displaystyle n=32}$ ${\displaystyle n<32}$ ${\displaystyle 7}$ ${\displaystyle n=32}$ ${\displaystyle 7}$ ${\displaystyle n=32}$

However, if you compare this value with the list of highly-totient numbers directly above it, you will see that the number is already in the -th place . This number is the totient of different numbers which all have the same totient, viz . Because there is no smaller value that is totient for or more numbers, it is a high-totient number. The value is the smallest value, which is the totient of different numbers, but since it is greater than , it is not highly totient and therefore does not appear in this list. ${\displaystyle k=6}$ ${\displaystyle n=24}$ ${\displaystyle 10}$ ${\displaystyle n=24}$ ${\displaystyle n<24}$ ${\displaystyle 10}$ ${\displaystyle n=24}$ ${\displaystyle n=32}$ ${\displaystyle 7}$ ${\displaystyle 24}$

• A table follows, from which one can read the highly-totient numbers a little easier. In the first column are the ascending numbers, in the second column are those numbers whose totient is and in the third column you can read the number of numbers in the second column. Every time there is a higher number in this third column than in all the other lines before, it is a highly-totted number (which is colored yellow). At the end of the table, a few selected others are listed that may appear in the above examples: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

properties

• There are infinitely many highly-totted numbers.
• The number is the only odd highly-touted number. All other highly-totient numbers are even numbers. ${\displaystyle n=1}$
• The totient of a number can be calculated for each from its canonical prime factorization as follows (see general calculation formula of Euler's Phi function ): ${\displaystyle \varphi (x)}$ ${\displaystyle x}$ ${\displaystyle x\in \mathbb {N} ^{+}}$ ${\displaystyle x=\prod _{p\mid x}p^{k_{p}}}$

${\displaystyle \varphi (x)=\prod _{p\mid x}p^{k_{p}-1}(p-1)}$

Thus:

A high-totient number is a number that can be represented as a product in more ways than any other number . ${\displaystyle n}$ ${\displaystyle k<n}$

Example :

The hochtotiente number is the Totient of five numbers , , , and . Thus: ${\displaystyle n=8}$ ${\displaystyle x_{1}=15}$ ${\displaystyle x_{2}=16}$ ${\displaystyle x_{3}=20}$ ${\displaystyle x_{4}=24}$ ${\displaystyle x_{5}=30}$

${\displaystyle {\begin{array}{rclclclcl}\varphi (15)&=&\varphi (3\cdot 5)&=&3^{1-1}\cdot (3-1)\cdot 5^{1-1}\cdot (5-1)&=&1\cdot 2\cdot 1\cdot 4&=&8\\\varphi (16)&=&\varphi (2^{4})&=&2^{4-1}\cdot (2-1)&=&8\cdot 1&=&8\\\varphi (20)&=&\varphi (2^{2}\cdot 5)&=&2^{2-1}\cdot (2-1)\cdot 5^{1-1}\cdot (5-1)&=&2\cdot 1\cdot 1\cdot 4&=&8\\\varphi (24)&=&\varphi (2^{3}\cdot 3)&=&2^{3-1}\cdot (2-1)\cdot 3^{1-1}\cdot (3-1)&=&4\cdot 1\cdot 1\cdot 2&=&8\\\varphi (30)&=&\varphi (2\cdot 3\cdot 5)&=&2^{1-1}\cdot (2-1)\cdot 3^{1-1}\cdot (3-1)\cdot 5^{1-1}\cdot (5-1)&=&1\cdot 1\cdot 1\cdot 2\cdot 1\cdot 4&=&8\end{array}}}$

See also

• Euler's phi function
• Highly quoted number
• High composite number
• Non-cotient
• Nontotient
• Perfect total number
• Scarce total number

Web links

• Eric W. Weisstein : Totient Function . In: MathWorld (English).
• Eric W. Weisstein : Nontotient . In: MathWorld (English).
• Arndt Brünner: subsets and prime factor decompositions, Euler's Phi function and faculties. Calculation of Euler's Phi function. Accessed February 15, 2020 (German).