login
a(n) is the largest m such that phi(m) = n, where phi is Euler's totient function = A000010, or a(n) = 0 if no such m exists.
24

%I #38 Jul 27 2024 22:08:13

%S 2,6,0,12,0,18,0,30,0,22,0,42,0,0,0,60,0,54,0,66,0,46,0,90,0,0,0,58,0,

%T 62,0,120,0,0,0,126,0,0,0,150,0,98,0,138,0,94,0,210,0,0,0,106,0,162,0,

%U 174,0,118,0,198,0,0,0,240,0,134,0,0,0,142,0,270,0,0,0,0,0,158,0,330,0

%N a(n) is the largest m such that phi(m) = n, where phi is Euler's totient function = A000010, or a(n) = 0 if no such m exists.

%C To check that a property P holds for all EulerPhi(x) not exceeding n, for n with a(n) > 0, it suffices to check P for all EulerPhi(x) with x not exceeding a(n). - _Joseph L. Pe_, Jan 10 2002

%C The Alekseyev link in A131883 establishes the following explicit relationship between A131883, A036912 and A057635: for t belonging to A036912, we have t = A131883(A057635(t)-1). In other words, A036912(n) = A131883(A057635(A036912(n))-1) for all n.

%C From _Jianing Song_, Feb 16 2019: (Start)

%C Let f(n) = exp(gamma)*log(log(n)) + 2.5/log(log(n)), then a(n) < n*f(n^2) for all n > 1, where gamma = A001620.

%C Proof. Without loss of generality we suppose log(log(n)) > n_0 = sqrt(2.5/exp(gamma)) = 1.18475..., then f(n), n/f(n) and N(n) = ceiling(n*f(n^2)) are all monotonically increasing functions of n, and we have f(n) < 2*exp(gamma)*log(log(n)).

%C By the formula (3.41) in Theorem 15 by J. Barkley Rosser and Lowell Schoenfeld we have phi(k) > k/f(k) for k != 1, 2, 223092870. N(31802157) = 223092869 < 223092870, N(31802158) = 223092877 > 223092870, so N(n) != 223092870 (N(n) is increasing). So phi(N(n)) > N(n)/f(N(n)) > (n*f(n^2))/f(n*f(n^2)) (n/f(n) is increasing and log(log(n*f(n^2))) > n_0).

%C Note that f(n^2) < 2*exp(gamma)*log(log(n^2)) < 2*exp(gamma)*(log(n^2)/e) = 4*exp(gamma-1)*log(n) < 4*exp(gamma-2)*n < n, so n*f(n^2) < n^2, f(n*f(n^2)) < f(n^2) (f(n) is increasing and log(log(n*f(n^2))) > n_0), so phi(N(n)) > n. As a result, a(n) <= N(n) - 1 < n*f(n^2).

%C Conjecturally a(n) < n*f(n) for all n > 2. (End)

%H T. D. Noe, <a href="/A057635/b057635.txt">Table of n, a(n) for n = 1..10000</a>

%H Rosser, J. Barkley; Schoenfeld, Lowell (1962). <a href="https://projecteuclid.org/euclid.ijm/1255631807">Approximate formulas for some functions of prime numbers</a>. Illinois J. Math. 6 (1): 64-94.

%F a(2n+1) = 0 for n > 0, and a(2n) = 0 iff 2n is in A005277.

%e m = 12 is the largest value of m such that phi(m) = 4, so a(4) = 12.

%t a = Table[0, {100}]; Do[ t = EulerPhi[n]; If[t < 101, a[[t]] = n], {n, 1, 10^6}]; a

%o (PARI) a(n) = if(n%2, 2*(n==1), forstep(k=floor(exp(Euler)*n*log(log(n^2))+2.5*n/log(log(n^2))), n, -1, if(eulerphi(k)==n, return(k)); if(k==n, return(0)))) \\ _Jianing Song_, Feb 15 2019

%o (PARI) apply( {A057635(n,m=istotient(n))=if(!m, 0, n>1, m=log(log(n)*2); m=bitand(n*(exp(Euler)*m+2.5/m)\1,-2); while(eulerphi(m)!=n, m-=2); m, 2)}, [1..99]) \\ If n is known to be a totient, a nonzero 2nd arg can be given to avoid the check. - _M. F. Hasler_, Aug 13 2021

%Y Cf. A000010, A014197, A049283.

%Y Cf. A006511 (largest k for which A000010(k) = A002202(n)).

%K nonn

%O 1,1

%A _Jud McCranie_, Oct 10 2000

%E Edited and escape clause added to definition by _M. F. Hasler_, Aug 13 2021