This site is supported by donations to The OEIS Foundation.
Totatives and cototatives
The integers from 1 to that are coprime to are called the totatives of , while the remaining integers from 1 to are called cototatives.
Euler's totient function is the number of totatives of , while Euler's cototient function is the number of cototatives of .
Totatives
The set of totatives of is (see coprimality triangle)
where is the greatest common divisor (GCD) of and
Thus, Euler's totient function is the cardinality of the set of totatives of :
(Note that in the following table, most of the listed sequences are infinite, and thus we're referring to the subset of that sequence of all terms smaller than ).
Totatives of | A-number | Totient of A000010 | |
---|---|---|---|
1 | {1} | 1 | |
2 | {1} | 1 | |
3 | {1, 2} | 2 | |
4 | {1, 3} | 2 | |
5 | {1, 2, 3, 4} | 4 | |
6 | {1, 5} | 2 | |
7 | {1, 2, 3, 4, 5, 6} | 6 | |
8 | {1, 3, 5, 7} | 4 | |
9 | {1, 2, 4, 5, 7, 8} | A001651 | 6 |
10 | {1, 3, 7, 9} | 4 | |
11 | {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} | 10 | |
12 | {1, 5, 7, 11} | 4 | |
13 | {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} | 12 | |
14 | {1, 3, 5, 9, 11, 13} | 6 | |
15 | {1, 2, 4, 7, 8, 11, 13, 14} | 8 | |
16 | {1, 3, 5, 7, 9, 11, 13, 15} | 8 | |
17 | {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} | 16 | |
18 | {1, 5, 7, 11, 13, 17} | 6 | |
19 | {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18} | 18 | |
20 | {1, 3, 7, 9, 11, 13, 17, 19} | 8 | |
21 | {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} | 12 | |
22 | {1, 3, 5, 7, 9, 13, 15, 17, 19, 21} | 10 | |
23 | {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22} | 22 | |
24 | {1, 5, 7, 11, 13, 17, 19, 23} | 8 | |
25 | {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24} | 20 | |
26 | {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} | 12 | |
27 | {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26} | A001651 | 18 |
28 | {1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27} | 12 | |
29 | {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} | 28 | |
30 | {1, 7, 11, 13, 17, 19, 23, 29} | 8 |
The totatives yields the infinite sequence of finite sequences
- {{1}, {1}, {1, 2}, {1, 3}, {1, 2, 3, 4}, {1, 5}, {1, 2, 3, 4, 5, 6}, {1, 3, 5, 7}, {1, 2, 4, 5, 7, 8}, {1, 3, 7, 9}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 5, 7, 11}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {1, 3, 5, 9, 11, 13}, ...}
whose concatenation gives:
A038566 Numerators in canonical bijection from positive integers to positive rationals <= 1: arrange fractions by increasing denominator then by increasing numerator.
- {1, 1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 7, 1, 2, 4, 5, 7, 8, 1, 3, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 5, 7, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 5, 9, 11, 13, ...}
A000010 Euler's totient function (count of numbers up to and coprime to ).
- {1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, ...}
All totients for are even, since is a totative if and only if is a totative, while obviously can't be a totative of .
Isolated totatives
An isolated totative, , of is a positive integer which is less than and coprime to and such that neither nor are coprime to .
A132952 = number of isolated totatives of .
- {0, 1, 0, 2, 0, 2, 0, 4, 0, 4, 0, 4, 0, 6, 2, 8, 0, 6, 0, 8, 2, 10, 0, 8, 0, 12, 0, 12, 0, 8, 0, 16, 2, 16, 2, 12, 0, 18, 2, 16, 0, 12, 0, 20, 6, 22, 0, 16, 0, 20, 2, 24, 0, ...}
A132953 = the sum of the isolated totatives of .
- {0, 1, 0, 4, 0, 6, 0, 16, 0, 20, 0, 24, 0, 42, 15, 64, 0, 54, 0, 80, 21, 110, 0, 96, 0, 156, 0, 168, 0, 120, 0, 256, 33, 272, 35, 216, 0, 342, 39, 320, 0, 252, 0, 440, 135, ...}
Cototatives
The set of cototatives of is (see coprimality triangle)
where is the greatest common divisor (GCD) of and
Thus, Euler's cototient function is the cardinality of the set of cototatives of :