A380604 -id:A380604 - cp's OEIS frontend

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

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.

A379883 a(1) = 1. Let j = a(n-1) and r = A046144(j). Then for n > 1, if j is novel and r > 0, a(n) = r. If j is novel and r = 0 then a(n) = 1. If j has occurred k (>1) times already then a(n) = k*j.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 1, 5, 2, 4, 8, 1, 6, 1, 7, 2, 6, 12, 1, 8, 16, 1, 9, 2, 8, 24, 1, 10, 2, 10, 20, 1, 11, 4, 12, 24, 48, 1, 12, 36, 1, 13, 4, 16, 32, 1, 14, 2, 12, 48, 96, 1, 15, 1, 16, 48, 144, 1, 17, 8, 32, 64, 1, 18, 2, 14, 28, 1, 19, 6, 18, 36, 72, 1, 20, 40, 1, 21, 1, 22, 4, 20, 60, 1, 23, 10, 30, 1, 24, 72, 144, 288, 1, 25, 8, 40, 80, 1, 26, 4

Offset: 1

David James Sycamore, Jan 09 2025

In other words if j = a(n-1) has not occurred earlier and has r (> 0) primitive roots then a(n) = r. Cases where novel A046144(j) = 0 cannot be counted multiplicatively (as k*j) for repeats, so a(n) = 1 is designed to permit the sequence to continue past such points, which means including in the count of 1's terms following (1,2,3,4,6), for which it is true that r = 1. Terms beyond a(12) = 8 which count the number of 1's (by the second condition) give the cardinality of terms with no primitive roots, plus the few (5) cases of terms with primitive root = 1.

Every even number m in A380594 appears finitely many times, consequent to occasions of integers v (>6) for which A046144(v) = m, and to repetitions (k*j) = m for j even. However every odd number appears once only (consequent to odd counts of 1's). The odd numbers appear in order, and since 2 precedes all of them, the primes are in order.

			a(2) = 1 since a(1)=1 and and 1 has one primitive root. Since 1 has been seen twice, a(3) = 2 and then a(4) = 1 since 2 is a novel term with one primitive root.
a(9) = 5, a novel term with two primitive roots so a(10) = 2, which has appeared once before (a(3)=2), so a(11) = 4, the second occurrence of 4 so a(12) = 8, a novel term with no primitive roots, meaning that a(13) = 1. The count of 1's is now 6, so a(14) = 6, meaning 5 prior terms with one primitive root and one with none.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^20.

Cf. A046144, A378508, A380594, A380604.

nn = 120; c[_] := 0; j = 1;
f[x_] := f[x] = Which[
  x == 1, 1,
  IntegerQ[PrimitiveRoot[x]], Nest[EulerPhi, x, 2],
  True, 0];
{j}~Join~Reap[Monitor[Do[
  If[c[j] == 0,
    Set[k, # + Boole[# == 0]] &[f[j]]; c[j]++,
    k = ++c[j]*j ];
j = Sow[k], {n, 2, nn}], n] ][[-1, 1]] (* Michael De Vlieger, Jan 09 2025 *)

a(78)=1 inserted by David Radcliffe, Aug 03 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula