Highly cototient number

In number theory, a branch of mathematics, a highly cototient number is a positive integer ${\displaystyle k}$ which is above 1 and has more solutions to the equation

${\displaystyle x-\phi (x)=k}$

than any other integer below ${\displaystyle k}$ and above 1. Here, ${\displaystyle \phi }$ is Euler's totient function. There are infinitely many solutions to the equation for

${\displaystyle k}$ = 1

so this value is excluded in the definition. The first few highly cototient numbers are:^[1]

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 the OEIS)

Many of the highly cototient numbers are odd.^[1]

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 becomes harder as the numbers get larger.