Innumber theory, a branch ofmathematics, ahighly cototient number is a positiveinteger${\displaystyle k}$ which is above 1 and has more solutions to theequation

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

than any other integer below${\displaystyle k}$ and above 1. Here,${\displaystyle \varphi }$ isEuler'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, ... (sequenceA100827 in theOEIS)

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

The concept is somewhat analogous to that ofhighly composite numbers. Just as there are infinitely many highly composite numbers, there are also infinitely many highly cototient numbers. Computations become harder, sinceinteger factorization becomes harder as the numbers get larger.

Thecototient of${\displaystyle x}$ is defined as${\displaystyle x-\varphi (x)}$, i.e. the number of positive integers less than or equal to${\displaystyle x}$ that have at least one prime factor in common with${\displaystyle x}$. For example, the cototient of 6 is 4 since these four positive integers have aprime 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 (one number in each case), so 4 is a highly cototient number.

(sequenceA063740 in theOEIS)

n	ks such that${\displaystyle k-\varphi (k)=n}$	number ofks such that${\displaystyle k-\varphi (k)=n}$ (sequenceA063740 in theOEIS)
0	1	1
1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ... (all primes)	∞
2	4	1
3	9	1
4	6, 8	2
5	25	1
6	10	1
7	15, 49	2
8	12, 14, 16	3
9	21, 27	2
10		0
11	35, 121	2
12	18, 20, 22	3
13	33, 169	2
14	26	1
15	39, 55	2
16	24, 28, 32	3
17	65, 77, 289	3
18	34	1
19	51, 91, 361	3
20	38	1
21	45, 57, 85	3
22	30	1
23	95, 119, 143, 529	4
24	36, 40, 44, 46	4
25	69, 125, 133	3
26		0
27	63, 81, 115, 187	4
28	52	1
29	161, 209, 221, 841	4
30	42, 50, 58	3
31	87, 247, 961	3
32	48, 56, 62, 64	4
33	93, 145, 253	3
34		0
35	75, 155, 203, 299, 323	5
36	54, 68	2
37	217, 1369	2
38	74	1
39	99, 111, 319, 391	4
40	76	1
41	185, 341, 377, 437, 1681	5
42	82	1
43	123, 259, 403, 1849	4
44	60, 86	2
45	117, 129, 205, 493	4
46	66, 70	2
47	215, 287, 407, 527, 551, 2209	6
48	72, 80, 88, 92, 94	5
49	141, 301, 343, 481, 589	5
50		0

The first few highly cototient numbers which areprimes are^[2]

2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839, 1049, 1259, 1889, 2099, 2309, 2729, 3359, 3989, 4289, 4409, 5879, 6089, 6719, 9029, 9239, ... (sequenceA105440 in theOEIS)

• Highly totient number

• Integer sequences

• Articles with short description
• Short description is different from Wikidata