A138537 -id:A138537 - cp's OEIS frontend

A058340 Primes p such that phi(x) = p-1 has only 2 solutions, namely x = p and x = 2p.

11, 23, 29, 31, 47, 53, 59, 67, 71, 79, 83, 103, 107, 127, 131, 137, 139, 149, 151, 167, 173, 179, 191, 197, 199, 211, 223, 227, 229, 239, 251, 263, 269, 271, 283, 293, 307, 311, 317, 331, 347, 359, 367, 373, 379, 383, 389, 419, 431, 439, 443, 463, 467, 479

Offset: 1

Labos Elemer, Dec 14 2000

nonn

Two solutions, p and 2p, exist for all odd primes p; primes in sequence have no other solutions.
Conjecture: if q > 7 is in A005385, then q is in the sequence. - Thomas Ordowski, Jan 04 2017
Proof of conjecture: q'=(q-1)/2 is an odd prime > 3.  If phi(x)=2q', which has 2-adic order 1 but is not a power of 2, there must be exactly one odd prime r dividing x.  We could also have a factor of 2 (but no higher power, which would contribute more 2's to phi(x)).  If x = r^e or 2r^e, then phi(x) = (r-1) r^(e-1).  For this to be 2q' one possibility is r-1 = 2 and r^(e-1)=q', but then q'=r=3, ruled out by q > 7.  The only other possibility is r-1=2q' and e=1, which makes r=q and x=q or 2q. - Robert Israel, Jan 04 2017
Information from Carl Pomerance: It is known that almost all primes (in the sense of relative asymptotic density) are in the sequence. - Thomas Ordowski, Jan 08 2017

			For p=2, phi(x)=1 has only two solutions, but they are 1 and 2, not 2 and 4, so 2 is not in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A005385, A006093, A058339, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080, A138537.

filter:= n -> isprime(n) and nops(numtheory:-invphi(n-1))=2:
select(filter, [seq(i,i=3..10000,2)]); # Robert Israel, Aug 12 2016

Take[Rest@ Keys@ Select[KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], Length@ # == 2 &], 54] (* Michael De Vlieger, Dec 29 2017 *)

a(n) ~ n log . - Charles R Greathouse IV, Nov 18 2022

Edited by Ray Chandler, Jun 06 2008

A138786 "Left" odd composite numbers n for which n < A140607((n-1)/2).

Original entry on oeis.org

9, 21, 25, 27, 35, 45, 49, 55, 69, 75, 77, 81, 93, 95, 99, 105, 115, 119, 121, 125, 133, 135, 141, 143, 147, 153, 155, 161, 165, 169, 175, 187, 189, 203, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 253, 259, 261, 267, 279, 285, 287

Offset: 1

Vladimir Shevelev, May 18 2008

nonn

There are odd composite numbers which are neither in this sequence nor in A140608. The first such number is 91, see A140667.

Ray Chandler, Table of n, a(n) for n=1..5713

Cf. A140607, A039649, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A000010, A000040, A140608, A140667.

Extended by Ray Chandler, May 20 2008

A140607 (A039649(2n+1)+A137576(n))/2.

Original entry on oeis.org

3, 5, 7, 10, 11, 13, 13, 17, 19, 22, 23, 31, 37, 29, 31, 31, 43, 37, 37, 41, 43, 55, 47, 64, 45, 53, 61, 55, 59, 61, 55, 61, 67, 78, 71, 73, 91, 106, 79, 136, 83, 77, 85, 89, 91, 96, 109, 97, 136, 101, 103, 109, 107, 109, 109, 113, 155, 103, 145, 166, 111, 201, 127, 113

Offset: 1

Vladimir Shevelev, May 18 2008

nonn

If 2n+1 is a prime then a(n) = 2n+1.

Ray Chandler, Table of n, a(n) for n=1..10000

Cf. A039649, A137576, A000010, A000040, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A140608, A138786, A140667.

Extended by Ray Chandler, May 20 2008, May 24 2008

A140608 "Right" odd composite numbers n for which n > A140607((n-1)/2).

Original entry on oeis.org

15, 33, 39, 51, 57, 63, 65, 85, 87, 111, 117, 123, 129, 145, 159, 171, 177, 183, 185, 195, 201, 205, 249, 255, 265, 273, 275, 291, 303, 305, 315, 321, 327, 333, 339, 341, 393, 399, 411, 417, 435, 447, 451, 455, 465, 471, 481, 485, 489, 505, 511, 513, 519, 537

Offset: 1

Vladimir Shevelev, May 18 2008

nonn

Conjecture. The sequence is infinite.

Ray Chandler, Table of n, a(n) for n=1..2022

Cf. A140607, A039649, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A000010, A000040, A138786, A140667.

Extended by Ray Chandler, May 20 2008

A140667 Odd composite numbers k for which k = A140607((k-1)/2).

Original entry on oeis.org

91, 1581, 2465, 8481, 25761, 31609, 33355, 34945, 118405, 146611, 319507, 736291, 994507, 3270403, 3375487, 5176153, 6186403, 6228685, 8650951, 10679131, 22028203, 26017291, 31470211, 33796531, 41710411, 42149971, 42474547, 46672291, 48316969, 49019851, 58986091, 68182003, 69885649

Offset: 1

Ray Chandler, May 20 2008

nonn

Cf. A140607, A039649, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A000010, A000040, A140608, A138786.

f(n) = (eulerphi(2*n+1) + 1 + g(n))/2; \\ A140607
g(n) = sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isok(c) = if (!isprime(c) && (c%2), f((c-1)/2) == c); \\ Michel Marcus, Jan 31 2023

More terms from Michel Marcus, Jan 31 2023

A074987 a(n) is the least m not equal to n such that phi(m) = phi(n).

Original entry on oeis.org

2, 1, 4, 3, 8, 3, 9, 5, 7, 5, 22, 5, 21, 7, 16, 15, 32, 7, 27, 15, 13, 11, 46, 15, 33, 13, 19, 13, 58, 15, 62, 17, 25, 17, 39, 13, 57, 19, 35, 17, 55, 13, 49, 25, 35, 23, 94, 17, 43, 25, 64, 35, 106, 19, 41, 35, 37, 29, 118, 17, 77, 31, 37, 51, 104, 25, 134, 51, 92, 35, 142

Offset: 1

Joseph L. Pe, Oct 02 2002

In 1922, Carmichael asked if for any given natural number n there exists a natural number m different from n such that phi(m) = phi(n). A. Schlafly and S. Wagon showed in 1994 that if there is an n such that phi(m) != phi(n) for all m distinct from n, then n must be greater than 10^(10^7). [Improved to 10^(10^10) by Kevin Ford. - Pontus von Brömssen, May 15 2020]
I conjecture that a(n) <= 2n. I have checked this for all n <= 10^4. (It is not possible to do better than the 2n upper bound since a(11) = 2*11.)
For odd n the conjecture is true because phi(n)=phi(2n). - T. D. Noe, Oct 18 2006
From Robert Israel, Aug 12 2016: (Start)
If a(n) > n then a(a(n)) = n.
If n is in A138537 then a(n) = 2*n. (End)
From David A. Corneth, May 12 2018: (Start)
A210719 has values n such that a(n) > n, so a(A210719(n)) = n.
Its complement, A296214, has values n such that a(n) < n. (End)

			phi(5) = 4 and 8 is the least natural number k different from 5 such phi(k) = 4. Hence phi(5) = 8.

J. Tattersall, "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, pp. 162-163.

T. D. Noe, Table of n, a(n) for n = 1..10000
K. Ford, The distribution of totients, arXiv:1104.3264 [math.NT], 2011.
A. Schlafly and S. Wagon, Carmichael's conjecture on the Euler function is valid below 10^{10,000,000}, Mathematics of Computation, 63 No. 207(1994), 415-419.
Wikipedia, Carmichael's_totient_function_conjecture

Cf. A138537, A210719, A296214.

N:= 1000: # to get a(n) for n <= N
todo:= N;
for n from 1 while todo > 0 do
  v:= numtheory:-phi(n);
  if assigned(R[v]) then
    if n <= N then
      A[n]:= R[v]; todo:= todo-1;
    fi;
    if R[v] <= N and not assigned(A[R[v]])  then
      A[R[v]]:= n; todo:= todo-1;
    fi;
  else
    R[v]:= n
  fi
od:
seq(A[n],n=1..N); # Robert Israel, Aug 12 2016

l = {}; Do[ e = EulerPhi[n]; i = 1; While[e != EulerPhi[i] || n == i, i++ ]; l = Append[l, i], {n, 1, 100}]; l
(* Second program: *)
Module[{nn=300,lst},lst=Table[{n,EulerPhi[n]},{n,nn}];Take[Table[ SelectFirst[ lst,#[[2]] == lst[[k,2]] && #[[1]]!=lst[[k,1]]&],{k,nn}],100]][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Oct 23 2020 *)

a(n) = my(t=eulerphi(n), m=1); while ((eulerphi(m) != t) || (m==n), m++); m; \\ Michel Marcus, May 15 2020

from sympy import totient
def A074987(n):
  m=1
  while totient(m)!=totient(n) or m==n:
    m+=1
  return m # Pontus von Brömssen, May 15 2020

cp's OEIS Frontend

A058340 Primes p such that phi(x) = p-1 has only 2 solutions, namely x = p and x = 2p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A138786 "Left" odd composite numbers n for which n < A140607((n-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A140607 (A039649(2n+1)+A137576(n))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A140608 "Right" odd composite numbers n for which n > A140607((n-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A140667 Odd composite numbers k for which k = A140607((k-1)/2).

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions

A074987 a(n) is the least m not equal to n such that phi(m) = phi(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python