Pythonによる約数の個数と合計の計算

約数のリストを作成し、その個数、数量を計算する

約数のリストで求める関数

pythonで正の整数の約数をリストで求めるプログラムを作成し、このリストから約数の個数と合計を計算します。リストの使い途は集計だけなので並べ替えはせず、効率的に計算する方法を考えます。

約数を効果的に計算しリストで返す
  1. def divisor_list(num):
  2. divisors = []
  3. for i in range(1, int(num**0.5)+1):
  4. if num % i == 0:
  5. divisors.append(i)
  6. if i**2 == num:
  7. continue
  8. divisors.append(int(num/i))
  9. return divisors
  11. d = divisor_list(1200)
  12. print(d)
  13. print(f'個数：{len(d)} 合計：{sum(d)}')

[1, 1200, 2, 600, 3, 400, 4, 300, 5, 240, 6, 200, 8, 150, 10, 120, 
12, 100, 15, 80, 16, 75, 20, 60, 24, 50, 25, 48, 30, 40]
個数：30  合計：3844

作成したリストに対しlen関数で個数を、sum関数で合計を計算することができます。

個数と合計を集計する

前節のプログラムを、個数と数量をタプルで返す関数に変更します。

cnt
約数の個数をカウントします。
sigma
約数の合計を足しこんでいきます。
約数のリストを作成する
  1. def divisor_cs(num):
  2. cnt = 0
  3. sigma = 0
  4. for i in range(1, int(num**0.5)+1):
  5. if num % i == 0:
  6. cnt += 1
  7. sigma += i
  8. if i**2 == num:
  9. continue
  10. cnt +=1
  11. sigma+=(int(num/i))
  12. return cnt,sigma
  14. cnt,sigma=divisor_cs(1200)
  15. print(f'個数：{cnt} 合計：{sigma}')

個数：30  合計：3844
6.7.10.11. 約数が見つかったら、リストを追加する代わりに個数cnt、数量sigmaを足しこんでいきます。
12. この関数のように返り値を複数にすると、タプルになります。このため、14.では、cntとsigmaをアンパックして受け取ります。

divisor_cs関数は引数として指定した正の整数の約数の個数と合計をタプルで返しますが、合計だけを知りたいときには個数に当たる部分の変数の名前をいちいち考えて指定するのは思いのほか負担になります。このような場合、不要な変数は_で受けることができます。

約数の合計だけを計算
  1. _ ,sigma =divisor_cs(36)
  2. sigma

3844

素因数分解の結果から約数の個数と合計を計算する

正の整数の約数の個数や合計を計算する際に、素因数分解の結果を利用することができます。

素因数分解をする関数

前提として、素因数分解をする関数を作成します。

約数を辞書形式で返す関数
  1. def factorint(num):
  2. factor={}
  3. prime = 2
  4. while(prime <= num):
  5. expon=0
  6. while(num % prime == 0):
  7. expon+=1
  8. num //= prime
  9. if expon != 0:
  10. factor[prime]=expon
  11. prime += 1
  12. return factor
  14. factorint(1200)

{2: 4, 3: 1, 5: 2}

上記の通り、$1,200=2^4\times3^1\times5^2$のように、素因数をkey、べき乗をvalueとする辞書形式で返します。

素因数分解の結果から約数の個数と合計を計算する

約数の個数を計算する

約数の個数は、素因数分解$N=p^aq^br^c \cdots$の結果から計算することができます。

$N=(a+1)(b+1)(c+1) \cdots$

約数においてpのべき乗は0乗からa乗までのa+1個、同様にqはb+1、rはc+1となり、これらの組合せになることを考えると上記の式は理解しやすいと思います。

素因数分解の結果から約数の個数を計算する
  1. def divisor_c(num):
  2. factor=factorint(num)
  3. cnt=1
  4. for expon in factor.values():
  5. cnt*=(expon+1)
  6. return cnt
  8. divisor_c(1200)

30

約数の合計を計算する

約数の個数は、素因数分解の結果から$N=p^aq^br^c \cdots$次の式で計算することができます。

$(p^0+p^1+…+p^a)(q^0+q^1+…q^b)(r^0+r^1+…+r^c)\cdots$

考え方は個数と同様です。

素因数分解の結果から約数の合計を計算する
  1. def divisor_s(num):
  2. factor=factorint(num)
  3. sigma=1
  4. for prime,expon in factor.items():
  5. terms = 0
  6. for i in range(expon+1):
  7. terms+=prime**i
  8. sigma*=terms
  9. return sigma
  11. divisor_s(1200)

少し面倒くさいプログラムになってしまいました。そこで、上記式の各項を初項1,公比pの各項は等比数列と考え、次の通り書き換えることができます。

$(p^0+p^1+…+p^a)(q^0+q^1+…q^b)(r^0+r^1+…+r^c)\cdots$=$\displaystyle \frac{p^{a+1}-1}{p-1}+\frac{q^{b+1}-1}{q-1}+\frac{r^{c+1}-1}{r-1}+\cdots$

これを式にすると次のようになります。

  1. # 素因数分解の結果から約数の個数を計算する
  2. def divisor_s(num):
  3. factor=factorint(num)
  4. sigma=1
  5. for prime,expon in factor.items():
  6. sigma*=int((prime**(expon+1)-1)/(prime-1))
  7. return sigma
  9. divisor_s(1200)

結果はいずれも次の通りです。

3844

約数の計算には興味深い結果がみられます。