A027413 If n is an odd prime, a(n) = the number of primitive roots mod n, otherwise a(n) = the number of k < n divisible by at least one but not all of the prime factors of n.

0, 0, 1, 0, 2, 3, 2, 0, 0, 5, 4, 6, 4, 7, 6, 0, 8, 9, 6, 10, 8, 11, 10, 12, 0, 13, 0, 14, 12, 21, 8, 0, 12, 17, 10, 18, 12, 19, 14, 20, 16, 29, 12, 22, 18, 23, 22, 24, 0, 25, 18, 26, 24, 27, 14, 28, 20, 29, 28, 42, 16, 31, 24, 0, 16, 45, 20, 34, 24, 45, 24, 36, 24, 37, 30, 38, 16

Offset

1,5

Comments

Old name was: "Number of primitive solutions of system "for all 2<=i<=n, k^i > 1 mod n"."

The meaning of "primitive" is twofold: (i) Because k^i == (k+n)^i (mod n), we admit only solutions k where k is the representative 2<=k<n. (ii) For prime n, the residue k^i==1 (mod n) is unavoidable if we let i run through the numbers counted by phi(n). So we also admit solutions k where the set of {k^i mod n} is the full {1,2,...,n-1}. - R. J. Mathar, Robert Israel, Jun 09 2016

If n is an odd prime, a(n) = A000010(n-1). If n is composite, a(n) = n-n(1+A173557(n))/A007947(n). - Robert Israel, Jun 09 2016

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Maple

A027413 := proc(n)
    local a, k, i, kimods ;
    a := 0 ;
    for k from 2 to n-1 do
        kimods := {} ;
        for i from 2 to n do
            kimods := kimods union {modp(k^i, n)};
        end do:
        if min(op(kimods)) > 1 or nops(kimods) = n-1 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Jun 09 2016
f:= proc(n)
local F, q, r;
   if isprime(n) then numtheory:-phi(n-1)
   else
     F:= numtheory:-factorset(n);
     q:= convert(F, `*`);
     r:= convert(map(`-`, F, 1), `*`);
     n*(q-r-1)/q;
    fi;
end proc:
f(2):= 0: f(1):= 0:
map(f, [$1..1000]); # Robert Israel, Jun 09 2016

Mathematica

f[n_] := Module[{F, q, r}, If[PrimeQ[n], EulerPhi[n-1], F = FactorInteger[ n][[All, 1]]; q = Times @@ F; r = Times @@ (F-1); n(q-r-1)/q]];
f[2] = 0; f[1] = 0;
f /@ Range[100] (* Jean-François Alcover, Aug 15 2020, after Robert Israel *)

Crossrefs

Cf. A000010, A007947, A173557.

Sequence in context: A363841 A291293 A259572 * A379820 A343230 A019509

Adjacent sequences: A027410 A027411 A027412 * A027414 A027415 A027416

Keyword

nonn

Author

Sandor Adrian (sandor(AT)skylab.math.unibuc.ro), Olivier Gérard

Extensions

Better definition from Robert Israel, Jun 09 2016

Status

approved