A378508 -id:A378508 - cp's OEIS frontend

A378506 The number of solutions to the equation phi(phi(x)) = n, where phi is the Euler totient function.

5, 8, 0, 13, 0, 4, 0, 23, 0, 2, 0, 14, 0, 0, 0, 36, 0, 2, 0, 5, 0, 2, 0, 32, 0, 0, 0, 2, 0, 0, 0, 54, 0, 0, 0, 11, 0, 0, 0, 23, 0, 0, 0, 5, 0, 0, 0, 66, 0, 0, 0, 2, 0, 4, 0, 3, 0, 0, 0, 2, 0, 0, 0, 78, 0, 0, 0, 0, 0, 0, 0, 38, 0, 0, 0, 0, 0, 0, 0, 41, 0, 2, 0, 6

Offset: 1

Amiram Eldar, Nov 29 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
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. A000010, A010554, A014197, A378507, A378508.

a[n_] := Sum[PhiMultiplicity[i], {i, PhiInverse[n]}]; Array[a, 100] (* using David M. Bressoud's CNT.m *)

a(n) = vecsum(apply(x -> invphiNum(x), invphi(n))); \\ using Max Alekseyev's invphi.gp

a(n) > 0 if and only if n is in A378508.

A378509 Totient numbers k for which there is no solution to the equation phi(phi(x)) = k.

Original entry on oeis.org

30, 42, 46, 58, 66, 70, 78, 102, 106, 110, 116, 126, 136, 138, 140, 148, 150, 166, 196, 198, 210, 222, 226, 228, 262, 268, 270, 282, 294, 296, 306, 310, 316, 330, 332, 342, 346, 366, 372, 378, 382, 388, 392, 438, 444, 452, 456, 460, 462, 466, 478, 498, 502, 506

Offset: 1

Amiram Eldar, Nov 29 2024

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
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.

Intersection of A002202 (totient numbers) and the complement of A378508.

Cf. A000010, A010554, A378510.

q[k_] := Module[{v = PhiInverse[k]}, Length[v] > 0 && AllTrue[v, PhiMultiplicity[#] == 0 &]]; Select[Range[1000], q] (* using David M. Bressoud's CNT.m *)

is(k) = {my(v = invphi(k)); if(#v == 0, return(0)); for(i = 1, #v, if(istotient(v[i]), return(0))); 1;} \\ using Max Alekseyev's invphi.gp

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.

A380604 Numbers k such that there is no number i such that A046144(i) = 2*k.

Original entry on oeis.org

7, 13, 15, 17, 19, 21, 23, 25, 28, 29, 31, 33, 34, 35, 37, 38, 39, 43, 45, 47, 49, 51, 52, 53, 55, 57, 58, 59, 61, 62, 63, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 83, 85, 87, 91, 92, 93, 94, 97, 98, 99, 101, 103, 104, 105, 107, 109, 111, 112, 113, 114, 115, 117, 118

Offset: 1

David James Sycamore, Jan 28 2025

nonn

2*a(n) are the even numbers which are not in A378508, namely numbers 2*m for which no number exists which has 2*m primitive roots. See A380594 for discussion of even numbers which are not in this sequence.

			 There is no x such that A046144(x) = 14, so 7 is a term in this sequence (see also A380594).

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, A378508, A380594.

q[n_] := Count[Join @@ PhiInverse[PhiInverse[2*n]], ?(IntegerQ[PrimitiveRoot[#]] &)] == 0; Select[Range[120], q] (* _Amiram Eldar, Jan 28 2025, using David M. Bressoud's CNT.m *)

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

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

A378506 The number of solutions to the equation phi(phi(x)) = n, where phi is the Euler totient function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378509 Totient numbers k for which there is no solution to the equation phi(phi(x)) = k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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

A380604 Numbers k such that there is no number i such that A046144(i) = 2*k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions