cp's OEIS Frontend

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

%I A074987 #55 Jul 11 2023 14:42:20
%S A074987 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,
%T A074987 13,58,15,62,17,25,17,39,13,57,19,35,17,55,13,49,25,35,23,94,17,43,25,
%U A074987 64,35,106,19,41,35,37,29,118,17,77,31,37,51,104,25,134,51,92,35,142
%N A074987 a(n) is the least m not equal to n such that phi(m) = phi(n).
%C A074987 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]
%C A074987 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.)
%C A074987 For odd n the conjecture is true because phi(n)=phi(2n). - _T. D. Noe_, Oct 18 2006
%C A074987 From _Robert Israel_, Aug 12 2016: (Start)
%C A074987 If a(n) > n then a(a(n)) = n.
%C A074987 If n is in A138537 then a(n) = 2*n. (End)
%C A074987 From _David A. Corneth_, May 12 2018: (Start)
%C A074987 A210719 has values n such that a(n) > n, so a(A210719(n)) = n.
%C A074987 Its complement, A296214, has values n such that a(n) < n. (End)
%D A074987 J. Tattersall, "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, pp. 162-163.
%H A074987 T. D. Noe, <a href="/A074987/b074987.txt">Table of n, a(n) for n = 1..10000</a>
%H A074987 K. Ford, <a href="http://arxiv.org/abs/1104.3264">The distribution of totients</a>, arXiv:1104.3264 [math.NT], 2011.
%H A074987 A. Schlafly and S. Wagon, <a href="https://doi.org/10.1090/S0025-5718-1994-1226815-3">Carmichael's conjecture on the Euler function is valid below 10^{10,000,000}</a>, Mathematics of Computation, 63 No. 207(1994), 415-419.
%H A074987 Wikipedia, <a href="https://en.wikipedia.org/wiki/Carmichael&#39;s_totient_function_conjecture">Carmichael's_totient_function_conjecture</a>
%e A074987 phi(5) = 4 and 8 is the least natural number k different from 5 such phi(k) = 4. Hence phi(5) = 8.
%p A074987 N:= 1000: # to get a(n) for n <= N
%p A074987 todo:= N;
%p A074987 for n from 1 while todo > 0 do
%p A074987   v:= numtheory:-phi(n);
%p A074987   if assigned(R[v]) then
%p A074987     if n <= N then
%p A074987       A[n]:= R[v]; todo:= todo-1;
%p A074987     fi;
%p A074987     if R[v] <= N and not assigned(A[R[v]])  then
%p A074987       A[R[v]]:= n; todo:= todo-1;
%p A074987     fi;
%p A074987   else
%p A074987     R[v]:= n
%p A074987   fi
%p A074987 od:
%p A074987 seq(A[n],n=1..N); # _Robert Israel_, Aug 12 2016
%t A074987 l = {}; Do[ e = EulerPhi[n]; i = 1; While[e != EulerPhi[i] || n == i, i++ ]; l = Append[l, i], {n, 1, 100}]; l
%t A074987 (* Second program: *)
%t A074987 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 *)
%o A074987 (Python)
%o A074987 from sympy import totient
%o A074987 def A074987(n):
%o A074987   m=1
%o A074987   while totient(m)!=totient(n) or m==n:
%o A074987     m+=1
%o A074987   return m # _Pontus von Brömssen_, May 15 2020
%o A074987 (PARI) a(n) = my(t=eulerphi(n), m=1); while ((eulerphi(m) != t) || (m==n), m++); m; \\ _Michel Marcus_, May 15 2020
%Y A074987 Cf. A138537, A210719, A296214.
%K A074987 easy,nice,nonn
%O A074987 1,1
%A A074987 _Joseph L. Pe_, Oct 02 2002