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

%I #10 Feb 11 2014 19:05:30

%S 2,2,6,8,26,21,110,128,342,410,1862,1365,7562,7022,17477,32768,123362,

%T 87381,496694,419430,1198373,1906502,8023886,5592405,26843546,

%U 30973322,89478486,115043767,518358122,286331153,2078209982,2147483648,5206020966,8084644322

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

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

%e 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.

%t 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}]

%K nonn

%O 1,1

%A _Joseph L. Pe_, Oct 04 2002

%E a(16)-a(34) from _Donovan Johnson_, Nov 03 2011