3
$\begingroup$

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

enter image description here

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Steven Stadnicki Aug 3 at 0:45
  • $\begingroup$ 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$. $\endgroup$ – Vincent Granville Aug 3 at 1:21
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Aug 4 at 1:45
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Aug 4 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.