日常编码问题：三角数和大除数

欢迎大家回来，还有另一个问题需要解决！今天，我们将讨论三角数及其约数：尤其是大三角数！

虽然我们可以欣赏我对自然界中三角形数字的精彩艺术表现，但让我们先声明一下我们通常的免责声明：

1. 这个问题由精彩网站提供欧拉计划.net ，您可以订阅这里！有 800 多个数学和编码问题需要解决，并且有大量关于这些问题的讨论档案。它确实是一个让你绞尽脑汁学习新东西的完美工具！去看看并尝试解决你的挑战！

   
   

2. 我不是一个专业的程序员：只是一个喜欢写这类东西并喜欢分享他的镜头的人。我确信这不是最佳解决方案，因此，如果您有更好的解决方案或任何有关如何优化它的想法，我们非常欢迎您分享！

废话说得够多了，让我们看看今天的问题是什么：

三角形数序列是通过自然数相加生成的。所以第 7 个三角形数是 1+2+3+4+5+6+7=28。前十项为：1,3,6,10,15,21,28,36,45,55,...

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

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

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

问题非常简单：我们被要求了解第一个具有超过 500 个除数的三角数是什么。首先，让我们更好地了解什么是三角数以及什么是除数。

三角形数字

三角数是数字的一个特定子集，由直到某一特定数的所有自然数之和形成。它们被称为三角形，因为您总是可以将它们排列成三角形。这里有些例子：

在上图中，它是第三个、第四个和第五个三角形数字。因此，例如，第三个数字的形式为 1+2+3 = 6，第四个数字的形式为 1+2+3+4 = 10，依此类推。一般来说，nᵗʰ 三角数 Tₙ 等于

当然，这是数学中最著名的级数之一，也是由高斯提出的，他指出连续整数的总和等于：

所以基本上，例如，如果我们想计算第三个三角形数，我们只需计算 3*4/2 = 6。一旦我们开始编写解决方案，这将非常有帮助！

除数

要给出数字 n 的除数（或因子）的定义，非常简单：它是一个数字j ，可以乘以另一个整数k再次给出n 。例如，3是18的约数，因为我们可以将3和6相乘再次得到18。

然而，5 不是 18 的约数，因为没有数字k与 5 相乘得出 18。

通过定义，我们还得到一个重要的性质：如果j是n的约数，因为它可以乘以k得到n，那么k也是n的约数，因为它可以乘以j得到n。

这样我们就可以确定数字n总是至少有两个约数j和k （事实上， j可以总是 1 并且k可以是n ）。

另外，换句话说，如果n / j的余数等于 0 ，则数字j是数字n的除数。例如，18/3 = 6，余数为 0。

我们可以用模算术更好地形式化这个概念，即如果n % j = 0，则j是n的除数。换句话说，我们获得第二个属性：

我们感兴趣的第三个也是最后一个性质是，不存在大于 n/2 的数字n的约数，而不是n本身。这很容易理解。从第一个属性，我们知道因子在 1,…,n 范围内以某种方式“链接”在一起。

这是因为，如果j \ n，那是因为j * k = n。因此，也k\n。让我们再次以 18 为例，找到它的除数，并给它们着色以反映这个属性。

因此，举例来说，如果j = 3，k = 6，反之亦然，如果j = 6，k = 3，这意味着除了 1 之外，我们可以使用的最小j是 2，这给了我们最大的k可能， n/2 （在我们的例子中为 9） 。这有效：

• 对于偶数，在这种情况下最大的因子将恰好等于n 的一半；

• 对于奇数：如果我们不能将n除以 2（因为奇数会给我们一个有理数）；这意味着我们只能使用j > 2，这将始终给我们结果k < n/2。

  
  

最后，只有一种情况j和k可以相等：当n是平方数时。例如，当n = 36 时，一个可能的因子j = 6将产生另一个因子k = 6。稍后我们将在代码部分中详细讨论这种情况。

当然，这些概念非常琐碎，但它们在我们的解决方案中非常重要！

代码

代码将用Go编写，因为它确实是一种快速语言，但仍然保持很高的可读性。我们将解决方案分为两部分：首先，我们将创建一个函数来查找数字的除数，然后将其应用于三角形数字。

我们先看一下这个函数：

我们创建接受整数n并返回整数数组out的函数，其中将包含我们的除数。之后，我们out一些琐碎的因子，即 1 和n本身。

然后我们开始从 2 到n/2循环j （从第二个属性开始；还要注意，我们对n/2本身不感兴趣，因为如果n是偶数， k = n/2将被j = 2添加到除数中） j = 2次迭代：这就是为什么我们停在j<n/2而不是j≤ n/2 ）。

这样，我们只能在n的前半部分检查除数，从而大大加快了过程。

在每个循环中，我们检查 3 件事：

• 第三个 if 语句实际上检查是否n%j==0 ，换句话说，是否 0 ≠ n (mod j)。如果是这样，我们找到一个因素，并将j添加到列表中。我们还可以通过计算n/j然后移动到下一个j将其对应项k添加到列表中；

• 第二个 if 语句检查n是否为平方，因此j是n的根。如果是，则仅将一个除数j添加到out中，以避免重复，然后算法继续。

  
  

  假设n = 36 ：如果这个小块丢失，第三个 if 语句将被触发，导致out接收j = 6和k = n/j = 36/6 = 6 ，从而创建一个副本。

• 第一个 if 语句是最复杂的：它的目的是检查我们是否开始出现重复的jk对。如果是这样，我们可以立即中断循环，因为我们的因子都已经存在于out中。

  
  

具体来说，关于第三点，有两种情况需要检查：是否out[len(out)-1] == j或out[len(out)-2] == j 。

第一种情况是经典的：以数字 T₇ = 28 为例：

当j = 7时，它将等于最后插入的值。因此，我们可以打破循环。

第二种情况仅在我们找到平方n时发生。再以36为例：

当j = 9时，它将等于n的平方根之前附加的最后一个值，该值仅出现一次。因此，此时我们可以打破循环。

最后，我们可以简单地return out得到我们的除数。

应用结果

现在我们有了函数，我们可以将它应用于每个三角形数。我们将创建一个计数器c ，它将用作三角数的生成器。我们用高斯方程计算相关的三角数tn并检查它有多少个除数。

如果超过 500，我们将返回该tn作为结果。

但是……有一个问题！

ProjectEuler.net 确实是一个可爱的项目：除了呈现数学谜语和问题之外，他们的主要重点是提供一个开始学习、思考和推理数学的工具。

我喜欢这一点：他们如此坚定，以至于实际上禁止发布针对他们的问题的结果和指南（这是前 100 个问题之一，所以我知道这是允许的）。

鉴于此，我认为仅仅给出复制粘贴的解决方案并获得成就是不公平的。出于这个原因，我不会给你实际的解决方案：你自己尝试一下，并尝试想出一个比我的算法更好的算法（有很多算法）。对不起大家！ 😅

时间复杂度

我相信有很多更好的解决方案，因为我觉得这个镜头非常糟糕！

FindDivisor函数以线性时间运行：因为它取决于实例n的大小，并且它最多运行n/2个循环；我们可以将其视为 O(n)。

然而，我们必须先计算每个三角数，这也需要 O(tn) 时间，其中 tn 是结果（我们实际计算的最后一个）。鉴于此，整个算法的时间复杂度大约应为 O(tn*n)。

由于tn成为参数或我们的函数，并且我们在其中最多运行n/2个循环，因此我们可以将时间复杂度重写为 O(tn*tn/2) = O(tn²/2) = O(tn²)。不幸的是，这是一个二次时间解！

但令我惊讶的是，即使该算法具有这种复杂性，它的运行速度仍然相当快。为了在我的机器（AMD Ryzen 5，平均频率 2700 MHz）上给出结果，需要 322.564227 毫秒。

不过，尝试找到第一个超过 1000 因数的三角数花费了 3.827144472 秒，因此可以清楚地看到时间消耗正在迅速增加。

结论

我们终于成功了！我希望你们喜欢这篇文章，也希望你们能从中得到一些有趣的东西：如果是这样，请拍一两下，并与可能对这个主题感兴趣的人分享这篇文章！

再次对 ProjectEuler 的出色工作表示大力赞扬：我真的想建议你去看看他们能提供什么；我相信你会发现它超级有趣！

一如既往，感谢您的阅读。

尼古拉