ProE12:高度可约的三角形数

原题:

高度可约的三角形数
三角形数数列是通过逐个加上自然数来生成的。例如,第7个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。三角形数数列的前十项分别是:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
让我们列举出前七个三角形数的所有约数:
 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
我们可以看出,28是第一个拥有超过5个约数的三角形数。
第一个拥有超过500个约数的三角形数是多少?

理论准备

首先我们要看出来一个正常小朋友都能看出的问题,所有三角形的约数数量都是某种程度上的偶数,这是因为所有约数数量为奇数的数字都是完全平方数,用反证法易证除1外所有三角形数都不是完全平方数。

因此,只需要算出一半的约数数量就可以了,这一半的约数显然不超过《ProE12:高度可约的三角形数》就可以了

同时我们也知道了约数的数量比两倍的原数字开方小,我们完全可以用约数数量的平方作为起点!

def factors (n):
    ans = 0
    for i in range (1,int(n**0.5)+1):
        if n%i == 0:
            ans += 1
    return ans*2
def triones (n):
    return n*(n+1)//2
def trifac(n):
    i = n
    while factors(triones(i))<=n:
        i += 1
    return triones(i)
print(trifac(500))

这便是用py的做法.非常非常的慢…………..在讨论版找不到好看的方法.

点赞

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *