login
Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.
7

%I #22 Nov 14 2024 05:56:57

%S 2,2,6,6,12,6,18,12,18,12,22,12,42,18,30,30,60,18,54,30,42,22,46,30,

%T 66,42,54,42,58,30,62,60,66,60,90,42,126,54,90,60,150,42,98,66,90,46,

%U 94,60,98,66,120,90,106,54,150,90,126,58,118,60,198,62,126,120,210,66,134

%N Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.

%C Every number in this sequence occurs at least twice. For all n > 6, a(n) > phi(n)^2 is impossible. - _Alonso del Arte_, Dec 31 2016

%H Antti Karttunen, <a href="/A028476/b028476.txt">Table of n, a(n) for n = 1..10000</a> (computed from the b-file of A057826 provided by T. D. Noe)

%H Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).

%F a(1) = a(2) = 2, for n > 2, a(n) = A057826(A000010(n)/2). - _Antti Karttunen_, Aug 07 2017

%e phi(1) = 1 and phi(2) = 1 also. There is no greater k such that phi(k) = 1, so therefore a(1) = a(2) = 2.

%e phi(3) = phi(4) = phi(6) = 2, and there is no greater k such that phi(k) = 6, hence a(3) = a(4) = a(6) = 6.

%t Table[Module[{k = (2 Boole[n <= 6]) + #^2}, While[EulerPhi@ k != #, k--]; k] &@ EulerPhi@ n, {n, 120}] (* _Michael De Vlieger_, Dec 31 2016 *)

%o (PARI) a(n) = invphiMax(eulerphi(n)); \\ _Amiram Eldar_, Nov 14 2024, using _Max Alekseyev_'s invphi.gp

%Y Cf. A000010, A015126, A057826, A066412, A066659, A071181.

%K nonn,changed

%O 1,1

%A _Vladeta Jovovic_, Jan 12 2002