Suma de una función

Question

Dejemos que $n$ es un número entero positivo.

$n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ es la factorización primaria completa de $n$ .

Permítanme definir una función $f(n)$

$f(n) = p_1^{c_1}p_2^{c_2}...p_k^{c_k}$ donde $c_k = e_k$ si $e_k$ es divisible por $p_k$ Si no es así $c_k = e_k - 1$

Ejemplo:

$72 = 2^33^2$ Así que $f(72) = 2^{3-1}3^{2-1} = 2^{2}3^{1}=12$

$144 = 2^43^2$ Así que $f(144) = 2^{4}3^{2-1} = 2^{4}3^{1}=48$ , como $4$ es divisible por $2$ , exponente de $2$ sigue siendo el mismo.

Ahora dejemos que $$F(N) = \sum_{n=2}^N f(n)$$

Ejemplo: $F(10) = 1 + 1 + 4 + 1 + 1 + 1 + 4 + 3 + 1 = 17$

Ahora quiero evaluar $F(N)$ para un valor bastante grande de $N$ , digamos que $10^{12}$ . ¿Puedo hacerlo sin factorizar cada número?

Answer 1

Lo principal a tener en cuenta es que esta función sobre la que estás sumando es $1$ para los números sin cuadrado. Así que empieza con una suma de $N-1$ (añadiendo $1$ para cada número de $2$ a $N$ ), y ya casi has terminado.

Esto resuelve el problema de tener que conocer los primos hasta $N$ - ahora sólo tenemos que tratar con primos hasta $\sqrt N$ .

También hay que tener en cuenta que $p^p$ superará rápidamente $N$ por ejemplo, para su $N=10^{12}$ lo hace más allá de $p=11$ para no tener que lidiar con muchos casos de excepción de divisibilidad.

El resto es sólo contabilidad y, como tus etiquetas sugieren correctamente, inclusión-exclusión - puede haber algunos buenos trucos para ahorrar algunos cálculos, pero si no encuentras ninguno, debería ser lo suficientemente rápido para hacer inclusión-exclusión por fuerza bruta con las condiciones de ser divisible por al menos segundas potencias de los primos hasta $\sqrt N$ ya que no son muchos los que pueden ocurrir sin exceder $N$ .