To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

# 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. 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.[citation needed]

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 ${\displaystyle x}$ is defined as ${\displaystyle x-\phi (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 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.

(sequence A063740 in the OEIS)

 k (highly cototient k are bolded) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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 ${\displaystyle k-\phi (k)=n}$ number of ks such that ${\displaystyle k-\phi (k)=n}$ (sequence A063740 in the OEIS) 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

## Primes

The first few highly cototient numbers which are primes 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, ... (sequence A105440 in the OEIS)

## References

1. ^ Sloane, N. J. A. (ed.). "Sequence A100827 (Highly cototient numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..
2. ^ Sloane, N. J. A. (ed.). "Sequence A105440 (Highly cototient numbers that are prime)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.