Sum of a Product of Floors of Square Roots ... ApproximatelyDate: 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! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/