La función SOD (n) es la suma de divisores de un número entero n. Por ejemplo, SOD (24) = 2 + 3 + 4 + 6 + 8 + 12 = 35. La función CSOD (n) es la SOD acumulativa de un número entero n. ¿Cómo calculo CSOD (n)?

Bueno, intentaré la siguiente solución rápida y sucia que puede mejorarse. Además, espero que este problema no sea parte de algún concurso una vez más.

Estamos tratando de calcular [math] \ mathrm {CSOD} (n) [/ math].

Los divisores de números [matemáticos] \ leq n [/ matemáticos] adecuados ([matemática] \ neq 1 [/ matemática]) están en el rango [matemática] 2, \ ldots \ lfloor \ frac {n} {2} \ rfloor [ /matemáticas].

¿Cuántos [matemática] 2 [/ matemática] hay entre divisores? Aproximadamente la mitad de los números.

Para ser más precisos, su suma es [math] 2 \ lfloor \ frac {n} {2} \ rfloor -2. [/ Math] (Restamos 2 ya que 2 no es un divisor propio del número 2)

Por la lógica similar, la suma de todos los divisores [matemática] s [/ matemática] en estos números
es [math] s \ lfloor \ frac {n} {s} \ rfloor -s. [/ math]

Ahora observe que [math] n – s \ lfloor \ frac {n} {s} \ rfloor = r_s, [/ math] donde [math] r_s [/ math] es el resto de la división de [math] n [/ math ] por [matemáticas] s. [/ matemáticas]

Deje [math] m = \ lfloor \ frac {n} {2} \ rfloor [/ math].

Luego, al sumar todos los divisores se obtiene [math] \ displaystyle n (m-1) – \ sum_ {k = 2} ^ {m} k – \ sum_ {k = 2} ^ {m} r_k = [/ math] [math] n \ cdot (m-1) – \ frac {(m + 2) (m-1)} {2} – \ sum_ {k = 2} ^ {m} r_k. [/ math]

La parte más fea es el cálculo de [matemáticas] \ sum_ {k = 2} ^ {m} r_k [/ matemáticas]; el cálculo directo de esto requiere operaciones aritméticas [math] \ mathcal {O} (n) [/ math].

Ejemplo: [matemáticas] n = 10 [/ matemáticas]. Entonces [matemáticas] m = 5 [/ matemáticas].

Por algún abuso de notación denotar división descansa por [math] \ mathrm {mod} [/ math]

[matemáticas] \ mathrm {CSOD} (10) = 10 \ cdot 4 – \ frac {7 \ cdot 4} {2} – 10 \ mod 2 -10 \ mod 3 – 10 \ mod 4 – 10 \ mod 5 = 40 -14-3 = 23. [/ Matemáticas]

Así que redujimos el problema a un cálculo eficiente de [math] \ sum_ {k = 2} ^ {m} r_k [/ math].

Creo que el algoritmo directo puede mejorarse ligeramente.

Por ejemplo, si sé que [matemática] n \ mod 100 = r [/ matemática] entonces usando esta [matemática] r [/ matemática] puedo reemplazar [matemática] n \ mod d [/ matemática] por [matemática] r \ mod d [/ math] para cada [math] d [/ math] que es un divisor de [math] 100 [/ math].

La función de suma de divisores normal [matemática] d (n) [/ matemática] es igual a su función SOD, más 1 y n.

La suma [matemática] D (n) = \ sum_ {i = 1} ^ {n} d (i) [/ matemática] puede calcularse eficientemente al reconocer que es el número de puntos de la red debajo de la hipérbola [matemática] xy = n [/ math], entonces si [math] u = \ lfloor \ sqrt {n} \ rfloor [/ math],

[matemáticas] D (n) = 2 \ sum_ {i = 1} ^ {u} \ lfloor n / i \ rfloor – u ^ 2 [/ math]

(Ver la función sumatoria del divisor).

Ahora, solo necesita tomar [matemática] D (n) [/ matemática] y restar [matemática] \ sum_ {i = 1} ^ {n} 1 [/ matemática] y [matemática] \ sum_ {i = 1 } ^ {n} i [/ math], los cuales tienen formas cerradas simples. 🙂