Editing Highly cototient number

{{Short description|1 = Numbers k where x - phi(x) = k has many solutions}}

In [[number theory]], a branch of [[mathematics]], a '''highly cototient number''' is a positive [[integer]] <math>k</math> which is above 1 and has more solutions to the [[equation]] 

:<math>x - \phi(x) = k</math>

than any other integer below <math>k</math> and above 1. Here, <math>\phi</math> is [[Euler's totient function]]. There are infinitely many solutions to the equation for 

:<math>k</math> = [[1 (number)|1]] 

so this value is excluded in the definition. The first few highly cototient numbers are:<ref name=a100827>{{Cite OEIS|A100827|name=Highly cototient numbers}}.</ref>

:[[2 (number)|2]], [[4 (number)|4]], [[8 (number)|8]], [[23 (number)|23]], [[35 (number)|35]], [[47 (number)|47]], [[59 (number)|59]], [[63 (number)|63]], [[83 (number)|83]], [[89 (number)|89]], [[113 (number)|113]], [[119 (number)|119]], [[167 (number)|167]], [[209 (number)|209]], [[269 (number)|269]], 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, ... {{OEIS|id=A100827}}

Many of the highly cototient numbers are odd.<ref name=a100827/>

The concept is somewhat analogous to that of [[highly composite number]]s. Just as there are infinitely many highly composite numbers, there are also infinitely many highly cototient numbers. Computations become harder, since [[integer factorization]] becomes harder as the numbers get larger.

==Example==
The '''cototient''' of <math>x</math> is defined as <math>x - \phi(x)</math>, i.e. the number of positive integers less than or equal to <math>x</math> that have at least one prime factor in common with <math>x</math>. For example, the cototient of 6 is 4 since these four 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.

{{OEIS|id=A063740}}

{|class = "wikitable"
|-
| style="text-align:center" | '''''k''''' (highly cototient ''k'' are bolded)|| 0 || 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 || 26 || 27 || 28 || 29 || 30
|-
|'''Number of solutions to ''x'' − φ(''x'') = ''k''''' || 1 || ∞ || 1 || 1 || 2 || 1 || 1 || 2 || 3 || 2 || 0 || 2 || 3 || 2 || 1 || 2 || 3 || 3 || 1 || 3 || 1 || 3 || 1 || 4 || 4 || 3 || 0 || 4 || 1 || 4 || 3
|}

{|class="wikitable"
!''n''
!''k''s such that <math>k-\phi(k)=n</math>
|number of ''k''s such that <math>k-\phi(k)=n</math> {{OEIS|id=A063740}}
|-
|0
|1
|1
|-
|1
|2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ... (all primes)
|∞
|-
|'''2'''
|4
|1
|-
|3
|9
|1
|-
|'''4'''
|6, 8
|2
|-
|5
|25
|1
|-
|6
|10
|1
|-
|7
|15, 49
|2
|-
|'''8'''
|12, 14, 16
|3
|-
|9
|21, 27
|2
|-
|10
|
|0
|-
|11
|35, 121
|2
|-
|12
|18, 20, 22
|3
|-
|13
|33, 169
|2
|-
|14
|26
|1
|-
|15
|39, 55
|2
|-
|16
|24, 28, 32
|3
|-
|17
|65, 77, 289
|3
|-
|18
|34
|1
|-
|19
|51, 91, 361
|3
|-
|20
|38
|1
|-
|21
|45, 57, 85
|3
|-
|22
|30
|1
|-
|'''23'''
|95, 119, 143, 529
|4
|-
|24
|36, 40, 44, 46
|4
|-
|25
|69, 125, 133
|3
|-
|26
|
|0
|-
|27
|63, 81, 115, 187
|4
|-
|28
|52
|1
|-
|29
|161, 209, 221, 841
|4
|-
|30
|42, 50, 58
|3
|-
|31
|87, 247, 961
|3
|-
|32
|48, 56, 62, 64
|4
|-
|33
|93, 145, 253
|3
|-
|34
|
|0
|-
|'''35'''
|75, 155, 203, 299, 323
|5
|-
|36
|54, 68
|2
|-
|37
|217, 1369
|2
|-
|38
|74
|1
|-
|39
|99, 111, 319, 391
|4
|-
|40
|76
|1
|-
|41
|185, 341, 377, 437, 1681
|5
|-
|42
|82
|1
|-
|43
|123, 259, 403, 1849
|4
|-
|44
|60, 86
|2
|-
|45
|117, 129, 205, 493
|4
|-
|46
|66, 70
|2
|-
|'''47'''
|215, 287, 407, 527, 551, 2209
|6
|-
|48
|72, 80, 88, 92, 94
|5
|-
|49
|141, 301, 343, 481, 589
|5
|-
|50
|
|0
|}

==Primes==

The first few highly cototient numbers which are [[prime number|primes]] are <ref>{{Cite OEIS|A105440|name=Highly cototient numbers that are prime}}</ref>

: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, ... {{OEIS|id=A105440}}

==See also ==
* [[Highly totient number]]

==References==
{{reflist}}


{{Totient}}
{{Prime number classes}}
{{Classes of natural numbers}}

[[Category:Integer sequences]]