Re: How hard is this to prove?

quasi wrote:
> On Sat, 01 Oct 2005 23:38:23 -0700, quasi <quasi@xxxxxxxx> wrote:
>
> >On 1 Oct 2005 20:17:13 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
> >wrote:
> >
> >>
> >>Joubin Houshyar wrote:
> >>> quasi wrote:
> >>> > On 1 Oct 2005 19:48:37 -0700, "Joubin Houshyar" <Sun_of_27@xxxxxxxxx>
> >>> > wrote:
> >>> >
> >>> > >I am considering the following conjecture:
> >>> > >
> >>> > >(i) pi(n) > phi(n) / 2
> >>> > >
> >>> > >I have a few questions and would greatly appreciate feedback.
> >>> > >
> >>> > >1) Is this known? If it is, then great! (Could you please provide
> >>> > >reference(s)?)
> >>> >
> >>> > It's not known.
> >>> >
> >>> > >2) If not known, how hard (do you think) it would be to prove?
> >>> >
> >>> > Very hard, since it's also not true.
> >>>
> >>> Right you are. A typo:
> >>>
> >>> Revised conjecture:
> >>>
> >>> (i) pi(n!) > phi(n) / 2
> >>>
> >>> For all n > 4, where n is an even number.
> >>
> >>(Actually, scratch that -- Simply for all n > 4)
> >>
> >>(i) pi(n!) > phi(n) / 2 (where n > 4)
> >>
> >>>
> >>> Could you please reconsider the questions?
> >>>
> >>> /R
> >>>
> >>> Joubin Houshyar
> >
> >Well, now your inequality is obviously true, but much too weak, since
> >(bypassing small values if n):
> >
> >pi(n!)>n!/ln(n!)>n!/ln(n^n)=(n-1)!/ln(n)>(n-2)!>n/2>phi(n)/2
> >
> >quasi
>
> In other words, phi(n)/2 is tiny compared with pi(n!).


[I appreciate your help here. (Amateur hour, so please bear with me.)]

Well, actually you threw me off with your first reply. The original
was correct, but it clearly doesn't apply to all n.

Basically, I thought that it should hold -- rather I wanted it to hold
<g> -- for n = 2 * k, where k is not prime.

Then we consider pi(n) > phi(n)/2.

I plugged a few numbers in the calculator (haven't programmed it yet.)

1)
n = 210
phi(n) = 48
pi(n) = 36 > 48/2

2)
n = 120
phi(n) = 32
pi(n) = 30 > 32/2

3)
n = 110
phi(n) = 40
pi(n) = 30 > 40/2

4)
n = 108
phi(n) = 36
....

5)
n = 720
phi(n) = 48
pi(n) = 128 > 48/2

5)
n = 2310
phi(n) = 480
pi(n) = 343 > 480 / 2

It definitely seems to hold better for multi-factor (distinct) n's.
(Ex. primorials and factorials. In fact, it may actually hold for
these -- I'll have to write a program to check it.)

But cases where n = 2^2 * p definitely seem to break it fairly
consistently starting with p=31 and it gets worst when p get larger
(which I guess is obvious once one sees it).

6)
n = 4 * 31 = 124
phi(n) = 60
pi(n) = 30 // broke

7)
n = 2308
phi(n) = 1154 (!)
pi(n) = 343

.... and there goes the conjecture ...

I erronuously thought that phi(n) behaved in a relatively smooth/linear
fashion, but clearly its all over the place! (cf Phi(2308)=1154 and
phi(2310)=480).

So apparently its not that phi(n) is huge in general, but that it can
jump to fairly huge numbers.

Anyway, thanks for your help and time.

/R

.

Quantcast