Prev: testing; Google down but Drexel Math Forum up
Next: unipotent radical of parabolic subgroup
From: curious george on 15 Jul 2010 16:39
anyone knows a better approximation to ph(n) for composite integers that is
better than
ph(n) < or = to (n-n^1/2)

thanks



From: hagman on 15 Jul 2010 17:29
On 15 Jul., 22:39, "curious george" <bu...(a)bunch.net> wrote:
> anyone knows a better approximation to ph(n) for composite integers that is
> better than
> ph(n) < or = to (n-n^1/2)
>
> thanks

If we rule out n = p, n = p^2, n = 1, n = 8, n = 27
then we have
ph(n) < n - 2 sqrt(n) + 1.
However for n=p^2, we have
ph(n) = p^2 - p = n - sqrt(n).

(Let n be composite.
If n is a prime power, n = p^k, then ph(n) = n - p^(k-1)
so the inequality cannot be improved when n is the square of a prime.
If n is a higher prime power then ph(n) = n - p^(k-1) = n - p^(k/
2-1)*sqrt(n)
<= n - 2 sqrt(n) if p>3 or k>3
If n is not a prime power, say n = a*b with nontrivial coprime factors
a < b
then ph(n) = ph(a)*ph(b) <= (a-1)(b-1) = n - a - b + 1.
Let c = a/sqrt(n).
Then ph(n) <= n - (c+1/c)*sqrt(n) + 1 < n - 2 sqrt(n) + 1.)
From: Pubkeybreaker on 15 Jul 2010 18:13
On Jul 15, 5:29 pm, hagman <goo...(a)von-eitzen.de> wrote:
> On 15 Jul., 22:39, "curious george" <bu...(a)bunch.net> wrote:
>
> > anyone knows a better approximation to ph(n) for composite integers that is
> > better than
> > ph(n) < or = to (n-n^1/2)
>
> > thanks
>
> If we rule out n = p, n = p^2, n = 1, n = 8, n = 27
> then we have
>    ph(n) < n - 2 sqrt(n) + 1.
> However for n=p^2, we have
>    ph(n) = p^2 - p = n - sqrt(n).
>
> (Let n be composite.
> If n is a prime power, n = p^k, then ph(n) = n - p^(k-1)
> so the inequality cannot be improved when n is the square of a prime.
> If n is a higher prime power then ph(n) = n - p^(k-1) = n - p^(k/
> 2-1)*sqrt(n)
> <= n - 2 sqrt(n) if p>3 or k>3
> If n is not a prime power, say n = a*b with nontrivial coprime factors
> a < b
> then ph(n) = ph(a)*ph(b) <= (a-1)(b-1) = n - a - b + 1.
> Let c = a/sqrt(n).
> Then ph(n) <= n - (c+1/c)*sqrt(n) + 1 <  n - 2 sqrt(n) + 1.)

Use the normal order. See Hardy & Wright.
 | 
Pages: 1
Prev: testing; Google down but Drexel Math Forum up
Next: unipotent radical of parabolic subgroup