Problems & Puzzles:
Puzzles
Puzzle 211. A
beauty limit on prime numbers
As a part of a more general research
on certain type of limits,
Sebastián Martín Ruiz(1)
discovered the following beauty limit involving only prime numbers:
lim
n->∞
[pn/AS(pn)]
= 2
Q1:
Demonstrate the above limit.
I have indicated to SMR that the limit
he has gotten, can be used in order to obtain the following approximate
relation:
pn
≈ 2.AS(pn-1)
Q2: As a tool for
estimating a prime pn using the
'alternate
sum'
for all the primes
less than it, how good and efficient is this approximate formula
(2)?
_______
(1) Other results by S. Martin R. in his own
Web page
(2) For
computing purposes maybe you'll find useful that
AS(pn)
= pn - AS(pn-1)
Solution:
Bruce Fleming and
Joseph L. Pe sent the following contributions
to this puzzle:
Bruce Fleming
sent the following "outline proof":
The comparison with the Q-sequence
is a linear relation, Q(n) ~ n/2 and (AS(p_n)/p_n)n ~ n/2, that exhibits
some chaotic behavior and may therefore repay further attention.
Having thought further about the
question, I now realize that (AS(p_n)/p_n) is convergent, by the
alternating test, and that it converges to 1/2. The outline argument is
as follows.
Let s(m) = f(0) - f(1) + f(2) - ...
+ ((-1)^m)f(m), where f(k) = p_(n-k)/p_n and p_n denotes the n-th
prime. Then we can take the difference of partial sums as follows.
s(2k+1) - s(2k-1) = f(2k) - f(2k+1)
= (p_(n-2k) - p_(n-2k-1))/p_n > 0 (increasing)
s(2k) - s(2k-2) = f(2k) - f(2k-1) =
(p_(n-2k) - p_(n-2k+1))/p_n < 0 (decreasing)
So the first sequence is increasing
and tends to a limit or goes to infinity. Similarly, the second
sequence is decreasing and tends to a limit or goes to minus infinity.
But as n -> infinity and k -> n, we
have
lim(s(2k+1) - s(2k)) = lim
((-1)^(2k+1)) f(2k+1) = 0.
So both sequences converge to a
limit and the limits must be the same.
Reverting to the original notation,
AS(p_n)/p_n is therefore convergent. But how to show that the limit is
1/2?
Let us denote the n-th prime gap by
g(n) = p_n - p_(n-1). Then we can write AS(p_2n) as:
AS(p_2n) = g(2n)/p_2n + g(2n-2)/p_n
+ ... g(2)/p_n = sigma(k=1:n) g(2k)/p_2n.
Now clearly p_2n = sigma(k=1:n)
g(2k) + sigma(k=1:n) g(2k-1),
where, for convention, we put g(1)
= 2.
So we can see that unless there is
any bias in size between "odd" and "even" prime gaps, Martin Ruiz's
result should follow. Certainly no such bias is known.
Using an averaging argument which
is a corollary of the Prime Number Theorem, the order of the 2n-th prime
gap is about log(2n). Therefore the sum of the "even" prime gaps will
be of the same order as the integral
Int(1:n) log (2t) dt = n log(2n) -
n - c (a small constant).
If we assume p_2n ~ (2n) log(2n),
then the ratio of the sum of the first n "even" prime gaps to the 2n-th
prime approaches 1/2 as n -> oo. Therefore (p_n/AS(p_n)) -> 2.
Fleming also noted this:
My first impression is that there may be an analogy
between the plot of {(AS(p_n))/p_n}n against n and Hofstadter's Q-sequence
( http://mathworld.wolfram.com/HofstadtersQ-Sequence.html).
The following comparisons appear:
1 Both sequences are defined by a two term
recurrence relation;
2 The average orders of Q(n) and {(AS(p_n))/p_n}n
are both n/2;
3 Both sequences contain "well-behaved" points, that
is points that lie on the line f(n)=n/2 in the case of Q(n) and points
such that 2AS(p_n) = p_n +/- 1 in the case of the AS ratio function.)
4 The sequences exhibit self-similarity (?).
The main difference seems to be that Q(n) exhibits
periodic behavior. The AS ratio function does not appear to do so.
A question for the programmers is: What is the bound
on the error term in the case of (i) Q(n) and (ii) {(AS(p_n))/p_n}n? Which
of the two sequences is the more "chaotic" in terms of its deviation from
the linear relation?
In effect, we are seeking the remainder term g(n)
such that
2AS(p_n) = p_n + O(g(n)).
I do not know what techniques would enable this to
be determined but would be interested to see what the computer evidence
suggests.
He also noticed that:
The Ruiz theorem also works
for alternate sums of prime powers. For example, if we take
AS((p_n)^2) = (p_n)^2 - (p_n-1)^2 +
(p_n-2)^2 - ... + (-1)^(n+1).2^2
then lim ((p_n)^2)/AS((p_n)^2) -> 2
as n -> oo
The limit ((p_n)^k)/AS((p_n)^k) ->
2 holds generally for positive integers k and I suspect also for all
positive real k (though a rigorous proof is more difficult for reals).
***
Another interesting point of view came
from Joseph L. Pe who made a graph of pn/AS(pn) for n=1 to 5000 and
observes in such a graph "some fractal structure (although perhaps is not a
full-fledged fractal) in the sense that some regions of the graph are or
look like scaled-down copies of other regions. That is, there is some
self-similarity in the graph.".
... Now Hans Havermann
has completed his
graph up to n = 10^6 ( http://odo.ca/~haha/j/num/osc.jpg),
and it looks like the sequence now converges!
***
Joseph L. Pe made the following
criticism to the Fleming's proof:
(Notes in brackets [,] are mine. Notes preceded by ">" are
from the original proofs.)
>Let s(m) = f(0) - f(1) + f(2) - ... +
((-1)^m)f(m), where f(k) = p_(n-k)/p_n and p_n denotes the n-th prime.
[Fine. Fleming wants to show that the sequence AS(p(n))/p(n) converges by
showing that the partial sums s(m)
of the sequence converge.]
>Then we can take the difference of partial sums as follows.
>s(2k+1) - s(2k-1) = f(2k) - f(2k+1) = (p_(n-2k) - p_(n-2k-1))/p_n > 0
(increasing)
>s(2k) - s(2k-2) = f(2k) - f(2k-1) = (p_(n-2k) - p_(n-2k+1))/p_n < 0
(decreasing)
>So the first sequence is increasing and tends to a limit or goes to
infinity.
>Similarly, the second sequence is decreasing and tends to a limit or goes
to minus infinity.
>But as n -> infinity and k -> n, we have
>lim(s(2k+1) - s(2k)) = lim ((-1)^(2k+1)) f(2k+1) = 0.
[True, IF n -> infinity and k -> n, then lim(s(2k+1) - s(2k)) = 0. BUT this
does not imply that
lim(s(2k+1) - s(2k)) = 0 as k --> infinity, which must be shown. It is
perfectly conceivable that n --> infinity
but k DOES NOT APPROACH n. Indeed, n and k can both go to infinity, but k
can be fixed at about 1/4 of n, for
example, k = Floor(n/4). Then 2k+1 would be about 1/2 of n, and n-2k-1 about
1/2 of n, so that lim f(2k+1) =
lim p(n-2k-1)/p(n) = lim [(n/2) ln(n/2)] / [n ln n] = 1/2.]
>So both sequences converge to a limit and the limits must be the same.
>Reverting to the original notation, AS(p_n)/p_n is therefore convergent.
[Does not follow, since the previous argument is invalid.]
***
Bruce replied this, some days
later:
1 If professional mathematicians
have concluded that convergence is not provable by traditional methods,
I am not in a position to contradict them since I am not an academic.
2 The step "as n -> infinity and k
-> n" is not one I have seen used in this setting and I will not
therefore seek to defend its legitimacy.
3 If convergence is not readily
provable, we could attempt to prove the weaker statement that if
(AS(p_n))/p_n converges, then it converges to 1/2.
***
This is the SMR's
proof, available as a Word document.
***
Joseph L. Pe criticism to the
SMR proof became soon:
SMR's proof begins
> (1) Lim p(n)/(p(n) - p(n-1) + p(n-2) - p(n-3) + ... + (-1)^(n+1) p(1)) = 2
>Proof:
> p(n) ~ n ln n
> (1) = lim (n ln(n))/(n ln(n) - (n-1) ln(n-1) + (n-2) ln(n-2)-....+ (-1)^k
(n-k) ln(n-k)+ .... )
[True, p(n)~n ln n FOR LARGE N; in fact, p(n)-->n ln n. BUT in the
denominator of (1), that is, in
p(n) - p(n-1) + p(n-2) - p(n-3) + ... + (-1)^(n+1) p(1),
several of the primes p(n-k) are NOT LARGE!
In fact, p(n-k) goes down to .... 7, 5,
3, 2. For such primes, n ln n is far away. Therefore, the assertion
> (1) = lim (n ln(n))/(n ln(n) - (n-1) ln(n-1) + (n-2) ln(n-2)-....+ (-1)^k
(n-k) ln(n-k)+ .... )
is not justified. Note
that if the denominator WERE a nonnegative-term series, the line
> (1) = lim (n ln(n))/(n ln(n) - (n-1) ln(n-1) + (n-2) ln(n-2)-....+ (-1)^k
(n-k) ln(n-k)+ .... )
would be true, since the values of n ln(n) for large n would just dominate
in the limit the values of n ln(n) for small n. However, the denominator is
an alternating series, so this idea won't work! What's worse, the sequence
of partial sums of this series is not even increasing. If it were
increasing, again the large n ln(n)'s would dominate the small n ln(n)'s in
the limit. I don't see how SMR's argument can be fixed at
this point.]
***
|
