Ayuda para la función Möbius

Question

Dado algún número entero aleatorio grande k, ¿cuánto tiempo se tardaría en determinar la primalidad de k, a continuación, para calcular mobius(k), y cuánto más tiempo se tardaría en factorizar k, a continuación, para calcular mobius(k). Vi alguna fórmula que tenía que ver con raíces primitivas para calcular mobius(k), pero no entiendo por qué funciona ni cómo o cuánto más rápido es, entonces digamos tratando de factorizar el entero k.

Answer 1

Tengo entendido que nadie conoce una forma de calcular $\mu(n)$ se garantiza que es mucho más rápido que la factorización completa $n$ en primos. Determinar la primalidad es mucho más rápido que factorizar, por lo tanto, más rápido que calcular $\mu$ .

Answer 2

Creo que la fórmula que buscas implica Sumas de Ramanujan donde $$c_q(n)= \sum_{a=1}_{(a,q)=1}^{q}e^{2\pi i\frac{a}{q}n} = \mu(n)$$ si $(n,q)=1$ donde $\mu(n)$ es tu función de Möbius. De hecho, he visto esto hoy y estaba pensando lo mismo; es un resultado interesante, pero ¿es más rápido para la prueba de primalidad? No sé, estamos buscando cosas de esta forma para llegar a la conjetura de Goldbach. Debería ser un comentario, pero no había forma de que el término suma fuera legible en forma de comentario.