pi and phi

[David W. Wilson]

Jeffrey Shallit wrote:

> > > You can find good upper and lower bounds for arithmetic functions
> > > in my book with Eric Bach, _Algorithmic Number Theory_, Chapter 8.
> > > In particular you can find the following bound of Rosser and
> > > Schoenfeld,
> > >         phi(n) > n/(e^gamma log log n + 3/(log log n)) for n >= 3.
> > >
> > > Jeffrey Shallit
> >
> > Does this lower bound for phi(n) necessitate phi(n) > pi(n) ~ n/log(n)
> > for sufficient n?
>
> Yes.   In fact, using another bound in my book, you can show
> that phi(n) > pi(n) for n >= 11155.
>
> I guess the rest is just a simple brute force search.
>
> Jeff

And the result of the brute force search is:

A037171 is finite and complete as it now stands.

Also:

pi(n) >= phi(n): 2 3 4 6 8 10 12 14 18 20 24 30 42 60 90
pi(n) > phi(n): 6 12 18 24 30 42 60