In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, a branch of
mathematics, a highly cototient number is a positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
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
:
=
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
119 may refer to:
* 119 (number), a natural number
* 119 (emergency telephone number)
* AD 119, a year in the 2nd century AD
* 119 BC, a year in the 2nd century BC
* 119 (album), 2012
* 119 (NCT song)
*119 (Show Me the Money song)
* 119 (film), a ...
,
167,
209,
269
Year 269 (Roman numerals, CCLXIX) was a common year starting on Friday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Claudius and Paternus (or, less frequently, year 102 ...
, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, ...
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 number
__FORCETOC__
A highly composite number is a positive integer with more divisors than any smaller positive integer has. The related concept of largely composite number refers to a positive integer which has at least as many divisors as any smaller ...
s. 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 (one number in each case), so 4 is a highly cototient number.
Primes
The first few highly cototient numbers which are
primes
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
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, ...
See also
*
Highly totient number
References
{{Classes of natural numbers
Integer sequences