Highly cototient number


In number theory, a branch of mathematics, a highly cototient number is a positive integer which is above 1 and has more solutions to the equation
than any other integer below and above 1. Here, is Euler's totient function. There are infinitely many solutions to the equation for
so this value is excluded in the definition. The first few highly cototient numbers are:
Many of the highly cototient numbers are odd. In fact, after 8, all the numbers listed above are odd, and after 167 all the numbers listed above are congruent to 29 modulo 30.
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.

Example

The cototient of is defined as, i.e. the number of positive integers less than or equal to that have at least one prime factor in common with. 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, so 4 is a highly cototient number.
nks such thatnumber of ks such that
011
12, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,...
241
391
46, 82
5251
6101
715, 492
812, 14, 163
921, 272
100
1135, 1212
1218, 20, 223
1333, 1692
14261
1539, 552
1624, 28, 323
1765, 77, 2893
18341
1951, 91, 3613
20381
2145, 57, 853
22301
2395, 119, 143, 5294
2436, 40, 44, 464
2569, 125, 1333
260
2763, 81, 115, 1874
28521
29161, 209, 221, 8414
3042, 50, 583
3187, 247, 9613
3248, 56, 62, 644
3393, 145, 2533
340
3575, 155, 203, 299, 3235
3654, 682
37217, 13692
38741
3999, 111, 319, 3914
40761
41185, 341, 377, 437, 16815
42821
43123, 259, 403, 18494
4460, 862
45117, 129, 205, 4934
4666, 702
47215, 287, 407, 527, 551, 22096
4872, 80, 88, 92, 945
49141, 301, 343, 481, 5895
500

Primes

The first few highly cototient numbers which are primes are