# Nontotient

In number theory, a nontotient is a positive integer n which is not a totient number: it is not in the range of Euler's totient function φ, that is, the equation φ(x) = n has no solution x. In other words, n is a nontotient if there is no integer x that has exactly n coprimes below it. All odd numbers are nontotients, except 1, since it has the solutions x = 1 and x = 2. The first few even nontotients are this sequence:
    14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, ... (sequence A005277 in the OEIS)
The least value of k such that the totient of k is n are (0 if no such k exists) are this sequence:
    1, 3, 0, 5, 0, 7, 0, 15, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 25, 0, 23, 0, 35, 0, 0, 0, 29, 0, 31, 0, 51, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 69, 0, 47, 0, 65, 0, 0, 0, 53, 0, 81, 0, 87, 0, 59, 0, 61, 0, 0, 0, 85, 0, 67, 0, 0, 0, 71, 0, 73, ... (sequence A049283 in the OEIS)
The greatest value of k such that the totient of k is n are (0 if no such k exists) are this sequence:
    2, 6, 0, 12, 0, 18, 0, 30, 0, 22, 0, 42, 0, 0, 0, 60, 0, 54, 0, 66, 0, 46, 0, 90, 0, 0, 0, 58, 0, 62, 0, 120, 0, 0, 0, 126, 0, 0, 0, 150, 0, 98, 0, 138, 0, 94, 0, 210, 0, 0, 0, 106, 0, 162, 0, 174, 0, 118, 0, 198, 0, 0, 0, 240, 0, 134, 0, 0, 0, 142, 0, 270, ... (sequence A057635 in the OEIS)
The number of ks such that φ(k) = n are (start with n = 0) are this sequence:
    0, 2, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 6, 0, 0, 0, 6, 0, 4, 0, 5, 0, 2, 0, 10, 0, 0, 0, 2, 0, 2, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 4, 0, 3, 0, 2, 0, 11, 0, 0, 0, 2, 0, 2, 0, 3, 0, 2, 0, 9, 0, 0, 0, 8, 0, 2, 0, 0, 0, 2, 0, 17, ... (sequence A014197 in the OEIS)
Carmichael's conjecture is that there are no 1s in this sequence.
An even nontotient may be one more than a prime number, but never one less, since all numbers below a prime number are, by definition, coprime to it. To put it algebraically, for p prime: φ(p) = p − 1. Also, a pronic number n(n − 1) is certainly not a nontotient if n is prime since φ(p$^2$) = p(p − 1).
If a natural number n is a totient, n · 2$^k$ is a totient for all natural numbers k.
There are infinitely many even nontotient numbers: indeed, there are infinitely many distinct primes p (such as 78557 and 271129, see Sierpinski number) such that all numbers of the form 2$^a$p are nontotient, and every odd number has an even multiple which is a nontotient.
| n | numbers k such that φ(k) = n | n | numbers k such that φ(k) = n | n | numbers k such that φ(k) = n | n | numbers k such that φ(k) = n |
| 1 | 1, 2 | 37 | | 73 | | 109 | |
| 2 | 3, 4, 6 | 38 | | 74 | | 110 | 121, 242 |
| 3 | | 39 | | 75 | | 111 | |
| 4 | 5, 8, 10, 12 | 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 76 | | 112 | 113, 145, 226, 232, 290, 348 |
| 5 | | 41 | | 77 | | 113 | |
| 6 | 7, 9, 14, 18 | 42 | 43, 49, 86, 98 | 78 | 79, 158 | 114 | |
| 7 | | 43 | | 79 | | 115 | |
| 8 | 15, 16, 20, 24, 30 | 44 | 69, 92, 138 | 80 | 123, 164, 165, 176, 200, 220, 246, 264, 300, 330 | 116 | 177, 236, 354 |
| 9 | | 45 | | 81 | | 117 | |
| 10 | 11, 22 | 46 | 47, 94 | 82 | 83, 166 | 118 | |
| 11 | | 47 | | 83 | | 119 | |
| 12 | 13, 21, 26, 28, 36, 42 | 48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 84 | 129, 147, 172, 196, 258, 294 | 120 | 143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462 |
| 13 | | 49 | | 85 | | 121 | |
| 14 | | 50 | | 86 | | 122 | |
| 15 | | 51 | | 87 | | 123 | |
| 16 | 17, 32, 34, 40, 48, 60 | 52 | 53, 106 | 88 | 89, 115, 178, 184, 230, 276 | 124 | |
| 17 | | 53 | | 89 | | 125 | |
| 18 | 19, 27, 38, 54 | 54 | 81, 162 | 90 | | 126 | 127, 254 |
| 19 | | 55 | | 91 | | 127 | |
| 20 | 25, 33, 44, 50, 66 | 56 | 87, 116, 174 | 92 | 141, 188, 282 | 128 | 255, 256, 272, 320, 340, 384, 408, 480, 510 |
| 21 | | 57 | | 93 | | 129 | |
| 22 | 23, 46 | 58 | 59, 118 | 94 | | 130 | 131, 262 |
| 23 | | 59 | | 95 | | 131 | |
| 24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 96 | 97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420 | 132 | 161, 201, 207, 268, 322, 402, 414 |
| 25 | | 61 | | 97 | | 133 | |
| 26 | | 62 | | 98 | | 134 | |
| 27 | | 63 | | 99 | | 135 | |
| 28 | 29, 58 | 64 | 85, 128, 136, 160, 170, 192, 204, 240 | 100 | 101, 125, 202, 250 | 136 | 137, 274 |
| 29 | | 65 | | 101 | | 137 | |
| 30 | 31, 62 | 66 | 67, 134 | 102 | 103, 206 | 138 | 139, 278 |
| 31 | | 67 | | 103 | | 139 | |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 68 | | 104 | 159, 212, 318 | 140 | 213, 284, 426 |
| 33 | | 69 | | 105 | | 141 | |
| 34 | | 70 | 71, 142 | 106 | 107, 214 | 142 | |
| 35 | | 71 | | 107 | | 143 | |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 108 | 109, 133, 171, 189, 218, 266, 324, 342, 378 | 144 | 185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630 |