約数
正の約数の和が n となる自然数 N を求めるには、初項 1 の素因数のべき和の積を既知とするところから求める必要がある。
初項 1 の素数のべき和の列は 1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20, 24, 30, ...(オンライン整数列大辞典の数列 A108348)
例:正の約数の和が 60 になる自然数 N の求め方:
60 = 1 × 60 = 2 × 30 = 3 × 20 = 4 × 15 = 5 × 12 = 6 × 10 = 2 × 3 × 10 = 2 × 5 × 6 = 3 × 4 × 5 = 2 × 2 × 3 × 5
これらのうち初項 1 の素数のべき和の積になっているのは
1 1 × 60 2 3 × 20 3 4 × 15
の3通りである。
1 σ(N) = 1 × (1 + 59) → N = 1 × 59 = 59
2 σ(N) = (1 + 2) × (1 + 19) → N = 2 × 19 = 38
3 σ(N) = (1 + 3) × (1 + 2 + 2 + 2) → N = 3 × 2 = 24
(ただし因数が 31 または 8191 のときは、初項 1 の素数のべき和の表示が一意でなく、2通りなので、答えが複数求まる。 31 = 1 + 2 + 2 + 2 + 2 = 1 + 5 + 5 8191 = 1 + 2 + 2 + ... + 2 = 1 + 90 + 90
自然数 N の正の約数の和を、約数関数 σ(N) で表す。素因数分解により、正の約数の和も式で表すことができる。
N の素因数分解を N = 235... とすると、
σ ( N ) = ( 1 + 2 1 + ⋯ + 2 a 1 ) ( 1 + 3 1 + ⋯ + 3 a 2 ) ( 1 + 5 1 + ⋯ + 5 a 3 ) ⋯ = 2 a 1 + 1 − 1 2 − 1 ⋅ 3 a 2 + 1 − 1 3 − 1 ⋅ 5 a 3 + 1 − 1 5 − 1 ⋅ ⋯ {\displaystyle {\begin{aligned}\sigma (N)&=(1+2^{1}+\cdots +2^{a_{1}})(1+3^{1}+\cdots +3^{a_{2}})(1+5^{1}+\cdots +5^{a_{3}})\cdots \\&={\frac {2^{a_{1}+1}-1}{2-1}}\cdot {\frac {3^{a_{2}+1}-1}{3-1}}\cdot {\frac {5^{a_{3}+1}-1}{5-1}}\cdot \cdots \end{aligned}}}
正の約数の和が奇数になる自然数は、平方数と平方数の2倍のみである。これは平方数の約数の個数が奇数個になることと偶数の素数が 2 しかないからである。