OFFSET
1,1
COMMENTS
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
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.
From Jianing Song, Feb 16 2019: (Start)
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.
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)).
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).
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).
Conjecturally a(n) < n*f(n) for all n > 2. (End)
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1) (1962), 64-94.
FORMULA
a(2n+1) = 0 for n > 0, and a(2n) = 0 iff 2n is in A005277.
EXAMPLE
m = 12 is the largest value of m such that phi(m) = 4, so a(4) = 12.
MATHEMATICA
a = Table[0, {100}]; Do[ t = EulerPhi[n]; If[t < 101, a[[t]] = n], {n, 1, 10^6}]; a
PROG
(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
(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
(PARI) a(n) = invphiMax(n); \\ Amiram Eldar, Nov 14 2024 using Max Alekseyev's invphi.gp
CROSSREFS
KEYWORD
nonn
AUTHOR
Jud McCranie, Oct 10 2000
EXTENSIONS
Edited and escape clause added to definition by M. F. Hasler, Aug 13 2021
STATUS
approved