I have the following sum that I need to evaluate:
$$\sum\limits_{i=1}^{n} \left \lfloor \sqrt{2} \cdot i \right \rfloor$$
If the floor wasn't there it would have been too easy $\sqrt2 \sum\limits_{i=1}^{n} i$, but with the floor added I have no clue how to approach it. Is this sum solveable and if so how do I evaluate it?
Best Answer
I've found a fast enough algorithm to compute the exact value for $ n = 10^{100} $:
$$ \sum_{i=1}^{10^{100}} i\cdot\sqrt 2 = $$
$$ 70710678118654752440084436210484903928483593768847403658833986899536623923105351942519376716382078638821760123411090095254685423841027253480565451739737157454059823250037671948325191776995310741236436 $$
Here's the python code:
Here's the output I get for the above program:
Explanation of the algorithm
First, consider the sequence of differences of successive terms in this sum $ a_n = \lfloor n\sqrt 2 \rfloor - \lfloor(n-1) \sqrt 2 \rfloor $.
This sequence is all $ 1 $s and $ 2 $s: $ 1,1,2,1,2,1,1,2,1, ... $
Given this, we can compute the sum in question with $ \sum_{i=1}^n i \cdot a_{n-i+1} $. But this is obviously too slow with $ n = 10^{100} $. So rather than computing the sequence directly, we want to compute some info about it that still lets us compute the sum.
So we will only keep track of the following for the sequence $ a $:
The length of the sequence $ len(a) $
The function $ f_a(k) = \sum_{i=1}^{len(a)} (i+k) \cdot a_{len(a)-i+1} $. Then $ f_a(0) $ is the sum described above. You can think of this as being the above sum, but with $ a $ having $ k $ zeros appended to it. Because $ f_a $ is a finite sum of linear functions, it is linear. Therefore it is uniquely defined by its slope, $ slope(a) $ and $y$-intercept, $ intercept(a) $
Now suppose we have the above info for sequences $ a $ and $ b $. We can compute the same info for the concatenation of these sequences, $ c $.
$ len(c) = len(a) + len(b) $
$ f_c(k) = f_a(k + len(b)) + f_b(k) $, giving us
So this means that we can build the needed info for the whole sequence by combining info of smaller sequences.
Next, we need the fact that this sequence repeats itself a lot (I mean look at it).
Imagine a line drawn from $ (n,\sqrt n) $ to $ (m,\sqrt m) $ with $ m > n $. Between each time this passes through a vertical line, it passes through either $ 1 $ or $ 2 $ horizontal lines. These $ 1 $s and $2$s are exactly the sequence of differences of terms we defined above at indices $ n $ through $m$. Because of the irrationality of $ \sqrt 2 $, we can move this line around slightly and still get the same sequences. If we've computed the sequence up to some $ k $ and find that the fractional part of the $ k $th term in the original sum, $ frac(m*sqrt(2)) $ is close to the fractional part of the $ n $th term, we can translate the line above to $ (k,\sqrt k) $ to $ (k+m-n, \sqrt {k+m-n}) $ and this won't change the sequence associated with it.
So the algorithm works by building bigger and bigger lines described above by appending them together, remembering the info described above about the sequences associated with the lines (length, slope, intercept).