Max value of x/phi(x)

[Alonso Del Arte]

Thanks, Jud, that answers my question. The formula x/phi(x) <=
sqrt(2x) must be right. I tried giving Mathematica the command
Select[Range[1000000], (#/EulerPhi[#]) > (Sqrt[2*#]) &], and after
five minutes it returned and empty set {}.

And thanks to Hugo for stating the formulas phi(x) = x prod{ 1 - 1/p_i
}, prod{ 1 - 1/p_i }. That confirms my thought that the lower bound is
x+1.

Alonso
 
> 
> 
> On Mon, 30 Aug 2004 17:32:43 -0400, Jud McCranie
> <j.mccranie at adelphia.net> wrote:
> >
> >
> > At 04:59 PM 8/30/2004, Alonso Del Arte wrote:
> > >Does anyone know what the maximum possible value of x/phi(x) can be
> > >(where phi is Euler's totient function)? Is there a theorem in regards
> > >to this?
> > >
> > > From some playing around with Mathematica it seems to me that the
> > >value can be made as large as one wants by choosing a sufficiently
> > >large highly composite number, but I'm wondering if x/phi(x) is
> > >bounded by some property of x, such as its square root.
> >
> > There is a minimum for that ratio.  There is another theorem that says that
> > x/phi(x) <= sqrt( 2x), so the ratio must be unbounded.
> >
> > There are several sequences dealing with "highly composite" - enter that
> > phrase.
> >
> > Ref: Bach and Shallit, Algorithmic Number Theory, vol 1, theorem 8.8.7 for
> > the minimum.  I wrote the other in the margin, but I don't know a reference.
> >
> >
>