Highly cototient number

From Wikipedia, the free encyclopedia

In number theory, a branch of mathematics, a highly cototient number k is an integer that has more solutions to the equation

x − φ(x) = k,

where φ is Euler's totient function, than any integer below it, with the exception of 1. In other words, k is a cototient more often than any integer below it except 1. The first few highly cototient numbers are:

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 (sequence A100827 in OEIS)

1 is the highest cototient number, a k with infinitely many more solutions to x - φ(x) = k than any other integer. While 1 is the only odd highly totient number, there are several 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 mod 10. An even more interesting congruence is that all the terms after 8 are congruent to -1 mod a primorial.

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.

The first few highly cototient numbers which are primes (sequence A105440 in OEIS) are

2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839