Estoy tratando de encontrar buenas maneras de hacer frente a las sumas de la forma
Unesdoc.unesco.org unesdoc.unesco.org
$\sum_{k=1}^{N}k^j\varphi(k)$ Puede ser cualquier cosa pero estoy muy preocupado por los casos 0, 1 y 2.
$j$ Es la función totent de Euler.
¿Se puede hacer esto sin necesidad de calcular$\varphi(k)$ manualmente para cada paso de$k^j\varphi(k)$? ¿Hay alguna oportunidad de optimización? ¿Cualesquiera identidades que se aplican aquí pueden ayudar?
Para el caso j=0, se puede definir algunas auxiliar sumatorias para formular un algoritmo que se ejecuta en $O(n^{\frac{3}{4}})$ tiempo:
F(N) = cardinalidad{ a,b : 0 < a < b <= N }
R(N) = cardinalidad{ a,b : 0 < a < b <= N, mcd(a,b) = 1 }
Se puede ver que estamos buscando R(N) + 1. También, F(N) es $\dfrac{N(N-1)}{2}$.
Ahora veo algo bonito:
R$\left( \Big\lfloor\dfrac{N}{m}\Big\rfloor \right)$ = cardinalidad{ a,b : 0 < a < b <= N, mcd(a,b) = m }
Por qué? Esto es porque usted puede multiplicar cada coprime par de (a,b) por m.
Este hecho le permite escribir F en términos de R:
F(N) = $\displaystyle\sum_{m=1}^N{ R\left(\Big\lfloor\dfrac{N}{m}\Big\rfloor\right) } $
Ya que estamos mirando por R(N), podemos resolver para el primer término de la derecha de la sumación.
R(N) = F(N) - $\displaystyle\sum_{m=2}^N{ R\left(\Big\lfloor\dfrac{N}{m}\Big\rfloor\right) } $
Nota: esta propiedad interesante de la función floor aquí: $\Big\lfloor\dfrac{N}{m}\Big\rfloor$ permanecerá constante para un rango de m. Esto nos permite calcular la suma en trozos. ejemplo:
$\Big\lfloor\dfrac{1000}{m}\Big\rfloor$ es constante para m en el rango de [501,1000].
Usted debe ser capaz de calcular todos los valores de $\phi(1),\dots,\phi(N)$ simultáneamente en el tiempo $O(N\log\log N)$, suponiendo que se dispone de suficiente memoria.
Para ello, establecer una Criba de Eratóstenes-tipo de cálculo, pero en vez de sólo la grabación si cada número entero es primo o no, de mantener un seguimiento de cada paso en el tamiz que "cruza off" de un entero dado. El resultado es que se ha almacenado la lista de todos los números primos dividiendo $n$, para todos los $1\le n\le N$. (Puede modificar el tamiz para obtener la factorización completa, pero no es importante para este problema).
Una vez que este lista en el almacenamiento, se puede calcular todas las $\phi(n)$ por la fórmula $\phi(n)=n\prod_{p\mid n}(1-1/p)$. El número total de multiplicaciones es $\sum_{n\le N} \omega(n)$ donde $\omega(n)$ es el número de los distintos factores primos de a $n$; esta suma es conocido por ser $O(N\log\log N)$. (Estoy descuidadamente contar una multiplicación de dos números racionales como $1$ paso.)
Una configuración similar se permiten calcular los valores de cualquier multiplicativo de la función sobre un intervalo de tiempo no mucho más largo que la longitud del intervalo.
Andy ya se ha descrito bastante bien cómo calcular el $R_0$ en sublinear tiempo. Es importante memoize resultados ya calculados $R_j$ a fin de evitar la duplicación de los cálculos. Aquí hay una fórmula general para cualquier $j\geq0$:
$$R_j(n) = \sum\limits_{k=1}^n k^j \varphi(k) $$
$$S_j(n) = \sum\limits_{k=1}^n k^j$$ $$R_j(n) = S_{j+1}(n) - \sum\limits_{k=2}^n k^j R_j\left ( \left \lfloor \frac{n}{k} \right \rfloor \right )$$
Observe que $S_j$ es sólo un polinomio de grado $j+1$: $$S_1(n) = \frac{1}{2}n(n+1)$$ $$S_2(n) = \frac{1}{6}n(n+1)(2n+1)$$ $$S_3(n) = \frac{1}{4}n^2(n+1)^2$$
Tenga en cuenta que el interior de la suma puede ser calculado en $O(\sqrt{n})$ pasos (sin tomar en cuenta el cálculo de los valores de $R_j$ que se han calculado de todos modos) si tomamos $q=\lfloor \sqrt{n}\rfloor $:
$$\sum\limits_{k=2}^n k^j R_j\left ( \left \lfloor \frac{n}{k} \right \rfloor \right )$$ $$= \sum\limits_{k=2}^{\lfloor n/q \rfloor} k^j R_j\left ( \left \lfloor \frac{n}{k} \right \rfloor \right ) + \sum\limits_{m=1}^{q-1} \sum\limits_{k=\lfloor \frac{n}{m+1} \rfloor + 1}^{\lfloor \frac{n}{m} \rfloor} k^j R_j(m)$$ $$= \sum\limits_{k=2}^{\lfloor n/q \rfloor} (S_j(k) - S_j(k-1)) R_j\left ( \left \lfloor \frac{n}{k} \right \rfloor \right ) + \sum\limits_{m=1}^{q-1} \left ( S_j \left ( \left \lfloor \frac{n}{m} \right \rfloor \right ) - S_j \left ( \left \lfloor \frac{n}{m+1} \right \rfloor \right ) \right ) R_j(m)$$
En la respuesta por plamenko a Andy anteriormente, debemos tener cuidado de que R(n) no es lo mismo que $R_0(n)$. Yo realmente no entiendo por qué Andy no rango de su $(a,b)$$1\leq a\leq b\leq n$, en lugar de $a<b$. Si la tenía, su prueba se llevan a través de la misma, y la suma daría $F(n)=S_1(n)=n(n+1)/2$.
La prueba de principio establecido por Andy es válido para mayor $j$, sin embargo, con plamenko la notación y [cond] devolver 1 si cond es verdadera y 0 en caso contrario, si usted express $R_j(n)$ $$R_j(n)=\sum_{1\leq a\leq b\leq n} [gcd(a,b)=1] b^j,$$ a continuación, puede ver que, por el cambio de las variables de $a=mc,b=md$: $$R_j(\lfloor \frac nm\rfloor) = \sum_{1\leq c\leq d\leq \lfloor \frac nm\rfloor} [gcd(c,d)=1] d^j = \sum_{1\leq a\leq b\leq n} [gcd(a,b)=m] \frac{b^j}{m^j},$$ a partir de la cual, lo que se suma sobre todos los $m$, al igual que en la de Andy prueba, obtenemos: $$\sum_{m=1}^n m^j R_j(\lfloor \frac nm\rfloor) = R_j(n) + \sum_{m=2}^n m^j R_j(\lfloor \frac nm\rfloor) = \sum_{m=1}^n \sum_{1\leq a\leq b\leq n} [gcd(a,b)=m] b^j = \sum_{1\leq a\leq b\leq n} b^j$$ que en el final se resuelve a $\sum_{1\leq b\leq n} b^{j+1} = S_{j+1}(n).$ Lo que demuestra plamenko de la ecuación. El resto de plamenko la respuesta es invariable, y cosas muy útiles, de hecho!
En realidad tuve una idea diferente. El número de elementos en la secuencia Farey de orden$N$ es$1+\sum_{n=1}^N \phi(n)$. Y uno puede recursivamente construir toda la secuencia de Farey en orden (ver la primera ecuación mostrada). Así que incluso podría ser capaz de hacer esto a tiempo$O(N)$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
