Cómo encontrar $\sum_{i=1}^n\left\lfloor i\sqrt{2}\right\rfloor$ A001951 A Beatty secuencia: a (n) = floor(n*sqrt(2)).

Question

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

Si $n = 5$ luego

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

Secuencia de $1$ $20$ es:

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

¿Quiero encontrar respuesta $10^{100} n$?

Answer 1

Deje $S(\alpha,n) = \sum_{k=1}^n \lfloor \alpha k \rfloor$ $\alpha$ algunos irrationnal número positivo.

si $\alpha \ge 2$ dejamos $\beta = \alpha-1$ y se obtiene
$S(\alpha,n) = S(\beta,n) + \sum_{k=1}^n k \\ = S(\beta,n) + n(n+1)/2$

si $1 < \alpha < 2$, hay un teorema que dice que si $\beta$ satisface $\alpha^{-1} + \beta^{-1} = 1$, entonces las secuencias de $\lfloor \alpha n \rfloor$ $\lfloor \beta n \rfloor$ $n \ge 1$ partición $\Bbb N$ (sin contar a $0$)

Por lo tanto, dejar que $m = \lfloor \alpha n \rfloor$, $S(\alpha,n) + S(\beta, \lfloor m/\beta \rfloor) = \sum_{k=1}^m k = m(m+1)/2$
También, $\lfloor m/ \beta \rfloor = m - \lceil m/\alpha \rceil = m- n = \lfloor (\alpha-1)n \rfloor$.

Luego, dejando $n' = \lfloor (\alpha-1)n \rfloor $
$S(\alpha,n) = (n+n')(n+n'+1)/2 - S(\beta,n')$

Así que los dos fórmulas de darle una forma rápida de calcular $S$ si usted puede calcular el $n' = \lfloor (\alpha-1) n \rfloor$

---

En su caso, $\alpha = \sqrt 2$, así que comiencen en el segundo caso donde te $\beta = 2+\sqrt 2$. Desde la secuencia de $\alpha$s que se obtiene es periódica, se puede obtener una fórmula de recurrencia :

Deje $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')$

Por ejemplo, este le dice que $S(\sqrt 2,5) = 22 - S(\sqrt 2, 2) = 22 - 3 + S(\sqrt 2, 0) = 19$.

---

Ya que en cada paso $n$ es de aproximadamente multiplicado por $\sqrt 2 - 1$, los argumentos disminuir exponencialmente. Para$n = 10^{100}$, se necesitan aproximadamente $\lceil {100 \log {10}/\log (\sqrt 2-1)} \rceil = 262$ pasos para completar la recursividad. Esto es básicamente equivalente al cálculo de las potencias de $(\sqrt 2-1)$ con la suficiente precisión y debe ser factible rápidamente en cualquier equipo.

Answer 2

Es claro que, debido a la secuencia de $\{<n\sqrt{2}>\}$(la parte fraccionaria) es equidistributed en el intervalo de $[0,1)$, tenemos $$\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}$$ y para la última suma, $$\tag{2}\frac{1}{N}\sum_{n=1}^N <n\sqrt{2}> \to \frac{1}{2}\label{2}$$ como $N \to \infty$.

En otras palabras, tenemos $$\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}$$ como $N \to \infty$.

Así , en promedio, hemos $$\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}$$ y de hecho el resto término es menor que $1/2$.

Así llegamos a la conclusión de que $\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor$(que no es un número entero) es muy cercano al entero más cercano al número $\frac{N\sqrt{2}+\sqrt{2}-1}{2}$.

Una cosa interesante de la que he observado es que de hecho tenemos más agradable la decadencia del término de error, que es, $$\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}$$ así, volverá a nuestro problema original, nos encontramos con $$\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}$$ y, de hecho, el término de error es menor que 1/2. Por lo que la suma es el entero más cercano a la serie $$\tag{7}\label{7}\frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}=\frac{N(N\sqrt{2}+\sqrt{2}-1)}{2}$$.

Pero la prueba podría requerir más agradable aproximación que sólo la equidistribución de la secuencia. (Y parece aún más rápida decadencia del término de error!!)

++Agregado)))

Lo que siempre es cierto en la discusión anterior es $\eqref{3}$ o el equivalente a la forma $\eqref{4}$. Así que exactamente se puede averiguar el valor promedio de la Beatty secuencia de $\sqrt{2}$, es decir, la división de $\eqref{1}$$N$.

Sin embargo, para el cálculo exacto del valor de la suma de $\eqref{1}$, necesitamos más precisa aproximación en el término de error como $\eqref{5}$ o $\eqref{6}$. Por desgracia, $\eqref{5}$ no es cierto y así es $\eqref{7}$.

Creo que lo mejor que podemos hacer es lo siguiente: Para cualquier irracional $\gamma$, vamos a $L(\gamma)=1-|1-2<\gamma>|$. Entonces tenemos $$\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)}$$ con $c$ una constante irrelevante a $\gamma$ y $N$($c=2$ realmente funciona)

Esto, en esencia, afirma que la aleatoriedad de la distribución de la secuencia de $\{<n\gamma>\}$ $[0,1)$ depende de qué tan cerca $<\gamma>$ $0$ o $1$(tenga en cuenta que $L(\gamma)/2$ es la distancia mínima de$<\gamma>$$0$$1$. Por supuesto, esto es realmente un ingenuo aproximación, de ser necesario ajustar de muchas maneras.