The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Sum of a Product of Floors of Square Roots ... Approximately

Date: 03/30/2016 at 06:43:48
From: Ruan
Subject: Formula for Sum k=0 to n (floor(sqrt(n+k) * floor(sqrt(k)))

Hello, I am looking for an explicit formula for

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k)))

This seems simple, particularly since I have explicit formulas for each 
of the constituent sums,

   sum k from 0 to n (floor(sqrt(n + k)))
   sum k from 0 to n (floor(sqrt(k)))

But I just can't get it.



Date: 03/30/2016 at 17:37:12
From: Doctor Vogler
Subject: Re: Formula for Sum k=0 to n (floor(sqrt(n+k) * floor(sqrt(k)))

Hi Ruan,

Thanks for writing to Dr. Math. 

What kind of "explicit formula" are you looking for? For starters, what 
are the explicit formulas that you mentioned already having?

Also, if no explicit formula exists, are you interested in computable 
formulas? or numerical approximations? If so, how big of an n are you 
concerned with?

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 03/31/2016 at 03:25:12
From: Ruan
Subject: Formula for Sum k=0 to n (floor(sqrt(n+k) * floor(sqrt(k)))

Hi,

The formulas I already have look like this:

   sum k from 1 to n (floor(sqrt(k))) 
                   = (floor(sqrt(n)) - 1)th square pyramidal number 
                   + (floor(sqrt(n)) - 1)th triangular number
                   + floor(sqrt(n)) * (n - floor(sqrt(n))^2 + 1)

So, this is a direct formula. The size of n doesn't matter.

This is the kind of formula that I am interested in, if it makes sense.

If no formula exists, computable or numerical approximations for very 
large n would also be fine.



Date: 04/02/2016 at 16:34:31
From: Doctor Vogler
Subject: Re: Formula for Sum k=0 to n (floor(sqrt(n+k) * floor(sqrt(k)))

Hi Ruan,

Thanks for writing to Dr. Math. 

I would derive a formula like the one you gave differently.

The sum from k = 1 to k = n of (floor(sqrt(k))) equals the sum over all 
integers s of s times the number of integers k between 1 and n for which 
s = floor(sqrt(k)).

   sum k from 1 to n (floor(sqrt(k))) 
       = sum over s of s * (number of k between 1 and n 
                            for which floor(sqrt(k)) = s) 
       = sum over s of s * (number of k between 1 and n 
                            for which s <= sqrt(k) < s + 1) 
       = sum over s of s * (number of k between 1 and n 
                            for which s^2 <= k < (s + 1)^2).

Now, for most s between 1 and about sqrt(n), the number of such k is 
equal to the number of integers from s^2 to (s + 1)^2 - 1, which is 
2s + 1 numbers. (Of course, there are no such integers when s <= 0, and 
none when s > sqrt(n).) The tricky part is the last s with any k. The 
last s will be floor(sqrt(n)), which I will call m; and for this s = m, 
the number of k is n + 1 - s^2. 

So we have

   sum k from 1 to n (floor(sqrt(k))) 
       = sum over s of s * (number of k between 1 and n 
                            for which s^2 <= k < (s + 1)^2)
       = (sum s from 1 to m - 1 of s*(2s + 1)) + m*(n + 1 - m^2)
       = 1/3*(m - 1)(m)(2m - 1) + 1/2*(m - 1)m + m*(n + 1 - m^2)
       = nm - m(m - 1)(2m + 5)/6

Now, can we do the same thing to your more complex sum? The trick is that 
now you have TWO floor(sqrt)'s. But we can still make a start.

The sum from k = 0 to k = n of (floor(sqrt(n + k)) * floor(sqrt(k))) 
equals the sum over all pairs of integers s and t of s times t times the 
number of k between 1 and n for which s = floor(sqrt(k)) and 
t = floor(sqrt(n + k)).

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k)))
       = sum over s, t of s*t*(number of k between 1 and n 
                               for which floor(sqrt(k)) = s 
                                     and floor(sqrt(n + k)) = t) 
       = sum over s, t of s*t*(number of k between 1 and n 
                               for which s^2 <= k < (s + 1)^2 
                                     and t^2 <= n + k < (t + 1)^2)

Now, we could go about simplifying this in two ways:

   (1) For each s, there are either 1 or (only occasionally) 2 values
       for t. So we could write it as

          sum over s of (sum for one or both t's)

   (2) For each t, there may be a range of values for s. So we could 
       write it as

          sum over t of (sum over s)

But when I try to simplify this, I get something of the form

          sum over t of (sum over s of s*t*(2s + 1) + boundary terms)

Then, the inner sum has the form

          t times polynomial in s2 minus polynomial in s1

Here, s1 and s2 are the minimum and maximum values of s for that choice 
of t, which means that they are approximately sqrt(t^2 - n) and 
sqrt((t + 1)^2 - n), respectively.

Unfortunately, now we end up needing to sum something (over t) the terms 
of which involve sqrt(t^2 - n) and sqrt((t + 1)^2 - n). We don't have a 
direct formula for that, and if we tried switching variables like we did 
the first time, then the square inside the square root will mean that we 
still end up with a square inside a square root.

It's possible that we could find a way to compute this sum, but it's 
looking very messy -- so it's pretty likely that there is no 
closed-form solution.

Now, if you want an approximation to the sum, then we should proceed to 
simplify the exact sums as far as we can get, before switching to 
approximation methods. It feels like the second approach would be easier, 
with t being in the outer sum.

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k))) 

       = sum over s, t of s*t*(number of k between 1 and n 
                               for which s^2 <=   k   < (s + 1)^2 and 
                                         t^2 <= n + k < (t + 1)^2) 

       = sum over t from floor(sqrt(n)) to floor(sqrt(2n)) 
         of sum over s of s*t*(number of k between 1 and n 
                               for which s^2 <=   k   < (s + 1)^2 
                                     and t^2 <= n + k < (t + 1)^2)

Now, for each t, the smallest and largest values for s will be special 
cases. The general case, for values of s in between, will have 2s + 1 
values of k, from s^2 to (s + 1)^2 - 1, when those satisfy t^2 - n <= s^2 
and (s + 1)^2 <= (t + 1)^2 - n.

The smallest value of s will be s = floor(sqrt(t^2 - n)). This will 
include k values with t^2 - n <= k < (s + 1)^2, of which there are 
(s + 1)^2 - t^2 + n.

The largest value of s will be s = floor(sqrt((t + 1)^2 - n)). This 
will include k values with s^2 <= k < (t + 1)^2 - n, of which there 
are (t + 1)^2 - s^2 - n.

So if we let f(t) = floor(sqrt(t^2 - n)), then the smallest value is 
s = f(t) and the largest is s = f(t + 1), and

   sum over s of s*t*(number of k between 1 and n 
                      for which s^2 <=   k   < (s + 1)^2 and 
                                t^2 <= n + k < (t + 1)^2)
        =     f(t)*t*((f(t) + 1)^2 - t^2 + n)
           + f(t + 1)*t*((t + 1)^2 - f(t + 1)^2 - n)
           + sum from s = f(t) + 1 to f(t + 1) - 1 of st(2s + 1) 

        =    f(t)*t*((f(t) + 1)^2 - t^2 + n)
          + f(t + 1)*t*((t + 1)^2 - f(t + 1)^2 - n) 
          + t*(f(t + 1)(f(t + 1) - 1)(4f(t + 1) + 1)/6 
                     - f(t)(f(t) + 1)(4f(t) + 5)/6)

        =    f(t)*t*(f(t) + 1)^2 - f(t)*t*t^2
           + f(t)*t*n - t*f(t)(f(t) + 1)(4f(t) + 5)/6 
           + f(t + 1)*t*(t + 1)^2 
           - f(t + 1)*t*f(t + 1)^2 
           - f(t + 1)*t*n 
           + t*f(t + 1)(f(t + 1) - 1)(4f(t + 1) + 1)/6 

        =   t*[f(t)*(f(t) + 1)^2 - f(t)*t^2 + f(t)*n 
          - f(t)(f(t) + 1)(4f(t) + 5)/6 
          + f(t + 1)*(t + 1)^2 
          - f(t + 1)*f(t + 1)^2 
          - f(t + 1)*n 
          + f(t + 1)(f(t + 1) - 1)(4f(t + 1) + 1)/6] 

        =   t*[f(t)^3 + 2*f(t)^2 + f(t) - f(t)*t^2 
          + f(t)*n - (2/3)f(t)^3 - (3/2)f(t)^2 - (5/6)f(t)
          + f(t + 1)*(t + 1)^2 - f(t + 1)^3 - f(t + 1)*n 
          + (2/3)f(t + 1)^3 - (1/2)f(t + 1)^2 - (1/6)f(t + 1)] 

        =   t*[- f(t)*t^2 + f(t)*n + (1/3)f(t)^3 + (1/2)f(t)^2 + (1/6)f(t)
          + f(t + 1)*(t + 1)^2 - f(t + 1)*n - (1/3)f(t + 1)^3 
          - (1/2)f(t + 1)^2 - (1/6)f(t + 1)] 

        =   t*[G(t + 1) - G(t)]

Here,

   G(t) = f(t)*t^2 - f(t)*n - (1/3)f(t)^3 - (1/2)f(t)^2 - (1/6)f(t)
        = f(t)*t^2 - f(t)*n - f(t)*(f(t) + 1)*(2*f(t) + 1)/6

When f(t + 1) = f(t) + 1, then there are only two s values, so the 
smallest and largest s (special cases) are fine. There is nothing in 
between, which is okay, since in that case the sum for the middle part 
is zero.

The case you should be concerned about is where f(t) = f(t + 1): then, 
there is only one s -- namely s = f(t) = f(t + 1). That means that 
floor(sqrt(t^2 - n)) =

     s  = floor(sqrt((t + 1)^2 - n))
     s <= sqrt(t^2 - n) < sqrt((t + 1)^2 - n) <  s + 1
   s^2 <=      t^2 - n  <      (t + 1)^2 - n  < (s + 1)^2

Adding the first and the last inequalities together, we get:

      (t + 1)^2 - n + s^2 < t^2 - n + (s + 1)^2
   t^2 + 2t + 1 - n + s^2 < t^2 - n + s^2 + 2s + 1
                       2t < 2s

This means that t < s, which is ridiculous, since it would imply that 
t^2 < s^2 <= t^2 - n, and this in turn would mean that n < 0. So this 
case never happens and we don't have to worry about it.

The nice form of that result allows us to simplify the sum over t, since

   sum t from a to b - 1 of t*[G(t + 1) - G(t)] 

   =   sum t from a to b - 1 of t*G(t + 1) 
     - sum t from a to b - 1 of t*G(t)

   =   sum t from a + 1 to b of (t - 1)*G(t)
     - sum t from a to b - 1 of t*G(t)

   = (b - 1)*G(b) - a*G(a)
     + sum t from a + 1 to b - 1 of (t - 1)*G(t) 
     - sum t from a + 1 to b - 1 of t*G(t) 

   = (b - 1)*G(b) - a*G(a) 
     + sum t from a + 1 to b - 1 of [(t - 1)*G(t) - t*G(t)] 

   = (b - 1)*G(b) - a*G(a) - sum t from a + 1 to b - 1 of G(t)

On the other hand, while that formula is true for most t, the largest and 
smallest values of t are, again, incorrect. But we can make a formula for 
the largest and smallest values of t. The hard part is going to be that 
sum over G(t).

The smallest t is t = floor(sqrt(n)), for which s goes from 1 to f(t + 1).

The largest t is t = floor(sqrt(2n)), for which s goes from f(t) to
floor(sqrt(n)). But when s = floor(sqrt(n)), then k goes from s^2 to n, 
so there are n + 1 - s^2 such k.

Let p = floor(sqrt(n)) and q = floor(sqrt(2n)). Then

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k))) 
   =   sum t from p + 1 to q - 1 of t*[G(t + 1) - G(t)] 
     + f(p + 1)*p*((p + 1)^2 - f(p + 1)^2 - n) 
     + sum s from 1 to f(p + 1) - 1 of sp(2s + 1) 
     + f(q)*q*((f(q) + 1)^2 - q^2 + n) + pq(n + 1-p^2) 
     + sum s from f(q) + 1 to p - 1 of sq(2s + 1)

   =   (q - 1)*G(q) - (p + 1)*G(p + 1)
     - sum t from p + 2 to q - 1 of G(t) 
     +       f(p + 1)*p*((p + 1)^2 - f(p + 1)^2 - n) 
     + 1/3*p*f(p + 1)*(f(p + 1) - 1)*(2*f(p + 1) - 1)
     + 1/2*p*f(p + 1)*(f(p + 1) - 1) 
     + f(q)*q*((f(q) + 1)^2 - q^2 + n) + pq(n + 1 - p^2) 
     + 1/3*q*p*(p - 1)*(2p - 1) + 1/2*q*p*(p - 1) 
     - 1/3*q*f(q)*(f(q) + 1)*(2*f(q) + 1) - 1/2*q*f(q)*(f(q) + 1) 

   =   q*G(q) - p*G(p + 1)
     - sum t from p + 1 to q of G(t)
     +       f(p + 1)*p*((p + 1)^2 - f(p + 1)^2 - n)
     + 1/3*p*f(p + 1)*(f(p + 1) - 1)*(2*f(p + 1) - 1) 
     + 1/2*p*f(p + 1)*(f(p + 1) - 1) 
     + f(q)*q*((f(q) + 1)^2 - q^2 + n) + pq(n + 1 - p^2) 
     + 1/3*q*p*(p - 1)*(2p - 1) + 1/2*q*p*(p - 1)
     - 1/3*q*f(q)*(f(q) + 1)*(2*f(q) + 1) - 1/2*q*f(q)*(f(q) + 1) 

   = pq(n - (p - 1)(2p + 5)/6) - sum t from p + 1 to q of G(t)

This is the main result of the exact mathematical analysis, so I'll 
repeat it:

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k)))
   = pq(n - (p - 1)(2p + 5)/6) - sum t from p + 1 to q of G(t)

In particular, notice that if n is a few million or less, then a computer 
could quickly compute your original sum directly, but you'll notice it 
slowing down when n gets up to the billions or more, because you have to 
sum n terms.

With this new formula, you only have on the order of sqrt(n) terms, which 
means that a computer could easily compute the exact value for n up 
through the trillions, and -- with a little more effort (and a more 
efficient program) -- it could compute the sum for n as large as something 
in the millions of trillions.

Furthermore, this gives us a better way to get a good formula for an 
approximation to the sum. For a first-order approximation, we approximate 

      p by sqrt(n)
      q by sqrt(2n)
   f(t) by sqrt(t^2 - n)
   G(t) by f(t)*(t^2 - n) - (1/3)f(t)^3

And we approximate the sum by an integral.

The short story is that 

   sum k from 0 to n (floor(sqrt(n + k)) * floor(sqrt(k))) 

   = approximately   n^2(2/3*sqrt(2)) 
                   - integral p to q of (2/3)(t^2 - n)^(3/2) dt

                   = n^2(2/3*sqrt(2))
                   - (2/3)n^2 * integral 1 to sqrt(2) of (u^2 - 1)^(3/2) du

Use the change of variables t = u*sqrt(n) to relate those two integrals. 
The antiderivative of (u^2 - 1)^(3/2), which you can check by 
differentiating, is

  1/8 * ( u*(2u^2 - 5)*sqrt(u^2 - 1) + 3*ln(sqrt(u^2 - 1) + u) ) + C

So the integral evaluates to

  1/8 * ( 3*ln(sqrt(2) + 1) - sqrt(2) )

This means that your sum is approximately

  n^2 * ( 3/4 * sqrt(2) - 1/4*log(sqrt(2) + 1) )

Here, that coefficient is

   3/4 * sqrt(2) - 1/4*log(sqrt(2) + 1) 
   = 0.84031677502493553029311421...

I expect that it wouldn't take too much work to prove that the difference 
between the actual sum and this multiple of n^2 is always less than some 
number times n^(3/2).

That means that if n has about 1000 digits, then the sum has about 2000 
digits, and n^2 * ( 3/4 * sqrt(2) - 1/4*log(sqrt(2) + 1) ) will give about 
the first 500 digits of the sum. That's a pretty good approximation.

It *might* be possible to find a second-order term, which would be the 
multiple of n^(3/2) that closely approximates the difference, so that we 
could get an estimate within a multiple of n. But that will be a lot 
harder, and I'm not certain it will be feasible.

It also *might* be possible to find a better exact formula, by doing some 
transformation of the function f(t) that allows for easier summing. But 
since it involves a square inside the square root, there are about as 
many values of f(t) as there are of t, so I'm not optimistic that this 
is possible.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 04/03/2016 at 09:04:13
From: Ruan
Subject: Thank you (Formula for Sum k=0 to n (floor(sqrt(n + k) * floor
(sqrt(k))))

Thank you very much. This is brilliant! I am going to need some time to 
chew on it. Thanks a lot!
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/