Sequences based on algorithms

[Jonathan Post]

Thank you VERY much for working out what seemed intuitively plausible.
 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? That I
was stimulated to submit the seq by Andrew Plewe's seqs, and earlier
seqs in OEIS related to Legendre's conjecture, and then I mentioned
this on seqfans and you nailed it down with a pretty proof is, I would
say, exactly the sort of collaborative effort that Neil J. A. Sloane
intended. As I've said, the Web, and OEIS, have their greatest
strength as collaborationware.

Best,

Jonathan Vos Post

On 11/15/07, Max Alekseyev <maxale at gmail.com> wrote:
> On Nov 14, 2007 11:14 PM, Jonathan Post <jvospost3 at gmail.com> wrote:
>
> > I just submitted a related seq.  Whether the pattern I suggest for the
> > first 5 values (as subset of A132435) continues I leave to others,
> > perhaps through programming it, though I should have clicked "more" to
> > invite that.
> >
> > %I A000001
> > %S A000001 6, 35, 143, 391, 899, 1739, 3233, 5293, 8051, 11413, 17653,
> > 24883, 33389, 43931, 56977, 72731, 92881, 118829, 145699, 176039
> > %N A000001 Smallest prime between n^2 and (n+1)^2 times largest prime
> > between n^2 and (n+1)^2.
> > %C A000001 First 5 values are a subset of A132435.
>
> This is always the case.
> Let p and q be the smallest and largest primes in the interval [n^2,(n+1)^2].
> 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.
> Furthermore, (*) implies that
> q-1 <= [sqrt(q*p)] + y <= q
> and thus nextprime([sqrt(q*p)] + y) = q.
>
> Therefore, q*p belongs to A132435.
>
> Regards,
> Max
>