This is an old revision of this page, as edited by AnomieBOT(talk | contribs) at 04:03, 7 April 2014(Dating maintenance tags: {{Unreferenced}}). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Revision as of 04:03, 7 April 2014 by AnomieBOT(talk | contribs)(Dating maintenance tags: {{Unreferenced}})
than any other integer below k and above one. Here, φ is Euler's totient function. There are infinitely many solutions to the equation for k = 1 so this value is excluded in the definition. The first few highly cototient numbers are:
There are many odd highly cototient numbers. In fact, after 8, all the numbers listed above are odd, and after 167 all the numbers listed above are congruent to 9 modulo 10.
The concept is somewhat analogous to that of highly composite numbers. Just as there are infinitely many highly composite numbers, there are also infinitely many highly cototient numbers. Computations become harder, since integer factorization does, as the numbers get larger.
Example
The cototient of x is defined as x – φ(x), i.e. the number of positive integers less than or equal to x that have at least one prime factor in common with x. For example, the cototient of 6 is 4 since these 4 positive integers have a prime factor in common with 6: 2, 3, 4, 6. The cototient of 8 is also 4, this time with these integers: 2, 4, 6, 8. There are exactly two numbers, 6 and 8, which have cototient 4. There are fewer numbers which have cototient 2 and cototient 3 (one number in each case), so 4 is a highly cototient number.
k (highly cototient k are bolded)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Number of solutions to x – φ(x) = k (OEIS: A063740)
∞
1
1
2
1
1
2
3
2
0
2
3
2
1
2
3
3
1
3
1
3
1
4
4
3
Primes
The first few highly cototient numbers which are primes (sequence A105440 in the OEIS) are
