## 1. Sums of divisors

Let integer n be factorized as

n = p1e1 * p2e2 * ... * pkek

then the sum of divisors of n is represented as the following formula,

σ(n) = a1 * a2 * ... * ak

where

 ak = pkek+1 - 1 ------------ pk - 1

Especially,

 pkek+1 - 1 = pkek + ... + pk2 + pk + 1 ------------ pk - 1

so if n=pe then

σ(n) = pe + ... + p2 + p + 1.

When we compute the sum of divisors during factorization of n,
this formula is more easy to handle. The algorithm is following,

1. Let w=1 (σ(n) is stored in w).
2. p=prmdiv(n)
3. If p|n then
w = w*p+1
n = n/p
4. If p does not divide n then terminate.
5. The value pe + ... + p2 + p + 1 is stored in w.
6. goto 2.

The value of σ(n) where n = p1e1 * p2e2 * ... * pkek
is calculated by the following procedure.

1. Let s=1 (σ(n) is stored in s).
2. Let p be the smallest divisor of n.
3. If p=1 then terminate.
4. repeat 1. through 4. of above procedure.
5. If the condition 3. is held, let
s = s * w.
6. goto 2.

The program is following.

```10   fnSigma(N)
20   local S,W,P
30   S=1
40   W=1:P=prmdiv(N)
50   if N@P=0 then W=W*P+1:N=N\P:goto 50 else S=S*W
60   if N>1 then 40 else return(S)
```

previous index next

E-mail : kc2h-msm@asahi-net.or.jp
Hisanori Mishima