A010554 -id:A010554 - cp's OEIS frontend

A219027 Number of non-primitive roots for n, less than n.

0, 0, 1, 2, 2, 4, 4, 7, 6, 7, 6, 11, 8, 11, 14, 15, 8, 15, 12, 19, 20, 17, 12, 23, 16, 21, 20, 27, 16, 29, 22, 31, 32, 25, 34, 35, 24, 31, 38, 39, 24, 41, 30, 43, 44, 35, 24, 47, 36, 41, 50, 51, 28, 47, 54, 55, 56, 45, 30, 59, 44, 53, 62, 63, 64, 65, 46, 67, 68

Offset: 1

V. Raman, Nov 10 2012

nonn

a(n) will be the same as A219029(n) except when n is a member of A033949 or n = 1, i.e. n is not 2, 4, prime, power of a prime, twice a prime, or twice a prime power. In such cases, when n is a member of A033949, then a(n) = n-1.

Cf. A008330 (number of primitive roots for the n-th prime, less than n-th prime).
Cf. A046144 (number of primitive roots for n, less than n).
Cf. A010554 (value of phi(phi(n))).
Cf. A219029.

for(i=1,100,p=0;for(q=1,i-1,if(gcd(q,i)>1||znorder(Mod(q,i))!=eulerphi(i),p++));print1(p","))

n-1-A046144(n).

A300064 Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 30, 31, 32, 34, 35, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 58, 59, 60, 61, 62, 64, 67, 68, 70, 71, 73, 74, 75, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 94, 95, 96, 97, 98, 100, 101, 102, 103, 104, 105, 106, 107, 109, 110

Offset: 1

Max Alekseyev, Feb 23 2018

nonn

Numbers k such that A111725(k) = A010554(k).
Contains subsequences of the primes (A000040) and the prime powers (A000961) except 2^3 = 8.
The ratio a(n)/n tends to infinity as n grows (Müller and Schlage-Puchta, 2004).
Decompose (Z/kZ)* as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then k is a term if and only if m <= 1, or v(k_{m-1},p) < v(k_m,p) holds for all primes p dividing k_m = psi(k), where v(s,p) is the p-adic valuation of s. Otherwise, there are more than phi(phi(k)) residues modulo k of the maximum order. See my Oct 12 2021 formula for A111725 for a proof. - Jianing Song, Oct 20 2021

Amiram Eldar, Table of n, a(n) for n = 1..10000
Peter J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
T. W. Müller and J.-C. Schlage-Puchta, On the number of primitive lambda-roots, Acta Arithmetica, Vol. 115 (2004), pp. 217-223.

Complement of A300065.
Set union of A300079 and A000040.
Set union of A300080 and A000961 \ {8}.
Cf. A000010, A002322, A010554, A111725.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[100], q] (* Amiram Eldar, Oct 12 2021 *)

isA300064(n) = my(v=znstar(n)[2], l=#v); if(l<2, return(1), my(U=v[1], L=v[2], d=factor(U), w=omega(U)); for(i=1, w, if(valuation(L,d[i,1]) == d[i,2], return(0))); return(1)) \\ Jianing Song, Oct 20 2021

A300065 Numbers k such that the number of residues modulo k of the maximum order is different from phi(phi(k)).

Original entry on oeis.org

8, 12, 21, 24, 28, 33, 36, 42, 44, 56, 57, 63, 65, 66, 69, 72, 76, 77, 80, 84, 88, 91, 92, 93, 99, 108, 114, 117, 124, 126, 129, 130, 132, 133, 138, 141, 145, 147, 152, 154, 161, 168, 171, 172, 177, 182, 184, 185, 186, 188, 189, 195, 196, 198, 201, 207, 208, 209, 213, 216, 217, 228, 231, 234, 236, 237, 240, 248, 249, 252, 253, 258, 260, 264, 265, 266, 268, 273, 275, 276, 279, 282

Offset: 1

Max Alekseyev, Feb 23 2018

nonn

Numbers k such that A111725(k) is not equal to A010554(k).

The ratio a(n)/n tends to 1 as n grows.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Peter J. Cameron and D. A. Preece, Primitive lambda-roots, 2014.
T. W. Müller and J.-C. Schlage-Puchta, On the number of primitive lambda-roots, Acta Arithmetica, Vol. 115 (2004), pp. 217-223.

Complement of A300064.
Union of {8} and set difference of A024619 and A300080.
Cf. A000010, A002322, A010554, A111725, A300079.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] != EulerPhi[EulerPhi[n]]; Select[Range[300], q] (* Amiram Eldar, Oct 12 2021 *)

A300079 Composite numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

4, 6, 9, 10, 14, 15, 16, 18, 20, 22, 25, 26, 27, 30, 32, 34, 35, 38, 39, 40, 45, 46, 48, 49, 50, 51, 52, 54, 55, 58, 60, 62, 64, 68, 70, 74, 75, 78, 81, 82, 85, 86, 87, 90, 94, 95, 96, 98, 100, 102, 104, 105, 106, 110, 111, 112, 115, 116, 118, 119, 120, 121, 122, 123, 125, 128, 134, 135, 136, 140, 142, 143, 144, 146, 148, 150, 153

Offset: 1

Max Alekseyev, Feb 24 2018

nonn

Composite numbers k such that A111725(k) = A010554(k).

Contains as a subsequence the nontrivial prime powers (A246547) except 2^3 = 8.

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

Subsequence of A300064.
Set difference of A002808 and A300065.
Contains A300080 as a subsequence.
Cf. A000010, A002322, A010554, A111725, A246547.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[150], CompositeQ[#] && q[#] &] (* Amiram Eldar, Oct 12 2021 *)

A300080 Numbers k that are not prime powers, and have exactly phi(phi(k)) residues modulo k of the maximum order.

Original entry on oeis.org

6, 10, 14, 15, 18, 20, 22, 26, 30, 34, 35, 38, 39, 40, 45, 46, 48, 50, 51, 52, 54, 55, 58, 60, 62, 68, 70, 74, 75, 78, 82, 85, 86, 87, 90, 94, 95, 96, 98, 100, 102, 104, 105, 106, 110, 111, 112, 115, 116, 118, 119, 120, 122, 123, 134, 135, 136, 140, 142, 143, 144, 146, 148, 150, 153, 155, 156, 158, 159, 160, 162, 164, 165, 166

Offset: 1

Max Alekseyev, Feb 24 2018

nonn

Numbers k with at least two distinct prime factors (A024619) such that A111725(k) = A010554(k).

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

Set difference of: A300064 and A000961, A300079 and A246547, A024619 and A300065.

Cf. A000010, A002322, A010554, A111725.

q[n_] := Count[(t = Table[MultiplicativeOrder[k, n], {k, Select[Range[n], CoprimeQ[n, #] &]}]), Max[t]] == EulerPhi[EulerPhi[n]]; Select[Range[200], PrimeNu[#] > 1 && q[#] &] (* Amiram Eldar, Oct 12 2021 *)

A053470 a(n) is the cototient of n (A051953) iterated twice.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 4, 0, 4, 1, 4, 0, 8, 0, 8, 3, 8, 0, 8, 1, 8, 3, 8, 0, 12, 0, 8, 1, 12, 1, 16, 0, 12, 7, 16, 0, 22, 0, 16, 9, 16, 0, 16, 1, 22, 1, 16, 0, 24, 7, 16, 9, 22, 0, 24, 0, 16, 9, 16, 1, 24, 0, 24, 5, 24, 0, 32, 0, 20, 11, 24, 1, 36, 0, 32, 9, 30, 0, 44, 9, 24, 1, 32, 0

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Iteration of A051953 is ended at fixed point 0. Analogous 2nd iterates for number of divisors (A000005) and Euler-Phi (A000010) are A036454 and A010554.

			n=50, n_1 = n - phi(n) = 50 - 20 = 30, n_2 = n_1 - Phi(n_1) = 30 - 8 = 22, so the 50th term is 22.

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A051953, A000005, A000010, A036454, A010554.

Cf. A053471, A053472, A053473.

Array[Nest[# - EulerPhi@ # &, #, 2] &, 89] (* Michael De Vlieger, Dec 23 2017 *)

A051953(n) = (n-eulerphi(n));
A053470(n) = if(1==n,0,A051953(A051953(n))); \\ Antti Karttunen, Dec 22 2017

a(1) = 0; for n > 1, a(n) = A051953(A051953(n)).

A290086 a(n) = A289626(A000010(n)).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 5, 2, 5, 5, 8, 2, 4, 5, 5, 3, 6, 5, 8, 5, 4, 5, 11, 5, 8, 8, 8, 8, 13, 5, 11, 4, 13, 8, 21, 5, 11, 8, 13, 6, 12, 8, 11, 8, 17, 13, 19, 4, 21, 13, 11, 11, 15, 8, 21, 8, 11, 17, 21, 8, 18, 17, 18, 13, 19, 13, 28, 11, 21, 11, 21, 13, 19, 17, 10, 21, 22, 13, 25, 11, 28, 21, 45, 13, 28, 18, 21, 12, 28, 17, 49, 11, 21, 21, 27, 17

Offset: 1

Antti Karttunen, Aug 07 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000010, A010554, A077197, A277906, A289626, A290085, A290087, A290088.

a(n) = A289626(A000010(n)).

A293516 a(n) = phi(n) - 2*phi(phi(n)), where phi = Euler totient function, A000010.

Original entry on oeis.org

-1, -1, 0, 0, 0, 0, 2, 0, 2, 0, 2, 0, 4, 2, 0, 0, 0, 2, 6, 0, 4, 2, 2, 0, 4, 4, 6, 4, 4, 0, 14, 0, 4, 0, 8, 4, 12, 6, 8, 0, 8, 4, 18, 4, 8, 2, 2, 0, 18, 4, 0, 8, 4, 6, 8, 8, 12, 4, 2, 0, 28, 14, 12, 0, 16, 4, 26, 0, 4, 8, 22, 8, 24, 12, 8, 12, 28, 8, 30, 0, 18, 8, 2, 8, 0, 18, 8, 8, 8, 8, 24, 4, 28, 2, 24, 0, 32

Offset: 1

Antti Karttunen, Nov 27 2017

sign

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A010554, A051953, A070556, A083254, A295660.

Cf. A003401 (gives the positions of zeros after the two initial -1's).

A293516(n) = (eulerphi(n) - 2*eulerphi(eulerphi(n)));

a(n) = A000010(n) - 2*A010554(n).
a(n) = A070556(n) - A010554(n).
a(n) = -A083254(A000010(n)).

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

Original entry on oeis.org

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.

A068580 Let phi_m(x) = phi(phi(...(phi(x))...)) m times; sequence gives values of k such that phi_2(k) = tau(k).

Original entry on oeis.org

1, 5, 7, 15, 21, 22, 26, 40, 56, 66, 70, 78, 108, 120, 126, 168, 210

Offset: 1

Benoit Cloitre, Mar 26 2002

Numbers k such that A010554(k) = A000005(k).

Cf. A000005, A000010, A010554, A068579, A068581, A068582.

Select[Range[210], Nest[EulerPhi, #, 2] === DivisorSigma[0, #] &] (* Amiram Eldar, Jun 12 2022 *)

is(k) = numdiv(k) == eulerphi(eulerphi(k)); \\ Jinyuan Wang, Apr 05 2020

cp's OEIS Frontend

A219027 Number of non-primitive roots for n, less than n.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A300064 Numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A300065 Numbers k such that the number of residues modulo k of the maximum order is different from phi(phi(k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A300079 Composite numbers k such that there are exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A300080 Numbers k that are not prime powers, and have exactly phi(phi(k)) residues modulo k of the maximum order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A053470 a(n) is the cototient of n (A051953) iterated twice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290086 a(n) = A289626(A000010(n)).

Views

Author

Keywords

Links

Crossrefs

Formula

A293516 a(n) = phi(n) - 2*phi(phi(n)), where phi = Euler totient function, A000010.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links