View source for Noncototient

{{Short description|Positive integers with specific properties}}

In [[number theory]], a '''noncototient''' is a [[positive integer]] {{mvar|n}} that cannot be expressed as the difference between a positive integer {{mvar|m}} and the number of [[coprime]] integers below it. That is, {{math|1=''m'' &minus; ''φ''(''m'') = ''n''}}, where {{mvar|φ}} stands for [[Euler's totient function]], has no solution for&nbsp;{{mvar|m}}.  The ''[[cototient]]'' of {{mvar|n}} is defined as {{math|''n'' &minus; ''φ''(''n'')}}, so a '''noncototient''' is a number that is never a cototient.

It is conjectured that all noncototients are even. This follows from a modified form of the slightly stronger version of the [[Goldbach conjecture]]: if the even number {{mvar|n}} can be represented as a sum of two distinct primes {{mvar|p}} and {{mvar|q}}, then

<math display=block>\begin{align}
  pq - \varphi(pq) &= pq - (p-1)(q-1) \\
  &= p + q - 1 \\ 
  &= n - 1. 
\end{align}</math>

It is expected that every even number larger than 6 is a sum of two distinct primes, so probably no odd number larger than 5 is a noncototient. The remaining odd numbers are covered by the observations {{math|1=1 = 2 – ''φ''(2)}}, {{math|1=3 = 9 – ''φ''(9)}}, and {{math|1=5 = 25 – ''φ''(25)}}.

For even numbers, it can be shown
<math display=block>\begin{align}
  2pq - \varphi(2pq) &= 2pq - (p-1)(q-1) \\
  &= pq + p + q - 1 \\
  &= (p+1)(q+1) - 2
\end{align}</math>

Thus, all even numbers {{mvar|n}} such that {{math|''n'' + 2}} can be written as {{math|(''p'' + 1)(''q'' + 1)}} with {{mvar|p, q}} primes are cototients.

The first few noncototients are

:[[10 (number)|10]], [[26 (number)|26]], [[34 (number)|34]], [[50 (number)|50]], [[52 (number)|52]], [[58 (number)|58]], [[86 (number)|86]], [[100 (number)|100]], [[116 (number)|116]], [[122 (number)|122]], [[130 (number)|130]], [[134 (number)|134]], [[146 (number)|146]], [[154 (number)|154]], [[170 (number)|170]], [[172 (number)|172]], 186, 202, 206, 218, [[222 (number)|222]], 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, ... {{OEIS|id=A005278}}

The cototient of {{mvar|n}} are
: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, ... {{OEIS|id=A051953}}

Least {{mvar|k}} such that the cototient of {{mvar|k}} is {{mvar|n}} are (start with {{math|1=''n'' = 0}}, 0 if no such {{mvar|k}} exists)
:1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0,  ... {{OEIS|id=A063507}}

Greatest {{mvar|k}} such that the cototient of {{mvar|k}} is {{mvar|n}} are (start with {{math|1=''n'' = 0}}, 0 if no such {{mvar|k}} exists)
:1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, ... {{OEIS|id=A063748}}

Number of {{mvar|k}}s such that {{math|''k'' &minus; ''φ''(''k'')}} is {{mvar|n}} are (start with {{math|1=''n'' = 0}})
: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, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, ... {{OEIS|id=A063740}}

[[Paul Erdős|Erdős]] (1913–1996) and [[Wacław Sierpiński|Sierpinski]] (1882–1969) asked whether there exist infinitely many noncototients. This was finally answered in the affirmative by Browkin and Schinzel (1995), who showed every member of the infinite family <math> 2^k \cdot 509203</math> is an example (See [[Riesel number]]). Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca (2000).

{| class="wikitable mw-collapsible mw-collapsed"
|+ class="nowrap" | Cototients of {{mvar|n}} from 1-144
! {{mvar|n}} !! Numbers {{mvar|k}} such that {{math|1=''k'' &minus; ''&phi;''(''k'') = ''n''}}
|-
! 1
| all primes
|-
! 2
| 4
|-
! 3
| 9
|-
! 4
| 6, 8
|-
! 5
| 25
|-
! 6
| 10
|-
! 7
| 15, 49
|-
! 8
| 12, 14, 16
|-
! 9
| 21, 27
|-
! 10
| 
|-
! 11
| 35, 121
|-
! 12
| 18, 20, 22
|-
! 13
| 33, 169
|-
! 14
| 26
|-
! 15
| 39, 55
|-
! 16
| 24, 28, 32
|-
! 17
| 65, 77, 289
|-
! 18
| 34
|-
! 19
| 51, 91, 361
|-
! 20
| 38
|-
! 21
| 45, 57, 85
|-
! 22
| 30
|-
! 23
| 95, 119, 143, 529
|-
! 24
| 36, 40, 44, 46
|-
! 25
| 69, 125, 133
|-
! 26
| 
|-
! 27
| 63, 81, 115, 187
|-
! 28
| 52
|-
! 29
| 161, 209, 221, 841
|-
! 30
| 42, 50, 58
|-
! 31
| 87, 247, 961
|-
! 32
| 48, 56, 62, 64
|-
! 33
| 93, 145, 253
|-
! 34
| 
|-
! 35
| 75, 155, 203, 299, 323
|-
! 36
| 54, 68
|-
! 37
| 217, 1369
|-
! 38
| 74
|-
! 39
| 99, 111, 319, 391
|-
! 40
| 76
|-
! 41
| 185, 341, 377, 437, 1681
|-
! 42
| 82
|-
! 43
| 123, 259, 403, 1849
|-
! 44
| 60, 86
|-
! 45
| 117, 129, 205, 493
|-
! 46
| 66, 70
|-
! 47
| 215, 287, 407, 527, 551, 2209
|-
! 48
| 72, 80, 88, 92, 94
|-
! 49
| 141, 301, 343, 481, 589
|-
! 50
| 
|-
! 51
| 235, 451, 667
|-
! 52
| 
|-
! 53
| 329, 473, 533, 629, 713, 2809
|-
! 54
| 78, 106
|-
! 55
| 159, 175, 559, 703
|-
! 56
| 98, 104
|-
! 57
| 105, 153, 265, 517, 697
|-
! 58
| 
|-
! 59
| 371, 611, 731, 779, 851, 899, 3481
|-
! 60
| 84, 100, 116, 118
|-
! 61
| 177, 817, 3721
|-
! 62
| 122
|-
! 63
| 135, 147, 171, 183, 295, 583, 799, 943
|-
! 64
| 96, 112, 124, 128
|-
! 65
| 305, 413, 689, 893, 989, 1073
|-
! 66
| 90
|-
! 67
| 427, 1147, 4489
|-
! 68
| 134
|-
! 69
| 201, 649, 901, 1081, 1189
|-
! 70
| 102, 110
|-
! 71
| 335, 671, 767, 1007, 1247, 1271, 5041
|-
! 72
| 108, 136, 142
|-
! 73
| 213, 469, 793, 1333, 5329
|-
! 74
| 146
|-
! 75
| 207, 219, 275, 355, 1003, 1219, 1363
|-
! 76
| 148
|-
! 77
| 245, 365, 497, 737, 1037, 1121, 1457, 1517
|-
! 78
| 114
|-
! 79
| 511, 871, 1159, 1591, 6241
|-
! 80
| 152, 158
|-
! 81
| 189, 237, 243, 781, 1357, 1537
|-
! 82
| 130
|-
! 83
| 395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889
|-
! 84
| 164, 166
|-
! 85
| 165, 249, 325, 553, 949, 1273
|-
! 86
| 
|-
! 87
| 415, 1207, 1711, 1927
|-
! 88
| 120, 172
|-
! 89
| 581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921
|-
! 90
| 126, 178
|-
! 91
| 267, 1027, 1387, 1891
|-
! 92
| 132, 140
|-
! 93
| 261, 445, 913, 1633, 2173
|-
! 94
| 138, 154
|-
! 95
| 623, 1079, 1343, 1679, 1943, 2183, 2279
|-
! 96
| 144, 160, 176, 184, 188
|-
! 97
| 1501, 2077, 2257, 9409
|-
! 98
| 194
|-
! 99
| 195, 279, 291, 979, 1411, 2059, 2419, 2491
|-
! 100
| 
|-
! 101
| 485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201
|-
! 102
| 202
|-
! 103
| 303, 679, 2263, 2479, 2623, 10609
|-
! 104
| 206
|-
! 105
| 225, 309, 425, 505, 1513, 1909, 2773
|-
! 106
| 170
|-
! 107
| 515, 707, 1067, 1691, 2291, 2627, 2747, 2867, 11449
|-
! 108
| 156, 162, 212, 214
|-
! 109
| 321, 721, 1261, 2449, 2701, 2881, 11881
|-
! 110
| 150, 182, 218
|-
! 111
| 231, 327, 535, 1111, 2047, 2407, 2911, 3127
|-
! 112
| 196, 208
|-
! 113
| 545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769
|-
! 114
| 226
|-
! 115
| 339, 475, 763, 1339, 1843, 2923, 3139
|-
! 116
| 
|-
! 117
| 297, 333, 565, 1177, 1717, 2581, 3337
|-
! 118
| 174, 190
|-
! 119
| 539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599
|-
! 120
| 168, 200, 232, 236
|-
! 121
| 1331, 1417, 1957, 3397
|-
! 122
| 
|-
! 123
| 1243, 1819, 2323, 3403, 3763
|-
! 124
| 244
|-
! 125
| 625, 1469, 1853, 2033, 2369, 2813, 3293, 3569, 3713, 3869, 3953
|-
! 126
| 186
|-
! 127
| 255, 2071, 3007, 4087, 16129
|-
! 128
| 192, 224, 248, 254, 256
|-
! 129
| 273, 369, 381, 1921, 2461, 2929, 3649, 3901, 4189
|-
! 130
| 
|-
! 131
| 635, 2147, 2507, 2987, 3131, 3827, 4187, 4307, 4331, 17161
|-
! 132
| 180, 242, 262
|-
! 133
| 393, 637, 889, 3193, 3589, 4453
|-
! 134
| 
|-
! 135
| 351, 387, 575, 655, 2599, 3103, 4183, 4399
|-
! 136
| 268
|-
! 137
| 917, 1397, 3161, 3317, 3737, 3977, 4661, 4757, 18769
|-
! 138
| 198, 274
|-
! 139
| 411, 1651, 3379, 3811, 4171, 4819, 4891, 19321
|-
! 140
| 204, 220, 278
|-
! 141
| 285, 417, 685, 1441, 3277, 4141, 4717, 4897
|-
! 142
| 230, 238
|-
! 143
| 363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183
|-
! 144
| 216, 272, 284
|}

==References==
* {{cite journal | zbl=0820.11003 | last1=Browkin | first1=J. | last2=Schinzel | first2=A. | title=On integers not of the form n-φ(n) | journal=Colloq. Math. | volume=68 | number=1 | pages=55–58 | year=1995 | doi=10.4064/cm-68-1-55-58 | doi-access=free }}
* {{cite journal | zbl=0965.11003 | last1=Flammenkamp | first1=A. | last2=Luca | first2=F. | title=Infinite families of noncototients | journal=Colloq. Math. | volume=86 | number=1 | pages=37–41 | year=2000 | doi=10.4064/cm-86-1-37-41 | doi-access=free }}
* {{cite book |last=Guy | first=Richard K. | author-link=Richard K. Guy | title=Unsolved problems in number theory | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | pages=138–142}}

== External links ==
* [http://mathworld.wolfram.com/Noncototient.html Noncototient definition from MathWorld]

{{Totient}}
{{Classes of natural numbers}}

[[Category:Integer sequences]]