11
$\begingroup$

[A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)).][1]

If $n = 5$ then

$$\left\lfloor1\sqrt{2}\right\rfloor+ \left\lfloor2\sqrt{2}\right\rfloor + \left\lfloor3\sqrt{2}\right\rfloor +\left\lfloor4 \sqrt{2}\right\rfloor+ \left\lfloor5\sqrt{2}\right\rfloor = 1+2+4+5+7 = 19$$

Sequence from $1$ to $20$ is:

$S=\{1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,25,26,28\}$

I want to find answer for $10^{100} n$?

$\endgroup$
  • $\begingroup$ Clearly $10^{100}$ is large enough for any asymptotic behaviour to take place. Are you looking for an exact value of $a_{10^{100}}$ or an approximation? $\endgroup$ – Hugh Dec 10 '16 at 6:32
  • $\begingroup$ @Hugh if possible both of them :) $\endgroup$ – Sinoheh Dec 10 '16 at 6:37
  • 3
    $\begingroup$ You said you wanted both exact and asymptotic. It's quite rude to ignore my answer and give a two word response for what more you want $\endgroup$ – Hugh Dec 10 '16 at 6:47
  • 2
    $\begingroup$ Actually, $i\sqrt{2}-[i\sqrt{2}]$ is equidistributed on $[0,1)$, so finding asymptotic behavior is the best we can. The values of averaged sum behaves just like $\frac{\sqrt{2}n+\sqrt{2}-1}{2}$. $\endgroup$ – HyJu Dec 10 '16 at 6:57
  • 3
    $\begingroup$ @Hugh Yes it is. See link. For a proof, read the Fourier analysis textbook written by E.M.Stein and R.Shakarchi. $\endgroup$ – HyJu Dec 10 '16 at 8:13
19
$\begingroup$

Let $S(\alpha,n) = \sum_{k=1}^n \lfloor \alpha k \rfloor$ for $\alpha$ some irrationnal positive number.

if $\alpha \ge 2$ we let $\beta = \alpha-1$ and you get
$S(\alpha,n) = S(\beta,n) + \sum_{k=1}^n k \\ = S(\beta,n) + n(n+1)/2$

if $1 < \alpha < 2$, there is a theorem that says if $\beta$ satisfies $\alpha^{-1} + \beta^{-1} = 1$, then the sequences $\lfloor \alpha n \rfloor$ and $\lfloor \beta n \rfloor$ for $n \ge 1$ partition $\Bbb N$ (not counting $0$)

Therefore, letting $m = \lfloor \alpha n \rfloor$, $S(\alpha,n) + S(\beta, \lfloor m/\beta \rfloor) = \sum_{k=1}^m k = m(m+1)/2$
Also, $\lfloor m/ \beta \rfloor = m - \lceil m/\alpha \rceil = m- n = \lfloor (\alpha-1)n \rfloor$.

Then, letting $n' = \lfloor (\alpha-1)n \rfloor $ you have
$S(\alpha,n) = (n+n')(n+n'+1)/2 - S(\beta,n')$

So those two formulas give you a very fast way to compute $S$ if you can compute $n' = \lfloor (\alpha-1) n \rfloor$


In your case, $\alpha = \sqrt 2$, so you begin in the second case where you get $\beta = 2+\sqrt 2$. Since the sequence of $\alpha$s you get is periodic, you can get a recurrence formula :

Let $n' = \lfloor (\sqrt 2 -1) n \rfloor$,

$S(\sqrt 2,n) = (n+n')(n+n'+1)/2 - S(2+\sqrt 2,n') \\ = (n+n')(n+n'+1)/2 - S(\sqrt 2,n') - n'(n'+1) \\ = nn'+n(n+1)/2-n'(n'+1)/2 - S(\sqrt 2,n')$

For example this tells you that $S(\sqrt 2,5) = 22 - S(\sqrt 2, 2) = 22 - 3 + S(\sqrt 2, 0) = 19.$


Since at each step $n$ is approximately multiplied by $\sqrt 2 - 1$, the arguments decrease exponentially. For $n = 10^{100}$ you need approximately $\lceil {100 \log {10}/\log (\sqrt 2-1)} \rceil = 262$ steps to complete the recursion. This is basically equivalent to computing the powers of $(\sqrt 2-1)$ with enough precision and should be doable quickly on any computer.

$\endgroup$
  • $\begingroup$ Could you please explain more $\endgroup$ – Sinoheh Dec 11 '16 at 11:28
  • $\begingroup$ explain more what ? $\endgroup$ – mercio Dec 11 '16 at 11:58
  • $\begingroup$ Nothing. Its clear. i'm testing and I will share answer $\endgroup$ – Sinoheh Dec 11 '16 at 12:03
  • 2
    $\begingroup$ @mercio The same question, how can it be done for say $e$? Could you show an example for it as it's greater than 2 like $S(5,e)$? Thanks $\endgroup$ – four_lines Jun 2 '17 at 11:18
  • $\begingroup$ @IndoUbt um do you have any difficulty when applying the two formulas for $S(e,5)$ ? $\endgroup$ – mercio Jun 2 '17 at 21:26
7
$\begingroup$

It is clear that, because the sequence $\{<n\sqrt{2}>\}$(the fractional part) is equidistributed over the interval $[0,1)$, we have $$\tag{1}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\sum_{n=1}^N <n\sqrt{2}>\label{1}$$ and for the latter sum, $$\tag{2}\frac{1}{N}\sum_{n=1}^N <n\sqrt{2}> \to \frac{1}{2}\label{2}$$ as $N \to \infty$.

In other words, we have $$\tag{3}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}+o(N)\label{3}$$ as $N \to \infty$.

So , in average, we have $$\tag{4}\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{(N+1)\sqrt{2}}{2}-\frac{1}{2}+o(1)\label{4}$$ and in fact the remainder term is smaller than $1/2$.

So we conclude that $\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor$(which is not an integer) is very close to the nearest integer to the number $\frac{N\sqrt{2}+\sqrt{2}-1}{2}$.

One interesting thing I observed is that we in fact have more nice decay of the error term, that is, $$\tag{5}\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{(N+1)\sqrt{2}}{2}-\frac{1}{2}+o(\frac{1}{N}),\label{5}$$ so, return to our original problem, we come up with $$\tag{6}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}+o(1)\label{6}$$ and in fact the error term is again smaller than 1/2. So the sum is the nearest integer to the number $$\tag{7}\label{7}\frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}=\frac{N(N\sqrt{2}+\sqrt{2}-1)}{2}$$.

But the proof could possibly require more nice approximation than just the equidistribution of the sequence. (And there seems even more faster decay of the error term!!)

++Added))

What always true in the above discussion is $\eqref{3}$ or the equivalent form $\eqref{4}$. So we can exactly figure out the average value of the Beatty sequence of $\sqrt{2}$, that is, the division of $\eqref{1}$ by $N$.

However, for the exact computation of the value of the sum $\eqref{1}$, we need more precise approximation on the error term like $\eqref{5}$ or $\eqref{6}$. Unfortunately, $\eqref{5}$ is not true and so is $\eqref{7}$.

I think the best we can do is this: For any irrational $\gamma$, let $L(\gamma)=1-|1-2<\gamma>|$. Then we have $$\left\vert \sum_{n=1}^N \lfloor n\gamma \rfloor - \left(\frac{N(N+1)\gamma}{2}-\frac{N}{2}\right) \right\vert \leq \frac{c}{L(\gamma)}$$ with $c$ a constant irrelevant to $\gamma$ and $N$($c=2$ would actually work)

This essentially asserts that the randomness of the distribution of the sequence $\{<n\gamma>\}$ in $[0,1)$ depends on how close $<\gamma>$ is to $0$ or $1$(Note that $L(\gamma)/2$ is the minimum distance from $<\gamma>$ to $0$ and to $1$. Of course this is really a naive approximation, need to be adjusted in many ways.

$\endgroup$
  • $\begingroup$ This is work for little numbers. Do you know how to generate this numbers? oeis.org/A194104 also watch this oeis.org/A194102 $\endgroup$ – Sinoheh Dec 10 '16 at 14:58
  • $\begingroup$ @Sinoheh Actually, I tried numbers no more than you've tested. Try the averaged one at the middle of my answer. This must work for all large values of $N$. Numerical test seems very interesting though. Can you show me the results? $\endgroup$ – HyJu Dec 10 '16 at 15:54
  • $\begingroup$ For example: input: "23223423" your result is : 381362049543566.61858316753391048249640080000565 with halfUp is : 381362049543567 and the correct answer is :381362049543566. If you want I test with bigger number I must put my server to work until tomorrow to test 10^31. If you think it can help us I will make 1 sample for this question with 10 ^31 number $\endgroup$ – Sinoheh Dec 10 '16 at 16:08
  • $\begingroup$ It looks like the formula is quite accurate, and the error can be $\pm 1$ and $\pm 2$. For example, if we define error(N) as the value of the last formula - the true value, then $error(72)=1$, $error(35)=-1$, $error(83652)=2$, $error(40390)=-2$. And this numbers looks random for me. I'm wondering whether it is possible to nail down the exact summation value. $\endgroup$ – xslittlegrass Dec 11 '16 at 1:56
  • $\begingroup$ And for N up to 100000, there are 12086 numbers with error=-1 and 14880 numbers with error=1 and 2 numbers with error=-2 and 12 numbers with error=2. $\endgroup$ – xslittlegrass Dec 11 '16 at 2:04

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.