A072209 - OEIS

%I #25 Feb 25 2025 07:16:40

%S 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 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 36,48,28,40,16,40,36,48,20,64,44,24,24,72,40,48,24,18,54

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

%C Essentially sequence A046144 with all zero entries deleted.

%H T. D. Noe, <a href="/A072209/b072209.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = phi(phi(A033948(n))).

%t 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 Join[{1},(Length/@PrimitiveRootList[Range[300]])/.(0->Nothing)] (* _Harvey P. Dale_, Oct 01 2024 *)

%o (PARI) is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2, &n) && n>2));

%o lista(nn) = for (n=1, nn, if (is(n), print1(eulerphi(eulerphi(n)), ", "))); \\ _Michel Marcus_, May 12 2017

%o (Python)

%o from sympy import primepi, integer_nthroot, totient

%o def A072209(n):

%o     def bisection(f,kmin=0,kmax=1):

%o         while f(kmax) > kmax: kmax <<= 1

%o         kmin = kmax >> 1

%o         while kmax-kmin > 1:

%o             kmid = kmax+kmin>>1

%o             if f(kmid) <= kmid:

%o                 kmax = kmid

%o             else:

%o                 kmin = kmid

%o         return kmax

%o     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     return totient(totient(bisection(f,n,n))) # _Chai Wah Wu_, Feb 24 2025

%Y Cf. A033948, A046144.

%K nice,nonn

%O 1,5

%A _Lekraj Beedassy_, Jul 03 2002