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

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, 8, 24, 6, 12, 28, 16, 8, 20, 24, 24, 12, 24, 18, 16, 40, 12, 40, 22, 32, 12, 40, 32, 24, 52, 36, 48, 28, 40, 16, 40, 36, 48, 20, 64, 44, 24, 24, 72, 40, 48, 24, 18, 54

Offset

1,5

Comments

Essentially sequence A046144 with all zero entries deleted.

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

Formula

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

Mathematica

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

Prog

(PARI) is(n)=if(n%2, isprimepower(n) || n==1, n==2 || n==4 || (isprimepower(n/2, &n) && n>2));
lista(nn) = for (n=1, nn, if (is(n), print1(eulerphi(eulerphi(n)), ", "))); \\ Michel Marcus, May 12 2017
(Python)
from sympy import primepi, integer_nthroot, totient
def A072209(n):
    def bisection(f, kmin=0, kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    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)))
    return totient(totient(bisection(f, n, n))) # Chai Wah Wu, Feb 24 2025

Crossrefs

Cf. A033948, A046144.

Sequence in context: A208216 A208217 A009213 * A226559 A060169 A117958

Adjacent sequences: A072206 A072207 A072208 * A072210 A072211 A072212

Keyword

nice,nonn

Author

Lekraj Beedassy, Jul 03 2002

Status

approved