This site is supported by donations to The OEIS Foundation.

Totatives and cototatives

From OeisWiki
(Redirected from Totatives)
Jump to: navigation, search


This article page is a stub, please help by expanding it.


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 ).

Table of totatives
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 :

See also