A231772 -id:A231772 - cp's OEIS frontend

A231773 Numbers k such that there are no numbers with k primitive roots.

3, 5, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 50, 51, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95

Offset: 1

Arkadiusz Wesolowski, Nov 13 2013

nonn

Numbers k such that A231772(k) = 0.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A007617, A010554, A046144, A231772.

r=95; for(n=2, r, m=0; for(c=2*n+1, n^2+1, if(n%2==1, break); e=eulerphi(c); if(e==lcm(znstar(c)[2])&&eulerphi(e)==n, m=1; break)); if(m==0, print1(n, ", ")));

a(n) = A007617(n) for n <= 16.

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

Original entry on oeis.org

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

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

nonn

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.

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

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.

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

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

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

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

cp's OEIS Frontend

A231773 Numbers k such that there are no numbers with k primitive roots.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula