login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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 (list; graph; refs; listen; history; text; internal format)
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: A106385 A291293 A259572 * A343230 A019509 A071484

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 10:11 EDT 2021. Contains 346447 sequences. (Running on oeis4.)