A010554 -id:A010554 - cp's OEIS frontend

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

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.

A386261 a(n) = A001511(A001511(n)), where A001511 is the ruler function.

Original entry on oeis.org

1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1

Offset: 1

Amiram Eldar, Jul 17 2025

The first occurrence of k = 1, 2, ... is at n = 2^(2^(k-1) - 1) = A058891(k).

The asymptotic density of the occurrences of k = 1, 2, ... in this sequence is 2^(2^(k-1))/(2^(2^k)-1) = 2/3, 4/15, 16/255, 256/65535, 65536/4294967295, ...

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

Cf. A001511, A003159, A048649, A058891.

Similar sequences: A010553, A010554, A051027, A055033, A058699, A068346, A132090, A178601, A181776, A284908, A386262.

f[n_] := IntegerExponent[n, 2] + 1; a[n_] := f[f[n]]; Array[a, 100]

a(n) = valuation(valuation(n, 2) + 1, 2) + 1;

a(n) >= 1, with equality if and only if n is in A003159.

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Sum_{m>=0} 1/(2^(2^m) - 1) = 1.4039368... (A048649).

A386262 a(n) = A051903(A051903(n)) for n >= 2, a(1) = 0.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 0, 0, 1, 0, 0, 0

Offset: 1

Amiram Eldar, Jul 17 2025

The first occurrence of k = 1, 2, ... is at n = 2^(2^k) = A001146(k).
If n is an exponentially squarefree number (A209061) then a(n) <= 1. The converse is not necessarily true, with n = 2592 = 2^5 * 3^4 being the least counterexample.
The asymptotic density of the occurrences of 0 in this sequence is 1/zeta(2) = 6/Pi^2 (A059956).
The asymptotic density of the occurrences of 1 in this sequence is Sum_{k squarefree > 1} (1/zeta(k+1) - 1/zeta(k)) = 0.348423339572619656701... .

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

Cf. A005117, A001146, A051903, A059956, A209061.

Similar sequences: A010553, A010554, A051027, A055033, A058699, A068346, A132090, A178601, A181776, A284908, A386261.

f[n_] := Max[FactorInteger[n][[;; , 2]]]; f[1] = 0; a[n_] := f[f[n]]; a[1] = 0; Array[a, 100]

f(n) = if(n == 1, 0, vecmax(factor(n)[,2]));
a(n) = if(n == 1, 0, f(f(n)));

a(n) = 0 if and only if n is squarefree (A005117).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Sum_{k>=2} A051903(k) * (1/zeta(k+1)-1/zeta(k)) = 0.43779421197744649258... .

A063999 Numbers k such that the number of primes <= k is phi(phi(k)).

Original entry on oeis.org

2, 37, 55, 91, 95, 136, 178, 226, 507, 723, 1166, 1168, 1284, 1323, 2658, 3082, 7564, 8166, 11578, 12014, 12018, 12026, 15340, 40220, 50544, 55490, 56810, 69732, 89210, 100114, 100126, 111306, 131532, 226716, 226722, 232938, 519312, 683240, 849534

Offset: 1

Jason Earls, Sep 06 2001

nonn

			37 belongs to the sequence because number of primes <= 37 is equal to 12 (counting 2,3,5,7,11,13,17,19,23,29,31,37), while phi(37)=36 (counting 1,2,...,36) and phi(36)=12 (counting 1,5,7,11,13,17,19,23,25,29,31,35).

Harry J. Smith, Table of n, a(n) for n = 1..44

Cf. A000720, A010554.

with(numtheory): p:=proc(n) if pi(n)=phi(phi(n)) then n else fi end: seq(p(n), n=1..900000); #  Emeric Deutsch, Feb 24 2005

pi(n) = s=0; for(x=1,n, if(isprime(x),s++)); s; for(n=1,10^6, if(pi(n)==eulerphi(eulerphi(n)),print(n)))

{ default(primelimit, 2500000); n=0; for (m=1, 10^9, if (primepi(m)==eulerphi(eulerphi(m)), write("b063999.txt", n++, " ", m); if (n==44, break)) ) } \\ Harry J. Smith, Sep 05 2009

More terms from Emeric Deutsch, Feb 24 2005

A111409 a(n) = f(f(n+1)) - f(f(n)), where f(0)=0, and for m>0, f(m) = phi(m) = A000010(m).

Original entry on oeis.org

1, 0, 0, 0, 1, -1, 1, 0, 0, 0, 2, -2, 2, -2, 2, 0, 4, -6, 4, -2, 0, 0, 6, -6, 4, -4, 2, -2, 8, -8, 4, 0, 0, 0, 0, -4, 8, -6, 2, 0, 8, -12, 8, -4, 0, 2, 12, -14, 4, -4, 8, -8, 16, -18, 10, -8, 4, 0, 16, -20, 8, -8, 4, 4, 0, -8, 12, -4, 4, -12, 16, -16, 16, -12, 4, -4, 4, -8, 16, -8, 2, -2, 24, -32, 24, -20, 12, -8, 24, -32, 16, -4, -4, 6

Offset: 0

N. J. A. Sloane, Nov 12 2005

sign

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A000010 (phi).

First differences of A010554.

a:= n-> (f-> f(f(n+1))-f(f(n)))(numtheory[phi]):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 20 2022

Definition corrected by N. J. A. Sloane, Feb 14 2018

A163373 a(n) = phi(phi(sigma(n))).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 4, 4, 2, 2, 4, 2, 4, 4, 8, 2, 8, 4, 4, 8, 4, 4, 8, 8, 4, 8, 8, 4, 8, 8, 12, 8, 6, 8, 24, 6, 8, 8, 8, 4, 16, 8, 8, 8, 8, 8, 16, 12, 16, 8, 12, 6, 16, 8, 16, 16, 8, 8, 16, 8, 16, 16, 36, 8, 16, 16, 12, 16, 16, 8, 32, 12, 12, 16, 16, 16, 16, 16

Offset: 1

Jaroslav Krizek, Jul 25 2009

nonn

a(n) = A000010(A000010(A000203(n))) = A000010(A062401(n)) = A010554(A000203(n)).

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A000010, A000203, A010554, A062401.

[EulerPhi(EulerPhi(SumOfDivisors(n))): n in [1..80]]; // Vincenzo Librandi, Dec 20 2016

EulerPhi[EulerPhi[DivisorSigma[1, Range[100]]]] (* G. C. Greubel, Dec 20 2016 *)

vector(100, n, eulerphi(eulerphi(sigma(n)))) \\ G. C. Greubel, Dec 20 2016

a(n) = A000010(A000010(A000203(n))) = A000010(A062401(n)) = A010554(A000203(n)).

A173337 Numbers k>1 such that phi(phi(k)) = sigma(sopf(k)).

Original entry on oeis.org

40, 50, 54, 171, 195, 231, 330, 377, 387, 518, 638, 742, 745, 888, 1057, 1141, 1397, 1561, 1788, 2422, 2682, 2763, 3206, 3357, 3805, 4037, 4344, 4382, 4915, 5093, 5138, 5391, 5558, 5951, 6147, 8063, 8952, 9132, 9422, 10109, 10968, 11796, 12287, 12481

Offset: 1

Michel Lagneau, Feb 16 2010

nonn

			40 is in the sequence because phi(40)= 16, phi(16) = 8, sopf(40) = 7 and sigma(7) = 8;
171 is in the sequence because phi(171) = 108, phi(108) = 36, sopf(171) = 22 and sigma(22) = 36.

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

Cf. A000010 (Euler totient function), A000203 (sum of divisors), A008472 (sum of prime factors), A010554.

with(numtheory) :
A008472 := proc(n)
        add(p, p = factorset(n):
end proc:
isA173337 := proc(n)
        phi(phi(n)) = sigma(A008472(n)) ;
end proc:
for n from 1 do
        if isA173337(n) then printf("%d,",n) ; fi;
end do: # R. J. Mathar, Jul 06 2012

sopf[n_] := Plus @@ (First@# & /@ FactorInteger[n]); Select[Range[2, 13000], EulerPhi[EulerPhi[#]] == DivisorSigma[1, sopf[#]] &] (* Amiram Eldar, Jul 09 2019 *)
Select[Range[2,15000],DivisorSigma[1,Total[FactorInteger[#][[All,1]]]] == EulerPhi[ EulerPhi[#]]&] (* Harvey P. Dale, Apr 05 2020 *)

isok(n) = (n>1) && eulerphi(eulerphi(n)) == sigma(vecsum(factor(n)[, 1])); \\ Michel Marcus, Jul 10 2019

k such that A010554(k) = A000203(A008472(k)).

Definition clarified by N. J. A. Sloane, Apr 05 2020

A184968 Smallest k such that phi(phi(k)) = 2^n, where phi is the Euler totient function.

Original entry on oeis.org

5, 11, 17, 41, 85, 137, 257, 641, 1285, 2329, 4369, 10537, 17477, 35209, 65537, 163841, 297109, 557057, 1114129, 2687017, 4491589, 8978569, 16843009, 42009217, 71304257, 143163649, 286331153, 690563369, 1145390149, 2281701377, 4295098369, 10737647617

Offset: 1

Michel Lagneau, Mar 27 2011

nonn

			a(5) = 85 because phi(85) = 64, phi(64) = 2^5.

Robert Israel, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A010554.

with(numtheory):for n from 1 to 22 do: id:=0:for k from 1 to 10000000 while(id=0)
  do: if phi(phi(k)) =2^n then id:=1:print(k):else fi:od:od:
# Alternative:
f:= proc(n) local S,s,r;
  uses numtheory;
  S:= sort(convert(invphi(2^n),list));
  r:= infinity;
  for s in S while s < r do
    r:= min(r, min(invphi(s)))
  od;
  r
end proc:
map(f, [$1..50]); # Robert Israel, Mar 22 2017

a(n) = {my(v = invphi(2^n), m); for(i = 1, #v, m = invphiMin(v[i]); v[i] = max(m, 0)); vecmin(select(x -> x > 0, v)); } \\ Amiram Eldar, Nov 15 2024, using Max Alekseyev's invphi.gp

a(23)-a(32) from Donovan Johnson, Jul 28 2011

A229910 a(n) = |{0 < g < prime(n): both g and g + g^{-1} are primitive roots modulo prime(n)}|, where g^{-1} is the inverse of g modulo prime(n).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 4, 2, 4, 4, 2, 4, 8, 6, 10, 8, 14, 4, 4, 12, 8, 6, 20, 24, 16, 16, 12, 26, 8, 16, 14, 12, 24, 14, 32, 10, 20, 18, 40, 48, 44, 4, 30, 16, 32, 18, 14, 18, 56, 8, 60, 40, 12, 40, 64, 64, 72, 20, 40, 32, 36, 80, 22, 44, 24, 72, 22, 36, 86, 32, 84, 88, 40, 24, 28, 94, 104, 28, 76, 28

Offset: 1

Zhi-Wei Sun, Oct 03 2013

nonn

Conjecture: a(n) > 0 for all n > 6. In other words, for any prime p > 13, there is a primitive root g modulo p such that g + g^{-1} is also a primitive root modulo p, where g^{-1} is the inverse of g modulo p.
Note that a(n) is even for any n > 1. In fact, if g is a primitive root modulo a prime p > 3, then the inverse of g mod p is different from g since g^2 cannot be congruent to 1 modulo p.
Conjecture: Let F be a finite field with |F| = q > 13. Then there is a primitive root g of F (i.e., a generator of the cyclic group F\{0}) such that g + g^{-1} is also a primitive root of F.  If q > 61, then there exists a primitive root g of F such that g - g^{-1} is also a primitive root of F.
The author has proved this for any finite field F with |F| > 2^{66}.

			a(5) = 2 since 2 and 6 are primitive roots modulo prime(5) = 11 with 2*6 == 1 (mod 11) and 2 + 6 = 8 also a primitive root modulo 11.
This example recalls that there is no symmetry g -> -g (in Z/pZ) (nor a symmetry w.r.t. odd/even g), therefore one cannot (unfortunately) compute a(n) by taking twice the count of the g<prime(n)/2 which satisfy the condition. E.g., for p=19=prime(8), only g = 14 (= -5) and g = 15 (= -4) are in the set. - _M. F. Hasler_, Oct 06 2013

M. F. Hasler, Table of n, a(n) for n = 1..1000

Cf. A001918, A229899.

Cf. A010554.

gp[g_,p_]:=gp[g,p]=Mod[g,p]>0&&Length[Union[Table[Mod[g^k, p],{k,1,p-1}]]]==p-1
a[n_]:=Sum[If[gp[g,Prime[n]]&&gp[g+PowerMod[g,-1,Prime[n]],Prime[n]],1,0],{g,1,Prime[n]-1}]
Table[a[n],{n,1,80}]

A229910(n)=my(p=prime(n));sum(g=2,p-2,znorder(Mod(g,p))==p-1 & Mod(g,p)^-1+g & znorder(Mod(g,p)^-1+g)==p-1) \\ M. F. Hasler, Oct 06 2013

A229910(n)={my(p=prime(n),u=0,s=0,i); n=p-1; for(g=2,p-2, bittest(u,g)&next; znorder(Mod(g,p))M. F. Hasler, Oct 06 2013

use ntheory ":all"; sub a229910 { my $p=nth_prime(shift); scalar(grep {is_primitive_root($,$p) && is_primitive_root($+invmod($,$p),$p)} 2..$p-2); } # _Dana Jacobsen, Sep 19 2016

Values a(1..400) double checked and extended to n=1000 by M. F. Hasler, Oct 06 2013

cp's OEIS Frontend

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

A386261 a(n) = A001511(A001511(n)), where A001511 is the ruler function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A386262 a(n) = A051903(A051903(n)) for n >= 2, a(1) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A063999 Numbers k such that the number of primes <= k is phi(phi(k)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Extensions

A111409 a(n) = f(f(n+1)) - f(f(n)), where f(0)=0, and for m>0, f(m) = phi(m) = A000010(m).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A163373 a(n) = phi(phi(sigma(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A173337 Numbers k>1 such that phi(phi(k)) = sigma(sopf(k)).

Views

Author