The sum of divisors#1782

The sum of divisors (Editorial)

Consider the function $σ (n)$ , which maps a positive integer $n$ to the sum of all its positive divisors.

If $n = p$ n = p, where $p$ is a prime number, then $n$ has exactly two divisors: $1$ and $p$ . Therefore,

σ (n) = 1 + p

σ(n) = 1 + p

If $n = p^{a}$ n = p^a, where $p$ is a prime number and $a \geq 1$ a \ge 1, then all divisors of $n$ are of the form:

1, p, p^{2}, ..., p^{a}

1, p, p^2, ..., p^a

Their sum forms a geometric progression; therefore,

σ (p^{a}) = 1 + p + p^{2} + p^{3} + ... + p^{a} = \frac{p ^{a + 1} - 1}{p - 1}

σ(p^a) = 1 + p + p^2 + p^3 + ... + p^a = \frac{p^{a+1} - 1}{p - 1}

The function $σ (n)$ is multiplicative, that is, for any pair of coprime integers $x$ and $y$ , the following equality holds:

σ (x y) = σ (x) σ (y)

σ(xy) = σ(x) σ(y)

Let a positive integer $n$ have the following prime factorization

n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}},

n = p_1^{a_1} p_2^{a_2}...p_k^{a_k},

where $p_{1}, p_{2}, ..., p_{k}$ p_1, p_2, ..., p_k are distinct prime numbers.

Then, using the multiplicativity of $σ (n)$ and the formula for powers of prime numbers, we obtain:

σ (n) = σ (p_{1}^{a_{1}}) \cdot σ (p_{2}^{a_{2}}) \cdot ... \cdot σ (p_{k}^{a_{k}}) = \frac{p _{1}^{a_{1} + 1} - 1}{p _{1} - 1} \cdot \frac{p _{2}^{a_{2} + 1} - 1}{p _{2} - 1} \cdot ... \cdot \frac{p _{k}^{a_{k} + 1} - 1}{p _{k} - 1}

σ(n) = σ(p_1^{a_1}) \cdot σ(p_2^{a_2}) \cdot ... \cdot σ(p_k^{a_k}) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdot ... \cdot \frac{p_k^{a_k+1}-1}{p_k-1}

The above sum can also be written in the following form:

σ (n) = i = 1 \prod k \frac{p _{i}^{a_{i} + 1} - 1}{p _{i} - 1} = i = 1 \prod k (1 + p_{i} + p_{i}^{2} + \dots + p_{i}^{a_{i}}) = i = 1 \prod k j = 0 \sum a_{i} p_{i}^{j} .

\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1} = \prod_{i=1}^{k} \left( 1 + p_i + p_i^2 + \dots + p_i^{a_i} \right) = \prod_{i=1}^{k} \sum_{j=0}^{a_i} p_i^{\,j}.

Example

The number $n = 239$ n = 239 is prime, that is, it has exactly two positive divisors: $1$ and $239$ . By the definition of the sum-of-divisors function, we obtain:

σ (239) = 1 + 239 = 240

σ(239) = 1 + 239 = 240

Consider the number $n = 24$ n = 24. Its prime factorization is:

24 = 2^{3} \cdot 3

24 = 2^3 \cdot 3

Since the numbers $2^{3}$ 2^3 and $3$ are coprime, we can apply the multiplicativity of the function $σ (n)$ :

σ (24) = σ (2^{3}) \cdot σ (3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

σ(24) = σ(2^3) \cdot σ(3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

Let's compute the sum of the divisors of the number $n = 24$ n = 24 directly. First, list all positive divisors of $24$ :

1, 2, 3, 4, 6, 8, 12, 24

1, 2, 3, 4, 6, 8, 12, 24

Adding them together, we obtain:

σ (24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24

σ(24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24

Notice that all divisors can be grouped in the following way:

σ (24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

σ(24) = \\ 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = \\ 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = \\ (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

Algorithm implementation

Read the input value $n$ .

scanf("%lld",&n);

Store the value of $σ (n)$ in the variable $r es$ .

res = 1;

Using the variable $i$ , iterate over all prime divisors of the number $n$ (according to the problem statement, they do not exceed $1000$ ). For each such divisor, compute its contribution to the sum of divisors of $n$ using the formula derived in the problem analysis.

for (i = 2; i <= 1000; i++)
{
  p = i;

Let $i$ be a prime divisor of n. Find the largest exponent $a$ such that $i^{a}$ i^a divides $n$ .

  while(n % i == 0)
  {
    n /= i; 
    p *= i;
  }

After the loop terminates, we obtain $p = i^{a + 1}$ p = i^{a+1}. Then we multiply the current value of the variable $r es$ by $\frac{i ^{a + 1} - 1}{i - 1}$ \frac{i^{a + 1} - 1}{i - 1}.

  res *= (p - 1) / (i - 1);
}

Print the answer.

printf("%lld\n",res);

Java implementation

import java.util.*;

class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long res = 1;
    for(int i = 2; i <= 1000; i++)
    {
      long p = i;
      while(n % i == 0)
      {
        n /= i; 
        p *= i;
      }
      res *= (p - 1) / (i - 1);
    }

    System.out.println(res);
    con.close();
  }
}

Java

Python implementation

Read the input value $n$ .

n = int(input())

Store the value of $σ (n)$ in the variable $r es$ .

res = 1

for i in range (2,1000) :
  p = i

Let $i$ be a prime divisor of n. Find the largest exponent $a$ such that $i^{a}$ i^a divides $n$ .

  while(n % i == 0) :
    n = n // i 
    p *= i

After the loop terminates, we obtain $p = i^{a + 1}$ p = i^{a+1}. Then we multiply the current value of the variable $r es$ by $\frac{i ^{a + 1} - 1}{i - 1}$ \frac{i^{a + 1} - 1}{i - 1}.

  res *= (p - 1) // (i - 1)

Print the answer.

print(res)