問題
三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.
最初の7項について, その約数を列挙すると, 以下のとおり.1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
では, 500個より多く約数をもつ最初の三角数はいくつか.
素直に
500 |
% {
for ($i, $d = 1, 0; $d -le $_; $i++)
{
for ($n, $d, $p = ($i * ($i + 1) / 2), 1, 2; $p * $p -le $n; $($p++; $d *= $x))
{for ($x = 1; $n % $p -eq 0; $x++)
{$n = $n / $p}}
if ($n -ne 1) {$d *= 2}
}
$i * ($i - 1) / 2
}
約数の表を生成して
500 |
% {
$ds = New-Object System.Collections.Generic.List[Int]
$ps = New-Object System.Collections.Generic.List[Int]
$ds.Add(1)
$ds.Add(1)
$i, $maxD = 2, 1
for ($j = 1; $maxD -le $_; $j++)
{
0,1 |
% {2 * $j + $_} |
% {
foreach ($p in $ps)
{
if ($p * $p -gt $_)
{break}
if ($_ % $p -eq 0)
{
if (($_ / $p) % $p -ne 0)
{return $ds.Add(2 * $ds[$_ / $p])}
return $ds.Add(2 * $ds[$_ / $p] - $ds[$_ / $p / $p])
}
}
$ds.Add(2)
$ps.Add($_)
}
0,1 |
? {$maxD -lt $ds[$j + $_] * $ds[2 * $j + 1]} |
% {
$i = 2 * $j + $_
$maxD = $ds[$j + $_] * $ds[2 * $j + 1]
}
}
$i * ($i + 1) / 2
}
考え方
以下、単に約数と書いた場合、正の約数を意味する。
素直な実装
2以上の整数 $n$ が $m$ 個の素因数$p_1, p_2, \dots, p_m$を持つ時、すなわち、$n$ が次のように表せる時
$$ n = \prod_{k = 1}^m p_k^{a_k} $$
$n$の約数の個数$d(n)$は
$$ d(n) = \prod_{k = 1}^m (a_k + 1)$$
となる。$i$ 番目の三角数$T(i)$は
$$T(i) = \sum_{k=1}^{i} k = \frac{1}{2} i (i + 1)$$
であるから、$T(i)$を試し割りで素因数分解して約数を計算していけば、解を得る。
といった、考察を踏まえて実装したのが一つ目の実装である。
約数の表を生成して
$T(i) = \frac{1}{2} i (i + 1)$における、$i$ と $i + 1$は互いに素であるため、
- $i$が偶数ならば、$d(T(i)) = d(\frac{1}{2}i (i + 1)) = d(\frac{i}{2})d(i + 1)$
- $i$が奇数ならば、$d(T(i)) = d(\frac{1}{2}i (i + 1)) = d(i)d(\frac{i + 1}{2})$
となる。そのため$i$番目の三角数の約数は、$i + 1$までの約数$d(1), d(2), \dots, d(i + 1)$が求まっていれば計算できる。
また、正整数 $n$ は 素数 $p$ と正整数 $m, k$ で次のように書ける。
$$n = p^m k$$
ただし、$p$ は $n$ の素因数で、$p$、$k$ は互いに素とする。 互いに素であることを使うと次のことが言える。
- $m = 1$ならば、$d(n) $$= d(pk) $$= d(p)d(k) $$= 2d(k) $$= 2 d(\frac{n}{p})$
- $m > 1$ならば、$d(n) $$= d(p^m k)$$= d(p^m)d(k)$$= (m + 1) d(k) $$= (2 m - (m - 1)) d(k) $$= 2 m d(k) - (m - 1) d(k) $$= 2 d(p^{m-1}) d(k) - d(p^{m-2})d(k)$$= 2 d(p^{m-1} k) - d(p^{m-2} k)$$= 2 d(\frac{n}{p}) - d(\frac{n}{p^2})$
$\frac{n}{p^2} < \frac{n}{p} < n$ なので、$n-1$までの約数$d(1), d(2), \dots, d(n-1)$と$p$が求まっていれば、$n$の約数$d(n)$を計算できる。
$p$は$n$以下の素数で試し割りすれば求まる。
といった、考察を踏まえて実装をこねくり回した結果が二つ目の実装である。
以上
範囲が決まっていればエラトステネスの篩を応用して約数表を求められるはずだが、本問については範囲の上界がわからず、その方法を諦めた。