cp's OEIS Frontend

A072209 Number of primitive roots of those integers with at least one primitive root.

%I A072209 #25 Feb 25 2025 07:16:40
%S A072209 1,1,1,1,2,1,2,2,2,4,4,2,8,2,6,4,10,8,4,6,12,8,8,12,6,16,12,10,22,12,
%T A072209 8,24,6,12,28,16,8,20,24,24,12,24,18,16,40,12,40,22,32,12,40,32,24,52,
%U A072209 36,48,28,40,16,40,36,48,20,64,44,24,24,72,40,48,24,18,54
%N A072209 Number of primitive roots of those integers with at least one primitive root.
%C A072209 Essentially sequence A046144 with all zero entries deleted.
%H A072209 T. D. Noe, <a href="/A072209/b072209.txt">Table of n, a(n) for n = 1..10000</a>
%F A072209 a(n) = phi(phi(A033948(n))).
%t A072209 Reap[ Do[ If[n == 1, Sow[1], If[ IntegerQ[ PrimitiveRoot[n]], Sow[ EulerPhi[ EulerPhi[n]]]]] , {n, 1, 100}]][[2, 1]] (* _Jean-François Alcover_, Feb 24 2012 *)
%t A072209 Join[{1},(Length/@PrimitiveRootList[Range[300]])/.(0->Nothing)] (* _Harvey P. Dale_, Oct 01 2024 *)
%o A072209 (PARI) is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2, &n) && n>2));
%o A072209 lista(nn) = for (n=1, nn, if (is(n), print1(eulerphi(eulerphi(n)), ", "))); \\ _Michel Marcus_, May 12 2017
%o A072209 (Python)
%o A072209 from sympy import primepi, integer_nthroot, totient
%o A072209 def A072209(n):
%o A072209     def bisection(f,kmin=0,kmax=1):
%o A072209         while f(kmax) > kmax: kmax <<= 1
%o A072209         kmin = kmax >> 1
%o A072209         while kmax-kmin > 1:
%o A072209             kmid = kmax+kmin>>1
%o A072209             if f(kmid) <= kmid:
%o A072209                 kmax = kmid
%o A072209             else:
%o A072209                 kmin = kmid
%o A072209         return kmax
%o A072209     def f(x): return int(n-1+x-(x>=2)-(x>=4)-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))-sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
%o A072209     return totient(totient(bisection(f,n,n))) # _Chai Wah Wu_, Feb 24 2025
%Y A072209 Cf. A033948, A046144.
%K A072209 nice,nonn
%O A072209 1,5
%A A072209 _Lekraj Beedassy_, Jul 03 2002