A380594 a(n) is the number of positive integers having 2*n primitive roots.

6, 4, 4, 6, 2, 8, 0, 4, 2, 2, 2, 8, 0, 2, 0, 4, 0, 4, 0, 12, 0, 2, 0, 12, 0, 2, 4, 0, 0, 2, 0, 6, 0, 0, 0, 10, 0, 0, 0, 2, 2, 6, 0, 4, 0, 2, 0, 12, 0, 2, 0, 0, 0, 4, 0, 6, 0, 0, 0, 10, 0, 0, 0, 6, 2, 2, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 2, 0, 8, 4, 2, 0, 6, 0

Offset

1,1

Comments

Let [n] be the set {k; A046144(k) = 2*n}; n >= 1, then a(n) = |[n]|.

If 2*n is a term in A378508, [n] is nonempty and a(n) > 0. Otherwise, if 2*n is not in A378508 then there is no number having 2*n primitive roots, so a(n) = 0; see Example, and A380604.

Links

Table of n, a(n) for n=1..85.

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

David M. Bressoud, A Course in Computational Number Theory (web page), CNT.m, Computational Number Theory Mathematica package.

Formula

a(n) <= A378506(2*n), with equality iff n is in A007617.

Example

For n = 1, 2*n = 2 and there are 6 distinct numbers having 2 primitive roots; [2] = {5,7,9,10,14,18}; so a(10) = 6.
For n = 5, 2*n = 10 and there are just 2 distinct numbers having 10 primitive roots; [5] = {23,46}; so a(5) = 2.
For n = 7, 2*n = 14 and there are no numbers having 14 primitive roots, so a(7) = 0.
The sets [n] listed in rows start as follows; length of row n = a(n):
  n          [n]                   a(n)
  1    {5,7,9,10,14,18}             6;
  2    {11,13,22,26}                4;
  3    {29,27,30,54}                4;
  4    {17,25,31,34,50,62}          6;
  5    {23,46}                      2;
  6    {29,37,43,49,58,74,86,98}    8;
  7    { }                          0;
  8    {41,61,82,122}               4;
  9    {81,162}                     2;
  10   {67,134}                     2;
  ...

Mathematica

a[n_] := Count[Join @@ PhiInverse[PhiInverse[2*n]], _?(IntegerQ[PrimitiveRoot[#]] &)]; Array[a, 100] (* Amiram Eldar, Jan 27 2025, using David M. Bressoud's CNT.m *)

Prog

(PARI) isA033948(n) = {my(f = factor(n)); lcm(znstar(f)[2]) == eulerphi(f); }
a(n) = {my(v = invphi(2*n), w, c = 0); for(i = 1, #v, c += vecsum(apply(x -> isA033948(x), invphi(v[i])))); c; } \\ Amiram Eldar, Jan 27 2025, using Max Alekseyev's invphi.gp

Crossrefs

Cf. A046144, A007617, A010554, A033949, A231772, A378506, A378508, A380604.

Sequence in context: A338303 A316162 A332431 * A198840 A211268 A021612

Adjacent sequences: A380591 A380592 A380593 * A380595 A380596 A380597

Keyword

nonn

Author

David James Sycamore, Michael De Vlieger, and Amiram Eldar, Jan 27 2025

Status

approved