Sequences based on algorithms

[Max Alekseyev]

On Nov 15, 2007 11:38 AM, Jonathan Post <jvospost3 at gmail.com> wrote:
>  May I ask that your proof appear as a comment in my so-far unnumbered
> seq, as it is sort enough, and nicely connects several seqs?

Sure. This is an updated proof.

Let p and q be the smallest and largest primes in the interval
[n^2,(n+1)^2].Note that in the case p=q the statement trivially holds.
So, for the rest of the proof we assume p < q. Then

n^2 < p < q < (n+1)^2
n < sqrt(p) < sqrt(q) < n+1
sqrt(q) - sqrt(p) < n+1 - n = 1
0 < (sqrt(q) - sqrt(p))^2 = q - 2*sqrt(q*p) + p < 1
0 < q - 2*[sqrt(q*p)] + p < 3

Since q - 2*[sqrt(q*p)] + p is integer,
1 <= q - 2*[sqrt(q*p)] + p <= 2
[sqrt(q*p)] - p + 1 <= q - [sqrt(q*p)] <= [sqrt(q*p)] - p + 2.    (*)

Now let y = [sqrt(q*p)] - p + 1. Then [sqrt(q*p)] - y = p - 1 and thus
nextprime([sqrt(q*p)] - y) = nextprime(p - 1) = p (it is easy to see
that p=3 is impossible).
Furthermore, (*) implies that
q-1 <= [sqrt(q*p)] + y <= q
and thus nextprime([sqrt(q*p)] + y) = q.

Therefore, q*p belongs to A132435.

Max