¿Hay una fórmula para calcular la suma de todos los divisores adecuados de un número?

Question

No necesito enumerar todos divisores apropiados, sólo quiero obtener su suma. Porque para un pequeño número, comprobando todos divisores apropiados y agregar para arriba no son gran cosa. Sin embargo, para un gran número, esto funcionaría muy lento. ¿Alguna idea?

Gracias,
Chan Nguyen

Answer 1

Si es la facturización de $n$ $$n=\prod_k p_k^{a_k}$$ where the $p_k$ are the distinct prime factors and the $a_k$ are the positive integer exponents, the sum of all the positive integer factors is $%$ $\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right).$

Por ejemplo, la suma de todos los factores de $120=2^3\cdot3\cdot5$ es %#% $ #%

Por factores propios , restar el $$(1+2+2^2+2^3)(1+3)(1+5)=15\cdot4\cdot6=360.$ de esta suma. Esto puede o no puede ser más rápido, dependiendo de la cantidad y cómo recibirá la facturización primera, pero esta es la típica técnica para problemas del concurso de high School secundaria de este tipo.

Answer 2

Sólo porque es muy interesante:

De hecho, hay un (a menos conocida) fórmula recursiva para calcular el $\sigma(n)$, la suma de los divisores de a $n$.

$$\sigma(n) = \sigma(n-1) + \sigma(n-2) - \sigma(n-5) - \sigma(n-7) + \sigma(n-12) +\sigma(n-15) + ..$$ Aquí $1,2,5,7,...$ es la secuencia de generalizada números pentagonales $\frac{3n^2-n}{2}$ $n = 1,-1,2,-2,...$ y los signos son repeticiones de $1,1,-1,-1$. La suma continúa hasta que se intenta calcular el $\sigma$ de algo negativo. Sin embargo, si $\sigma(0)$ se produce en la suma (esto sucede precisamente cuando $n$ es un generalizada pentagonal número), debe ser reemplazado por $n$ sí. En otras palabras $$\sigma(n) = \sum_{i\in \mathbb Z_0} (-1)^i\left( \sigma(n - \tfrac{3i^2-i}{2}) + \delta(n,\tfrac{3i^2-i}{2}) \right),$$ donde pongamos $\sigma(i) = 0$ $i\leq 0$ $\delta(\cdot,\cdot)$ es la delta de Kronecker.

Tenga en cuenta que el cálculo de $\sigma(n)$ requiere $\sigma(n-1)$ ya, por tanto, su complejidad es, al menos,$\mathcal O(n)$, lo que la convierte en algo inútil para los propósitos prácticos. Nota, sin embargo la falta de referencia a la divisibilidad en esta fórmula, lo que hace que sea un poco milagroso y por lo tanto vale la pena mencionar.

Aquí's una referencia a la de Euler papel de 1751.

Answer 3

Si No = a ^ p × b ^ q x c ^ r ×... luego divisores total = (p + 1)(q + 1) (r + 1)...

suma de divisores = a^(p+1)/(a–1) × b^(q+1)/(b–1) × c^(r+1)/(c–1)

por ejemplo, los divisores de 8064 8064 = 2 ^ 7 × 3 ^ 2 × 7 ^ 1

número total de divisores = (7+1)(2+1)(1+1) = 48

suma de divisores = [2^(7+1) –1]/(2–1) × [3^(2+1) –1]/(3–1) × [7^(1+1) –1]/(7–1)

= 255 × 7 × 8 = 26520

Answer 4

Si quieres valores numéricos la calculadora en el sitio siguiente listará todos los divisores de un número entero positivo dado, el número de divisores y su suma. También tiene enlaces a calculadoras para otras funciones número de teoría como de la función φ de Euler.

http://www.javascripter.net/Math/Calculators/divisorscalculator.htm

Answer 5

público int divisorSum (int n) {int suma = 0; para (int i = 1; i < = n; i ++) {si (n % i == 0) {suma += i; }} return suma; }