Highly quoted number

The quotient of a number is defined as . It is the Euler phi function (also Totient from above) which indicates how many to prime natural numbers, there are no greater than are. The value thus indicates the number of natural numbers that have at least one prime factor in common. ${\displaystyle n}$ ${\displaystyle n-\varphi (n)}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-\varphi (n)}$ ${\displaystyle 0<x\leq n}$ ${\displaystyle n}$

In number theory is a hochkototiente number (from the English highly cototient number ) is a natural number for which the equation ${\displaystyle n>1}$

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

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

A high-quotient number, which is a prime number, is called a high-quotient prime number .

Examples

• The cotients , i.e. the number of positive whole numbers that have at least one prime factor in common, are (for ): ${\displaystyle n-\varphi (n)}$ ${\displaystyle x<n}$ ${\displaystyle n}$ ${\displaystyle n=1,2,3,\ldots }$

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27 ... (Follow A051953 in OEIS )

Example :

In the 7th position of the list above is the number . The number has coprime numbers which are less than (namely all from to ), thus is and therefore is actually . ${\displaystyle 1}$ ${\displaystyle n=7}$ ${\displaystyle 6}$ ${\displaystyle n=7}$ ${\displaystyle 1}$ ${\displaystyle 6}$ ${\displaystyle \varphi (7)=6}$ ${\displaystyle 7-\varphi (7)=7-6=1}$

In other words: the number only has at least one prime factor in common with the number , which is why the cotient of is equal . ${\displaystyle n=7}$ ${\displaystyle x=7}$ ${\displaystyle n=7}$ ${\displaystyle 1}$

The number is in the 6th position in the list above . The number has coprime numbers that are less than , namely and . Thus is and therefore is actual . ${\displaystyle 4}$ ${\displaystyle n=6}$ ${\displaystyle 2}$ ${\displaystyle n=6}$ ${\displaystyle k=1}$ ${\displaystyle k=5}$ ${\displaystyle \varphi (6)=2}$ ${\displaystyle 6-\varphi (6)=6-2=4}$

In other words, the number has with the numbers , , and share at least one prime factor, so is the Kototient of the same . ${\displaystyle n=6}$ ${\displaystyle x_{1}=2}$ ${\displaystyle x_{2}=3}$ ${\displaystyle x_{3}=4}$ ${\displaystyle x_{4}=6}$ ${\displaystyle n=6}$ ${\displaystyle 4}$

• 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 p-\varphi (p)=p-(p-1)=p-p+1=1}$

The quotient of every prime number is therefore the same (which should be clear, especially since every prime number only has at least one prime factor in common with itself). There are infinitely many prime numbers, so there are also infinitely many solutions to the equation for . So if one were to allow the number for highly quoted numbers , there would be no other natural numbers that would have more solutions for the equation than . That is why it is excluded as a special case by definition, it has to be . ${\displaystyle 1}$ ${\displaystyle x-\varphi (x)=n}$ ${\displaystyle n=1}$ ${\displaystyle n=1}$ ${\displaystyle k}$ ${\displaystyle x-\varphi (x)=k}$ ${\displaystyle k=n=1}$ ${\displaystyle n=1}$ ${\displaystyle n>1}$

• Be . There are two solutions to the equation , namely and : ${\displaystyle n:=4}$ ${\displaystyle x-\varphi (x)=4}$ ${\displaystyle x_{1}=6}$ ${\displaystyle x_{2}=8}$

The number is coprime to the numbers and prime, so there are two coprime numbers, and that's why it is . So is . So the quotient of the number is , there are numbers that are less than or equal to, which have at least one prime factor in common. ${\displaystyle x_{1}=6}$ ${\displaystyle 1}$ ${\displaystyle 5}$ ${\displaystyle x_{1}=6}$ ${\displaystyle \varphi (6)=2}$ ${\displaystyle 6-\varphi (6)=6-2=4}$ ${\displaystyle x_{1}=6}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 6}$ ${\displaystyle x_{1}=6}$

The number is coprime to numbers and prime, so there are four coprime numbers and that's why it is . So is . The quotient of the number is also , there are numbers that are smaller or equal , which have at least one prime factor in common. ${\displaystyle x_{2}=8}$ ${\displaystyle 1,3,5}$ ${\displaystyle 7}$ ${\displaystyle x_{2}=8}$ ${\displaystyle \varphi (8)=4}$ ${\displaystyle 8-\varphi (8)=8-4=4}$ ${\displaystyle x_{2}=8}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 8}$ ${\displaystyle x_{2}=8}$

There is no other natural number less than for which the equation has two or more solutions. Thus is a highly quoted number. ${\displaystyle k>1}$ ${\displaystyle n=4}$ ${\displaystyle x-\varphi (x)=k}$ ${\displaystyle n=4}$

In other words: there are exactly two numbers, namely and , whose cotient is. The number of numbers whose quotient is must not be greater or equal in each case . Since this is the case, it is a highly rated number. ${\displaystyle x_{1}=6}$ ${\displaystyle x_{2}=8}$ ${\displaystyle n=4}$ ${\displaystyle n<4}$ ${\displaystyle 2}$ ${\displaystyle n=4}$

In fact, the value only occurs twice in the above list of cotients , namely in the 6th and 8th position. ${\displaystyle 4}$

• Be . There are three solutions to the equation , namely , and : ${\displaystyle n:=8}$ ${\displaystyle x-\varphi (x)=8}$ ${\displaystyle x_{1}=12}$ ${\displaystyle x_{2}=14}$ ${\displaystyle x_{3}=16}$

The number is coprime to numbers and prime, so there are four coprime numbers and it is . So is . ${\displaystyle x_{1}=12}$ ${\displaystyle 1,5,7}$ ${\displaystyle 11}$ ${\displaystyle x_{1}=12}$ ${\displaystyle \varphi (12)=4}$ ${\displaystyle 12-\varphi (12)=12-4=8}$

The number is coprime to numbers and prime, so there are six coprime numbers and it is . So is . ${\displaystyle x_{2}=14}$ ${\displaystyle 1,3,5,9,11}$ ${\displaystyle 13}$ ${\displaystyle x_{2}=14}$ ${\displaystyle \varphi (14)=6}$ ${\displaystyle 14-\varphi (14)=14-6=8}$

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

There is no other natural number less than that for which the equation has three or more solutions. Thus is a highly quoted number. ${\displaystyle k>1}$ ${\displaystyle n=8}$ ${\displaystyle x-\varphi (x)=k}$ ${\displaystyle n=8}$

In other words: there are exactly three numbers, namely , and , whose cotient is. The number of numbers whose quotient is must not be greater or equal in each case . Since this is the case, it is a highly rated number. ${\displaystyle x_{1}=12}$ ${\displaystyle x_{2}=14}$ ${\displaystyle x_{3}=16}$ ${\displaystyle n=8}$ ${\displaystyle n<8}$ ${\displaystyle 3}$ ${\displaystyle n=8}$

In fact, the value appears only three times in the above list of cotients , namely in the 12th, 14th and 16th position. ${\displaystyle 8}$

• The first high cotient numbers are the following:

2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, 2099, 2309, 2729, 3149, 3359, 3569, 3989, 4199, 4289, 4409, 4619, 5249, 5459, 5879, 6089, 6509, 6719, 6929 ... (episode A100827 in OEIS )

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

These upper high cotient numbers are the cotients for numbers (ascending for ): ${\displaystyle k}$ ${\displaystyle k=0,1,2,3,\ldots }$

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 19, 20, 22, 25, 28, 31, 34, 41, 42, 46, 52, 58, 59, 69, 74, 77, 83, 93, 99, 116, 130, 138, 140, 156, 165, 166, 167, 173, 192, 200, 218, 219, 223, 241, 242, 271, 276, 292, 304, 331 ... (Follow A101373 in OEIS )

Example :

The number is in the 12th position of the first list . The number is in the 12th position of the list below . This means that there are different numbers whose cotient results. No other number is less than the cotient of the same number or more than different numbers, which makes a high cotient number. ${\displaystyle n=119}$ ${\displaystyle k=13}$ ${\displaystyle 13}$ ${\displaystyle n=119}$ ${\displaystyle 119}$ ${\displaystyle 13}$ ${\displaystyle n=119}$

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

10, 0, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 143, 119, 197, 167, 279, 233, 281, 209, 269, 323, 299, 359, 497, 329, 455, 605, 389, 461, 479, 419, 539, 599, 509, 755, 791, 713, 875, 797, 719, 629, 659, 1025, 1163, 929, 779, 1193, 1121, 899, 1133, 1091, 839 ... (sequence A063741 in OEIS )

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

Example 1 :

In the -th place is the number . There is no number for which it is solvable. Thus, no number has the cotient . Numbers for which there are no numbers that can be solved are called non-cotient (from the English non-cotient ). The smallest non-cotients are: ${\displaystyle k=0}$ ${\displaystyle n=10}$ ${\displaystyle x}$ ${\displaystyle x-\varphi (x)=10}$ ${\displaystyle x}$ ${\displaystyle n=10}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x-\varphi (x)=n}$

10, 26, 34, 50, 52, 58, 86, 100, 116, 122 ... (sequence A005278 in OEIS )

Example 2 :

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

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

• A table follows, from which one can read the high quotient numbers a little easier. In the first column are the ascending numbers, in the second column are those numbers whose cotient is and in the third column you can read off the number of numbers that are in the second column. Every time there is a higher number in this third column than in all other lines before (except for ), it is a highly quoted 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=1}$ ${\displaystyle n}$ ${\displaystyle n}$

High quotient prime numbers

• The smallest highly cotient prime numbers are the following:

  2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839, 1049, 1259, 1889, 2099, 2309, 2729, 3359, 3989, 4289, 4409, 5879, 6089, 6719, 9029, 9239, 10289, 10709, 11549, 13649, 13859, 15329, 15959, 20789, 21839, 23099, 25409, 27299, 30029, ... (sequence A105440 in OEIS )

properties

• There are an infinite number of highly rated numbers. However, only 229 highly-rated numbers are known (as of February 23, 2020).
• Among the known 229 high quotient numbers are only the first three, namely , and even numbers. All others are odd numbers. ${\displaystyle n_{1}=2}$ ${\displaystyle n_{2}=4}$ ${\displaystyle n_{3}=8}$
• Of the known 229 high-cotient numbers, all end between the 14th and the 229th high-cotient number with the digit 9. So for all these high-cotient numbers from to : ${\displaystyle n}$ ${\displaystyle n_{14}=209}$ ${\displaystyle n_{229}=6276269}$

${\displaystyle n\equiv 9\equiv -1{\pmod {10}}}$

• Of the known 229 high-cotient numbers, all between the 9th and the 229th high-cotient number result in a remainder of 5 when divided by 6. So for all these high-cotient numbers from to : ${\displaystyle n}$ ${\displaystyle n_{9}=83}$ ${\displaystyle n_{229}=6276269}$

${\displaystyle n\equiv 5\equiv -1{\pmod {6}}}$

• Of the known 229 high-cotient numbers, all between the 14th and 229th high-cotient number result in a remainder of 29 when divided by 30. So for all these high-cotient numbers from to : ${\displaystyle n}$ ${\displaystyle n_{14}=209}$ ${\displaystyle n_{229}=6276269}$

${\displaystyle n\equiv 29\equiv -1{\pmod {30}}}$

• Of the known 229 high-cotient numbers, all between the 41st and the 229th high-cotient number result in a remainder of 209 when divided by 210. It therefore applies to all of these high-cotient numbers from to : ${\displaystyle n}$ ${\displaystyle n_{41}=4409}$ ${\displaystyle n_{229}=6276269}$

${\displaystyle n\equiv 209\equiv -1{\pmod {210}}}$

• Of the known 229 high-cotient numbers, all between the 169th and the 229th high-cotient number result in a remainder of 2309 when divided by 2310. It therefore applies to all of these high-cotient numbers from to : ${\displaystyle n}$ ${\displaystyle n_{169}=1351349}$ ${\displaystyle n_{229}=6276269}$

${\displaystyle n\equiv 2309\equiv -1{\pmod {2310}}}$

• If you summarize the above results, you get the following result:

With the exception of the first three high-cotient numbers , and all other known high-cotient numbers are congruent -1 modulo of a prime faculty . ${\displaystyle n_{1}=2}$ ${\displaystyle n_{2}=4}$ ${\displaystyle n_{3}=8}$

Example :

The first Primfakultäten loud , , , and . ${\displaystyle 2\#=2}$ ${\displaystyle 3\#=6}$ ${\displaystyle 5\#=30}$ ${\displaystyle 7\#=210}$ ${\displaystyle 11\#=2310}$

The 200th highly quoted number is . Indeed it is . It is also , , and . ${\displaystyle n_{200}=2984519}$ ${\displaystyle n_{200}\equiv 2309\equiv -1{\pmod {2310}}}$ ${\displaystyle n_{200}\equiv 209\equiv -1{\pmod {210}}}$ ${\displaystyle n_{200}\equiv 29\equiv -1{\pmod {30}}}$ ${\displaystyle n_{200}\equiv 5\equiv -1{\pmod {6}}}$ ${\displaystyle n_{200}\equiv 1\equiv -1{\pmod {2}}}$

See also

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

Web links

• Eric W. Weisstein : Highly Cototient Number . In: MathWorld (English).
• Eric W. Weisstein : Noncotient . 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). 

Individual evidence

1. ↑ Eric W. Weis Stone : Noncototient . In: MathWorld (English).
2. ↑ ^{a b c d e f g} List of the first 229 high-cotient numbers on OEIS A100827
3. ↑ Comments on OEIS A100827