第12题: 高可整除三角形数

题目

高可整除三角形数

三角形数序列是由自然数相加组成的。所以第 $7$ 个三角形数是 $1+2+3+4+5+6+7=28$。三角形数的前十项如下：

$$ 1,3,6,10,15,21,28,36,45,55,… $$

让我们列出前七个三角形数的因数：

$$ \begin{aligned} 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 \end{aligned} $$

我们可以看到 $28$ 是第一个拥有超过 $5$ 个因数的三角形数。

第一个因数个数超过 $500$ 的三角形数的值是多少？

Highly Divisible Triangular Number

The sequence of triangle numbers is generated by adding the natural numbers. So the $7$th triangle number would be $1+2+3+4+5+6+7=28$. The first ten terms would be:

$$ 1,3,6,10,15,21,28,36,45,55,… $$

Let us list the factors of the first seven triangle numbers:

We can see that $28$ is the first triangle number to have over five divisors.

$$ \begin{aligned} 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 \end{aligned} $$

What is the value of the first triangle number to have over five hundred divisors?

解题方法

暴力解法

三角形数公式如下：

$$ t=n*(n+1)/2 $$

递增求解三角形数后，通过循环判断该数因数求得答案。

求解公式

根据算术基本定理，对于任意的正整数 $N$ 存在唯一分解为

$$ N={p_1}^{a_1}\times {p_2}^{a_2}\times {p_3}^{a_3}\times \cdots \times{p_n}^{a_n} = \prod_{i=1}^{n}p_{i}^{k_{i}} $$

根据乘法原理对唯一分解中的因数进行组合，则对于任意正整数 $N$ 的因数个数 $d(N)$ ，存在一下计算方法

$$ d(N)=(a_1 + 1) \times (a_2 + 1) \times (a_3 + 1) \times \cdots \times (a_n + 1)=\prod_{i=1}^{n}\left(a_{i}+1\right) $$

假设 $N=N_1 \times N_2$，且 $N_1$ 和 $N_2$ 互素，则上述公式可以有以下计算

$$ \begin{aligned} N&=N_1 \times N_2 \\ &=\prod_{i=1}^{n_1}p_{i}^{k_{i}} \times \prod_{j=1}^{n_2}p_{j}^{k_{j}} \\ \end{aligned} $$

因数个数公式可进行如下计算：

$$ \begin{aligned} d(N)&=\prod_{i=1}^{n_1}\left(a_{i}+1\right) \times \prod_{j=1}^{n_2}\left(a_{j}+1\right) \\ &=d(N_1)\times d(N_2) \\ \end{aligned} $$

观察三角数公式可知 $n$ 和 $n+1$ 之间互素，因此

$$ d(t) = \begin{cases} d(n)\times d((n+1)/2) & \text{if $n$ is even} \\ d(n/2)\times d(n+1) & \text{if $n+1$ is even} \\ \end{cases} $$

根据求得的公式以此计算求解。