[seqfan] Re: A216607, A232091.

[David Applegate]

Ed Jeffrey asked:

> The formula for A216607 is

> a(n) = floor((1/4)*ceil(sqrt(4*n))^2) - n  (n>0),

> and the formula for A232091 is

> b(n) = ceiling(n/ceiling(sqrt(n)))*ceiling(sqrt(n))  (n>0).

> Could someone please (try to) find the least n for which

> (1) a(n) = b(n) - n

> does not hold and let me know which n it is?

The equation (1) is true.

Here is an ugly proof.  I suspect that there is a much simpler proof,
probably using standard results about integer square roots I don't
know, but I just bashed along.

We want to show (for all integers n > 0):

floor((1/4)*ceil(sqrt(4*n))^2) == ceiling(n/ceiling(sqrt(n)))*ceiling(sqrt(n))

Write sqrt(n) = k - f, where k is an integer and 0 <= f < 1, so:

   ceiling(sqrt(n)) = k

   n = k^2 - 2kf + f^2

   floor((1/4)*ceil(sqrt(4*n))^2) = floor((1/4)*ceil(2k-2f)^2)

   ceiling(n/ceiling(sqrt(n)))*ceiling(sqrt(n)) = ceiling(n/k)*k
         = ceiling(k - 2f + f^2/k) * k

First, consider the case when 0 <= f < 1/2.  In this case,

   floor((1/4)*ceil(2k-2f)^2) = floor(k^2) = k^2

Since k >= 1, f^2/k <= 2f, so

   0 <= 2f - f^2/k < 1

and

   ceiling(k - 2f + f^2/k) * k = k^2

and we are done.

Now, consider the case when 1/2 <= f < 1.  In this case,

   floor((1/4)*ceil(2k-2f)^2) = floor(k^2 - k + 1/4) = k^2 - k

Note that

   n - k^2 + k = f^2 - (2f-1) k

The left hand side is an integer, and the right hand side is < 1, so
it must be <= 0.  But

   f^2 - (2f-1) k <= 0

implies

   f^2/k - 2f <= -1

or

   2f - f^2/k >= 1

and since

   2f - f^2/k < 2,

we have

   ceiling(k - 2f + f^2/k) * k = (k-1)*k = k^2 - k

and we are done.

David Applegate

> From seqfan-bounces at list.seqfan.eu Thu Jan  9 14:19:22 2014
> From: "Lars Blomberg" <lars.blomberg at visit.se>
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Date: Thu, 9 Jan 2014 18:24:01 +0100
> Subject: [seqfan] Re: A216607, A232091.

> The equation (1) is true for all n < 10^9.

> Regards
> /Lars Blomberg

> -----Ursprungligt meddelande----- 
> From: L. Edson Jeffery 
> Sent: Thursday, January 09, 2014 6:02 AM 
> To: seqfan at list.seqfan.eu 
> Subject: [seqfan] A216607, A232091. 

> The formula for A216607 is

> a(n) = floor((1/4)*ceil(sqrt(4*n))^2) - n  (n>0),

> and the formula for A232091 is

> b(n) = ceiling(n/ceiling(sqrt(n)))*ceiling(sqrt(n))  (n>0).

> Could someone please (try to) find the least n for which

> (1) a(n) = b(n) - n

> does not hold and let me know which n it is?

> If (1) is not true, then I want to submit the sequence {b(n) - n} since it
> is related to A232091.

> Thanks,

> Ed Jeffery

> _______________________________________________

> Seqfan Mailing list - http://list.seqfan.eu/

> _______________________________________________

> Seqfan Mailing list - http://list.seqfan.eu/