A074933 Number of integers in {1, 2, ..., 2^n} that are coprime to n.

2, 2, 6, 8, 26, 21, 110, 128, 342, 410, 1862, 1365, 7562, 7022, 17477, 32768, 123362, 87381, 496694, 419430, 1198373, 1906502, 8023886, 5592405, 26843546, 30973322, 89478486, 115043767, 518358122, 286331153, 2078209982, 2147483648, 5206020966, 8084644322

Offset

1,1

Comments

Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.

Links

Table of n, a(n) for n=1..34.

Example

There are six integers in {1, 2, ..., 2^3} that are coprime to 3, i.e. 1, 2, 4, 5, 7, 8. Hence a(3) = 6.

Mathematica

h[n_] := Module[{l}, l = {}; For[i = 1, i <= 2^n, i++, If[GCD[i, n] == 1, l = Append[l, i]]]; l]; Table[Length[h[i]], {i, 1, 15}]

Crossrefs

Sequence in context: A052957 A275441 A197465 * A157253 A003178 A079494

Adjacent sequences: A074930 A074931 A074932 * A074934 A074935 A074936

Keyword

nonn

Author

Joseph L. Pe, Oct 04 2002

Extensions

a(16)-a(34) from Donovan Johnson, Nov 03 2011

Status

approved