Spectacular approximation to $\sum_{k=1}^n \{k \log_2 3\}$ where the curly brackets represent the fractional part

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$$.

• Isn't this essentially just saying that the values of your sum are nearly-equidistributed $\mod 1$? IIRC distribution of sequences of the form $\{n\alpha\}$ for irrational $\alpha$ have been pretty well-studied and I suspect that there's a connection to the continued fraction of $\alpha$. – Steven Stadnicki Aug 3 at 0:45
• I think it is more than that. Equidistribution provides a first-order, trivial approximation to the sum. Here it is a second-order approximation, and it depends on $\alpha$. – Vincent Granville Aug 3 at 1:21

$$\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.

• Agreed. But I am still surprised how this approximation is accurate, and wondering if you can get a better one -- an exact formula indeed, that does not involve an infinite summation. – Vincent Granville Aug 4 at 1:45
• What I meant is that the standard approximation is $\sum_{k=1}^n k \log_2 3 \approx \frac{n}{2}$ and is less accurate. It must be less accurate since it does not involve $\log_2 3$ and provides the same (weak) level of accuracy wtheter the number is $\log_2 3$ or any other irrational number. – Vincent Granville Aug 4 at 2:34