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