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
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/