设$f(n)$是三边长$a\le b\le c$均为整数且周长不超过n的三角形总数，$g(n)$是周长不超过n的本原三角形总数，则显然
$$f(n)=\sum_{k=1}^ng(\left\lfloor\dfrac{n}{k}\right\rfloor),$$
即
$$g(n)=f(n)-\sum_{k=2}^ng(\left\lfloor\dfrac{n}{k}\right\rfloor).$$
根据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))
|
