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

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{d|n} mu(d)*floor(2^n/d). - Ridouane Oudra, Mar 26 2025

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.

Maple

with(numtheory): seq(add(mobius(d)*floor(2^n/d), d in divisors(n)), n=1..60); # Ridouane Oudra, Mar 26 2025

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

Cf. A000079.

Sequence in context: A383802 A275441 A197465 * A383372 A157253 A003178

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