

A057635


a(n) is the largest m such that phi(m) = n, where phi is Euler's totient function = A000010.


12



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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. Namely, 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(gamma1)*log(n) < 4*exp(gamma2)*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
Rosser, J. Barkley; Schoenfeld, Lowell (1962). Approximate formulas for some functions of prime numbers. Illinois J. Math. 6 (1): 6494.


FORMULA

a(2n+1) = 0 for n > 0 and when a(2n) = 0, the nontotients (A005277)/2.


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


CROSSREFS

Cf. A000010, A014197.
Sequence in context: A065344 A131105 A321713 * A269943 A243015 A139717
Adjacent sequences: A057632 A057633 A057634 * A057636 A057637 A057638


KEYWORD

nonn


AUTHOR

Jud McCranie, Oct 10 2000


STATUS

approved



