login
Number of positive integers not exceeding n that are relatively prime to phi(n).
1

%I #13 Sep 23 2024 11:59:00

%S 1,2,2,2,3,3,3,4,3,5,5,6,5,5,8,8,9,6,7,10,7,9,11,12,10,9,9,9,13,15,9,

%T 16,14,17,12,12,13,13,13,20,17,14,13,18,15,21,23,24,14,20,26,17,25,18,

%U 22,19,19,25,29,30,17,17,21,32,22,26,21,34,32,23,25,24,25,25,30,25,21

%N Number of positive integers not exceeding n that are relatively prime to phi(n).

%H David A. Corneth, <a href="/A072302/b072302.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{d|phi(n)} moebius(d)*floor(n/d). - _Ridouane Oudra_, May 12 2024

%e Among the positive integers not exceeding 12, the six numbers 1,3,5,7,9,11 are relatively prime to phi(12)=4. Hence a(12)=6.

%p with(numtheory) : seq(add(mobius(d)*floor(n/d), d in divisors(phi(n))) , n=1..100) ; # _Ridouane Oudra_, May 12 2024

%t r = {}; Do[s = EulerPhi[n]; j = 0; For[i = 1, i <= n, i++, If[GCD[s, i] == 1, j++ ]]; r = Append[r, j], {n, 1, 10^2}]; r

%o (PARI) a(n) = my(d = divisors(eulerphi(n))); sum(i = 1, #d, moebius(d[i]) * floor(n / d[i])) \\ _David A. Corneth_, Sep 23 2024

%Y Cf. A000010, A008683.

%K nonn

%O 1,2

%A _Joseph L. Pe_, Jul 14 2002