Cómo encontrar la suma de todos los factores de un entero positivo cuyos factores son conocidos

Answer 1

Supongamos que tienes el número

[matemáticas] n = a ^ {\ alpha} b ^ {\ beta} c ^ {\ gamma}… [/ matemáticas]

Aquí, a, b, c, … son los factores primos de n. La suma de todos los factores de n se encontrará variando las potencias en a, b, c, …

Supongamos que [math] f (n) [/ math] representa la suma de todos los factores de n (incluido el número y 1).

Estoy haciendo la siguiente suposición sobre la fórmula para encontrar la suma (basada en la suma de la progresión geométrica):

[matemáticas] f (n) = (\ frac {a ^ {\ alpha + 1} – 1} {a – 1}) (\ frac {b ^ {\ beta + 1} – 1} {b – 1}) [/ matemáticas] [matemáticas] (\ frac {c ^ {\ gamma + 1} – 1} {c – 1})… [/ matemáticas]

Demostraremos que ese es el caso usando inducción.

El resultado es, por supuesto, trivial para probar si n tiene solo un factor primo. Supongamos que ya hemos establecido el resultado para

[matemáticas] n_k = a ^ {\ alpha} b ^ {\ beta} c ^ {\ gamma}… k ^ {\ kappa} [/ matemáticas]

Es decir,

[matemáticas] f (n_k) = (\ frac {a ^ {\ alpha + 1} – 1} {a – 1}) (\ frac {b ^ {\ beta + 1} – 1} {b – 1}) [/ matemáticas] [matemáticas] (\ frac {c ^ {\ gamma + 1} – 1} {c – 1})… (\ frac {k ^ {\ kappa + 1} – 1} {k – 1}) [/matemáticas]

Verificamos

[matemáticas] n_l = a ^ {\ alpha} b ^ {\ beta} c ^ {\ gamma}… k ^ {\ kappa} l ^ {\ lambda} [/ matemáticas]

Notamos eso

[matemáticas] f (n_ {l}) = f (n_ {k}) (l ^ 0 + l ^ 1 +… + l ^ {\ lambda}) = [/ matemáticas] [matemáticas] (\ frac {l ^ {\ lambda + 1} – 1} {l – 1}) f (k) [/ math].

Apliquemos esta fórmula al caso

[matemáticas] n = 12 = 2 ^ 2.3 ^ 1 [/ matemáticas]

[matemáticas] f (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 = [/ matemáticas] [matemáticas] \ frac {(2 ^ 3 – 1) (3 ^ 2 – 1)} {3 – 1} [/ matemáticas]

Answer 2

1. Escriba un método isFactor (x, n) que verifique si x es un factor de n.
2. Escriba un método para recorrer de x = 1 a n, y verifique si x es factor o no. Si es un factor, agregue este valor a un acumulador y al final del ciclo, devuelva este acumulador.

Aquí está el código en Scala:

def sumOfFactors (n: Int) = {
si (n <= 0) 0

@ annotation.tailrec
bucle def (x: Int, acc: Int): Int = {
si (x> n) acc

bucle else (x + 1, if (isFactor (x, n)) acc + x else acc)

}

bucle (1, 0)
}

def isFactor (x: Int, n: Int) = n% x == 0