As many of the questions that I have asked recently, this is related to my investigations in finding a standard mathematical constant that has 50% of its binary digits equal to zero. My approximation is good enough for my purpose (solving a small piece of the puzzle), but I think it is worth mentioning and study a bit further.
$\sum_{k=1}^n \{k \log_2 3\} = \Big(\frac{n(n+1)}{2}\log_2 3\Big) -h(n) + \epsilon_n$,
where $\epsilon_n$ is the error and $h(n)$ is an integer. More specifically:
$h(n) =\Big\lfloor \frac{n(n+1)}{2}\log_2 3 - \frac{n}{2} + 3\Big\rfloor$.
The approximation also works great if you replace $\log_2 3$ by another irrational number, but it fails with rational numbers.
Questions
- In absolute value, what is the maximum value of the error (the error is always a very small integer)
- Is it possible to obtain an exact formula? The error, while quite chaotic, seems to exhibit near periodicity. It is shown in the picture below: the Y-axis is the error, the X-axis is $n$.
I actually obtained an exact formula, but it does not seem very useful and involves a recursion:
$\sum_{k=1}^n \{k \log_2 3\} =\frac{n}{2}+f(n)$ with $f(n+1) = 2f(n) - f(n-1) + a(n)$ and $a(n) = \log_2 3 - 2$ if $\{n(\log_2 3 - 1)\} > 2 - \log_2 3$, $a(n) = \log_2 3-1 $ otherwise. The initial values are $f(1) = \log_2 3 - \frac{1}{2}$ and $f(2) = 3\log_2 3 - 5$.
$$\sum_{k=1}^n \{k \log_2(3)\} = $$
$$\log_2(3)\sum_{k=1}^n k - \sum_{k=1}^n \lfloor k \log_2(3)\rfloor = $$ $$\frac{n(n+1)}{2}\log_2(3) - \sum_{k=1}^n \lfloor k\log_2(3)\rfloor$$
So the meat of your question is:
$$\sum_{k=1}^n \lfloor k\log_2(3)\rfloor \approx \Big\lfloor \frac{n(n+1)}{2}\log_2 3 - \frac{n}{2} + 3\Big\rfloor$$
The equidistribution theorem confirms this as for large $n$ we can say:
$$\sum_{k=1}^n \lfloor k\log_2(3)\rfloor \approx \sum_{k=1}^n \left(k\log_2(3) - \frac{1}{2}\right )$$
And
$$\sum_{k=1}^n \left(\log_2(3^k) - \frac{1}{2}\right ) = \frac{n(n+1)}{2} \log_2(3)-\frac{1}{2}n$$
Your final $+3$ just offsets the bias from flooring, but lowers overall accuracy as all your errors are positive, rather than alternating as negative and positive. Better would be to only add $\frac{1}{2}$ to make the floor round.