De manera eficiente las pruebas si sigma(n) = m

Question

Estoy tratando de escribir una función que resuelve eficientemente este problema:

Dado enteros positivos m y n, determinar si $\sigma(n)=m$.

Por supuesto, estoy buscando para una rápida técnica de "factor de n, determinar sigma(n), y comprobar si las dos son iguales" o que no me han publicado aquí. Mi idea básica es encontrar pequeños factores de n (o su ausencia) y en cortocircuito si no factorización de la parte restante daría m.

Otras pruebas, como la necesidad de que $n$ ser un cuadrado o dos veces a la plaza de la si $m$ es impar, vienen a la mente.

Otras ideas, o pensamientos en cuanto a la forma de implementar esto? Si $m/n$ es muy grande puede ser descalificado por comparación con una lista de la sobreabundancia de los números y su abundancies, pero si es dentro de la gama posible yo tendría que encontrar algún modo equivalente a descalificar a los números que no tienen factores por debajo de un cierto límite de L a que he probado, y no está claro cómo hacerlo.

(Por supuesto, si soy lo suficientemente afortunado como para encontrar un componente $p^a\parallel n$ $\sigma(p^a)\nmid m$ estoy hecho, pero también muchos números no tienen ninguna pequeños factores que depender de encontrar esto en todos los casos).

Answer 1

Ha sido un tiempo desde que jugó con esto cuando se busca amistoso para los números, pero aquí están algunas sugerencias.

EDIT: Viendo la otra respuesta, parece que debo mencionar que $\sigma$ es multiplicativo, es decir, si $n=\prod_i p_i^{e_i}$$\sigma(n) = \prod_i (p_i^{e_i+1}-1)/(p-1)$, esto es necesario para el siguiente.

Suponiendo que tenemos una tabla de números primos ejecutar a través de los números primos hasta encontrar un factor de $n$, y actuar en consecuencia. Usted sólo necesita los números primos hasta alrededor de $n^{1/3}$.

1. Mientras se ejecuta a través de la pequeña los factores primos de n, digamos que encuentra que $p^e | n$ comprobar que $\sigma(p^e) | m$. (Es probablemente la mejor manera de dividir a cabo y comprobar que $\sigma(n/p^e) = m/\sigma(p^e)$ (obviously not bothering with primes smaller than $p$ en adelante). Esto tiende a corto el circuito de la computación muy rápidamente.

2. Obviamente corto circuito al $n>m$. Esta es la razón por la divisoria de los factores de $p^e$ $\sigma(p^e)$ es útil. En mi experiencia los pasos 1 y 2 son los más poderosos. También prueba si $n+1=m$ $n$ prime.

3. Si usted está en una buena cantidad de p que usted sabe que sólo puede haber dos factores primos, se resuelve la ecuación cuadrática resultante de $n = pq$, $m=(p+1)(q+1)$, por lo $n-m+1=p+q$, por lo que p y q son las raíces de $x^2 + (m-n-1) x + n$ (revisar mi álgebra). (también es necesario comprobar si $n = p^2$ y $m = p^2+p+1$, pero esto es fácil como $p=m-n-1$.

4. Muy de vez en cuando (decir siempre $p$ pasa $2^k$$k>10$) comprobar si $\sigma(n)$ debe ser menor que $m$, asumiendo que el resto de los factores de $n$ son distintos los factores de tamaño de $p$. Esto se pone complicado, y me olvido de los detalles. La idea viene de H. J. J. TeRiele de 1986 amistoso par de papel en Matemáticas Comp. Esencialmente, si $n=p^k q$ $m < (p+1)^k (q+1)$ con $p<q<p^2$ ($q$ no necesariamente entero)[*]

5. Si usted ha tratado con el primer par, y usted debe hacer que la primera, entonces vale la pena el manejo del caso de la extraña $m$ por separado (esta es otra razón para dividir $\sigma(p^e)$ como se encuentran. A la hora de dividir los pequeños primos de las potencias de 2 en $m$ desaparecen con bastante rapidez.
6. Una cosa más (una combinación de 2 y 3) si $m<n+n^{2/3}+n^{1/3}+1$ $n$ debe tener uno o dos factores primos, y se puede aplicar 3.

[*] Este no es demasiado complicado, después de todo. Si $p$ es un primer factor de $n$ más que puede contribuir a $\sigma(n)/n$$(p+1)/p$, así que si queremos un límite máximo valor posible de $\sigma(n)$ que $n$ no tiene ningún factor primo más pequeño que $p$, e $n$ $k$ factores primos, se puede utilizar el máximo de $\prod_i (p_i+1)$ limitado por $\prod_i p_i = n$ $p_i>p$ . Este es un multiplicador de Lagrange problema, y es fácil ver que es maximizado en el límite y el valor máximo es de $(p+1)^{k-1} (q+1)$, y si tenemos que maximizar esta con respecto a $k$ vemos que debemos elegir $k$ a ser tan grande como sea posible, tales que $q>p$.

Answer 2

Usted podría tratar de un tamiz. La más simple que viene a la mente es la creación de una lista de 1 a algún número n, donde al principio de cada elemento de la lista tiene el valor 1; de bucle a través de la lista añadiendo continuamente el número actual está en sus múltiplos hasta llegar al final de la lista. Aquí está el código (en C++):

int n = 1000000; // limit of the sieve
vector <int> sigma(n+1,1);
for(int i = 2;i <= n; i++)
    for(int j = i;j <= n;j += i)
        sigma[j] += i;

Answer 3

Bach, Miller y Shallit mostraron que dada $\sigma(n)$ y n puede n de factor aleatorio polinomio de tiempo, que puede ser utilizado para lo que usted desea. El papel es de una suma de Divisores, Perfecto Números y Factoring.