Resolver la suma $\sum_{i=1}^n \lfloor e\cdot i \rfloor $

Question

Cómo resolver $$\sum_{i=1}^n \lfloor e\cdot i \rfloor $$ Para un determinado $n$ .

Por ejemplo, si $n=3$ entonces la respuesta es $15$ y se puede hacer a mano. Pero para $n$ (Por ejemplo $10^{1000}$ ) se complica . ¿Hay alguna forma de calcular esta suma?

Answer 1

A continuación se presentan tres posibles ideas, las dos primeras no son tan satisfactorias.
La tercera es una modificación de las segundas ideas que podría funcionar.
Espero que puedan inspirar a otros a crear algo que sea útil.

Como serie de Fourier

En primer lugar, podemos reescribir $\lfloor x \rfloor$ como una serie de Fourier.

$$\lfloor x \rfloor = x - \{ x \} = x - \frac12 + \sum_{m=1}^\infty \frac{\sin(2\pi m x)}{\pi m}\tag{*1}$$

Dado que las discontinuidades de $\lfloor x \rfloor$ se encuentra dentro de $\mathbb{Z} \subset \mathbb{Q}$ . la función suelo es continua en irracional $x$ . Como resultado, RHS de $(*1)$ converge puntualmente a LHS para irracional $x$ .

Sustituir $x$ por $ek$ para $k = 1, \ldots, n$ y sumar sobre $k$ obtenemos.

$$\sum_{k=1}^n \lfloor ek \rfloor = \frac{e}{2}n(n+1) - \frac{n}{2} + \underbrace{\frac{1}{2\pi}\sum_{m=1}^\infty \frac{\cos(\pi m e) - \cos(\pi m e(2n+1))}{m\sin(\pi m e)}}_{I} $$ En principio, si podemos aproximar la serie $I$ en RHS lo suficientemente preciso, podemos redondear el RHS al entero más cercano y nos dará el valor de LHS. El problema es cuando aproximamos $I$ por sus sumas parciales, el $\sin(m \pi e)$ factor en el denominador hacen que sea muy difícil calcular el número correcto de términos que hay que mantener.

Evaluación recursiva

Si no insistimos en una fórmula cerrada, es posible evaluar la suma de forma recursiva.
Para $\alpha \in (1,\infty)\setminus \mathbb{Q}$ y $n \in \mathbb{Z}$ define $\displaystyle\;S(\alpha,n) \stackrel{def}{=} \sum_{k=1}^n\lfloor \alpha k \rfloor$ . La suma que queremos es $S(e,n)$ .

Hay dos ramas en la recursión:

• Caso I - $\alpha > 2$ .

  Vuelva a escribir $\alpha$ como $\beta + m$ donde $\beta \in (1,2)$ y $m = \lfloor \alpha - 1\rfloor$ tenemos $$S(\alpha,n) = \sum_{k=1}^n \left( mk + \lfloor \beta k\rfloor\right) = \frac{m}{2}n(n+1) + S(\beta,n)$$

• Caso II - $\alpha < 2$ .

  Sea $\beta = \frac{\alpha}{\alpha-1} \in (2,\infty) \setminus \mathbb{Q}$ , tenemos $$S(\alpha,n) = \sum_{k=1}^n \lfloor\alpha k\rfloor = \sum_{0 < \alpha k \le \alpha n} \lfloor\alpha k\rfloor = \sum_{0 < \alpha k < \lceil\alpha n\rceil} \lfloor\alpha k\rfloor\tag{*2} $$ Para cualquier $r \in (0,\infty) \setminus \mathbb{Q}$ secuencias de la forma $\left( \lfloor r k \rfloor \right)_{k\in\mathbb{Z}_{+}}$ se conocen como Secuencia Beatty .
  Desde $\frac{1}{\alpha} + \frac{1}{\beta} = 1$ las dos secuencias de Beatty $\left( \lfloor \alpha k\rfloor \right)_k$ y $\left( \lfloor \beta k\rfloor \right)_k$ son complementarios. Cada número entero positivo pertenece exactamente a una de estas dos secuencias. Como corolario, para cualquier $N \in \mathbb{Z}_{+}$ tenemos $$\sum_{0 < \alpha k < N} \lfloor \alpha k\rfloor + \sum_{0 < \beta k < N}\lfloor \beta k \rfloor = \frac12 N(N-1)$$

  Aplíquelo a $(*2)$ obtenemos $$S(\alpha,n) = \frac12\lfloor \alpha n\rfloor\lceil \alpha n\rceil - S\left( \beta, \left\lfloor \frac{1}{\beta}\lceil \alpha n\rceil\right\rfloor\right)$$

Combinando estas dos ramas, podemos evaluar $S(\alpha,n)$ recursivamente.

Resulta que un pregunta acerca de $\sum_{k=1}^n \lfloor \sqrt{2} k \rfloor$ se ha preguntado antes. En un responder por @merico, hay otra derivación de la fórmula de recurrencia en una forma ligeramente diferente. Comparando nuestras respuestas, observo que el término $\left\lfloor \frac{1}{\beta}\lceil \alpha n\rceil\right\rfloor$ aquí se puede simplificar a $\lfloor (\alpha-1)n\rfloor$ .

Dado que la recursión es una recursión de cola, podemos acelerar la implementación de $S(\alpha,n)$ desenrollando la recursividad. A continuación se muestra mi implementación de $S(\alpha,n)$ en el CAS máxima .

S(a0,n0) := block(
    [sum:0,sign:1,a:a0,n:n0,m],
    while (n > 0) do
        if( a > 2 ) then 
        (
            m : floor(a-1),
            sum : sum + sign*m*n*(n+1)/2,
            a : a - m
        ) else
        (
            m    : floor(a*n),
            sum  : sum + sign*m*(m+1)/2,
            sign : -sign,
            a    : a/(a-1),
            n    : m-n
        ),
    sum
);

Mediante el comando S(bfloat(%e),10^9) en máximos con $100$ precisión de los dígitos, el código anterior evalúa la suma $S(e,10^9)$ en $44$ pasos y retornos $$S(e,10^9) = 1359140915088663532$$

Como doble comprobación, podemos comparar este valor con la aproximación $$S_{appx}(\alpha,n) = \frac{\alpha}{2}n(n+1) - \frac{n}{2}$$ Desde $S_{appx}(e,10^9) \approx 1359140915088663531.9\ldots$ por encima del valor de $S(e,10^9)$ debería ser correcta.

El problema básico de este enfoque es cuando $n$ es grande, necesitamos un valor muy preciso de $e$ como una semilla. También necesitamos mantener la precisión durante todo el cálculo. Por ejemplo, si calculamos el número utilizando la precisión por defecto en máximos, el comando S(%e,10^9),numer devuelve un número equivocado $1359140915088663452$ . Si sólo utilizamos el S(bfloat(%e),10^9) sin aumentar la precisión, obtenemos otro número erróneo $1359140915088663538$ .

¿Algo que debería funcionar?

Inspirada en la obra de Jack D'Aurizio responder a otra variante de esta pregunta, investigué si se puede sustituir $e$ por uno de sus convergentes como entrada a $S(\alpha,n)$ . Parece que funciona.

Las ideas básicas son las siguientes.

Para cualquier $\alpha \in (1,\infty)\setminus\mathbb{Q}$ Consideremos su representación como CF (fracción continua):

$$\alpha = [a_0; a_1, a_2, \ldots ]$$

Sea $\displaystyle\;\frac{p_k}{q_k} = [a_0;a_1,\ldots, a_k]\;$ sea el $k^{th}$ convergente de $\alpha$ . Una propiedad del convergente es $$\left| \alpha - \frac{p_k}{q_k} \right| < \frac{1}{q_k^2}$$ De este modo, se puede demostrar que $\displaystyle\;\left\lfloor \frac{p_k}{q_k} n \right\rfloor = \lfloor \alpha n\rfloor$ para todos $n < q_k$ .

Cuando alimentamos $\displaystyle\;\frac{p_k}{q_k} = [ a_0, a_1, a_2, \ldots, a_k ]\;$ como entrada para la aplicación anterior de $S(\alpha,n)$ las variables se actualizarán de la siguiente manera.

$$\overbrace{\begin{align} \alpha &\leftarrow [1; a_1, a_2, \ldots, a_k ]\\ n &\leftarrow n \end{align}}^{\alpha > 2} \quad\text{ and }\quad \overbrace{\begin{align} \alpha &\leftarrow [ 1 + a_1; a_2, \ldots, a_k ]\\ n &\leftarrow \left\lfloor\frac{n}{ [ a_0 - 1; a_2, \ldots, a_k]} \right\rfloor \end{align}}^{\alpha < 2} $$

Si se siguen los pasos del bucle while, las variables se transformarán en esencialmente el mismo patrón.

Todas las CF finitas que aparecen durante este proceso son convergentes de las CF correspondientes asociadas a $\alpha$ . Si el denominador de todos estos CF finitos es mayor que el $n$ ven en un paso, producirán el mismo resultado que si $\alpha$ es la entrada.

En resumen, si se alimenta un convergente de orden suficientemente alto de $\alpha$ a la aplicación anterior de $S(\alpha,n)$ se obtiene el mismo resultado. La ventaja de este enfoque es que estaremos usando aritmética exacta de números racionales y ya no tenemos que preocuparnos por el error numérico.

Para el problema que nos ocupa, si se quiere calcular $S(e,n)$ para un gran $n$ , podemos estimar el orden de convergencia requerido de $e$ como sigue.

Encuentre el primer $\ell$ tal que $2^\ell \ell! > n$ y, a continuación, establezca $k = 3\ell$ . Para $n \approx 10^{4000}$ , $k \approx 4011$ debería ser suficiente.

En mi PC, puedo calcular $S(e,10^{4000})$ utilizando máximos en menos de un minuto. Sin embargo, tengo que admitir que no tengo manera de verificar que tengo la respuesta correcta.

Answer 2

Hagamos una aproximación $e$ por un número racional $A$ tal que tenemos un número entero positivo $k$ tal que $10^kA$ es un número entero (por ejemplo, $A=2.71$ avec $k=2$ ).

Podemos entonces utilizar el hecho de que $\lfloor (m\cdot10^k+i)A \rfloor = m\cdot 10^k A+\lfloor Ai \rfloor$ para cualquier número entero positivo $m$ .

Entonces, para un número entero positivo $r$ , $$ \large \sum_{i=1}^{r \cdot 10^k} \lfloor Ai \rfloor = r \sum_{i=1}^{10^k} \lfloor Ai \rfloor +\frac{r(r-1)}{2}10^{2k}A.$$

Dado que la suma es una función no decreciente de $A$ podemos acotar la suma deseada con dos aproximaciones racionales de $e$ uno grande y otro más pequeño.

Por ejemplo, con $A=2.71828$ y $A=2.71829$ (y $k=5$ , $r=10^4$ ) podemos encontrar que $$ 1359140000859160000 < \sum_{i=1}^{10^9} \lfloor ei \rfloor < 1359145000859150000 $$ Con $A=2.7182818$ y $A=2.7182819$ (y $k=7$ , $r=10^2$ ) encontramos que $$ 1359140900859141000 <\sum_{i=1}^{10^9} \lfloor ei \rfloor < 1359140950859140900.$$ Utilizando mejores aproximaciones, podemos obtener límites más estrictos.

Answer 3

descargo de responsabilidad: Esta no es una respuesta completa, sólo una aproximación que se me ocurrió y que era demasiado larga para comentarla.

Si truncamos $e $ en $3$ decimales (por lo que es 2,718), podemos obtener una aproximación decente:

$$\sum_{i=1}^n \lfloor 2.718i \rfloor \approx \frac32 (n(n+1) - \lfloor \frac{n}3 \rfloor ( \lfloor \frac{n}3 \rfloor + 1)) + \frac12 \lfloor \frac{n}4 \rfloor ( \lfloor \frac{n}4 \rfloor + 1) = f(n)$$

Utilicé el programa proporcionado en los comentarios para comparar las respuestas de $n = 542$ (Lo sé, no es muy grande, pero el programa se me acabó ahí).

$$\sum_{k=1}^{542} \lfloor ei \rfloor = 399,732$$

$$f(542) = 401,769$$

Para que el error sea aproximadamente $0.51$ %

A partir de aquí, se podría encontrar numéricamente una aproximación para el error en función de $n$ , digamos $\delta(n)$ y una aproximación mucho mejor para valores grandes sería $f(n) - \delta(n) $

Nunca encontrarás una respuesta exacta de esta manera, pero si sólo tienes curiosidad en el valor la suma toma para grandes $n$ Esta podría ser una buena manera de obtener una buena aproximación (podría ser difícil para un código calcular un valor exacto de sumas muy grandes). $n $ )