本原三角形

考虑三边长

a \leq b \leq c

均为整数的三角形。

本原三角形是其中满足

gcd (a, b, c) = 1

的三角形。

一共有多少个周长不超过

10^{7}

的本原三角形？

本题难度:

解答

设

f (n)

是三边长

a \leq b \leq c

均为整数且周长不超过n的三角形总数，

g (n)

是周长不超过n的本原三角形总数，则显然

f (n) = \sum_{k = 1}^{n} g (⌊ \frac{n}{k} ⌋),

即

g (n) = f (n) - \sum_{k = 2}^{n} g (⌊ \frac{n}{k} ⌋) .

根据OEIS A001400中的公式，f满足递推公式：

f (n) = 1 + f (n - 2) + f (n - 3) + f (n - 4) - f (n - 5) - f (n - 6) - a (n - 7) + f (n - 9),

且有初值（n从0到11）0,0,0,1,1,2,3,5,6,9,11,15，直接递计算即得结果

5777137137739632912

。

注：以下为Python 3代码，因记忆化搜索需要使用的cache装饰器为Python 3的新功能。

from functools import *

f=[0,0,0,1,1,2,3,5,6,9,11,15]

for n in range(12,10**7+1):
    f.append(f[n-2]+f[n-3]+f[n-4]-f[n-5]-f[n-6]-f[n-7]+f[n-9]+1)

@cache
def g(n):
    if n<=2:
        return 0;
    r=f[n]
    i=2
    while i<=n:
        j=n//(n//i)
        r-=g(n//i)*(j-i+1)
        i=j+1
    return r

print(g(10**7))