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

Author

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

Keywords

• nonn

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.

Examples

			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;
  ...
		

Links

• 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.

Crossrefs

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

Programs

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 *)

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

Formula

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