login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A074987 a(n) is the least m not equal to n such that phi(m) = phi(n). 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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)

REFERENCES

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

LINKS

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

l = {}; Do[ e = EulerPhi[n]; i = 1; While[e != EulerPhi[i] || n == i, i++ ]; l = Append[l, i], {n, 1, 100}]; l

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 *)

PROG

(Python)

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

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

CROSSREFS

Cf. A138537, A210719, A296214.

Sequence in context: A087207 A179206 A331740 * A294096 A128280 A182177

Adjacent sequences:  A074984 A074985 A074986 * A074988 A074989 A074990

KEYWORD

easy,nice,nonn

AUTHOR

Joseph L. Pe, Oct 02 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 06:14 EDT 2021. Contains 348040 sequences. (Running on oeis4.)