From Surf Wiki (app.surf) — the open knowledge base

Highly cototient number

1 = Numbers k where x - phi(x) = k has many solutions

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

:x - \phi(x) = k

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

:k = 1

so this value is excluded in the definition. 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, ...

Many of the highly cototient numbers are odd.

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 x is defined as x - \phi(x), i.e. the number of positive integers less than or equal to x that have at least one prime factor in common with x. 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 (one number in each case), so 4 is a highly cototient number.

'Number of solutions to x − φ(x) = k'''''	1	∞	1	1	2	1	1	2	3	2	0	2	3	2	1	2	3	3	1	3	1	3	1	4	4	3	0	4	1	4	3

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

Primes

The first few highly cototient numbers which are primes are

: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, ...

References

{{Cite OEIS. A100827
{{Cite OEIS. A105440

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

integer-sequences

Want to explore this topic further?

Ask Mako anything about Highly cototient number — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report