← 完整题目索引

PROJECT EULER · #0585

嵌套平方根

Nested Square Roots

仅题目 · 待解原题 ↗

考虑术语 x+y+z ,它表示嵌套平方根。 x、y和z是正整数,并且y和z不允许是完全平方数,因此外平方根下面的数字是无理数。仍然可以证明,对于 x、y 和 z 的某些组合,给定项可以简化为整数的简单平方根的和和/或差,实际上解除嵌套初始表达式中的平方根。

以下是这种解除嵌套的一些示例:
3+2+2=2+1=2+1
8+15+15=5+3
20+96+12=9+6+3−2=3+6+3−2
28+160+108=15+6+5−2

正如您所看到的,嵌套表达式中使用的整数也可能是完全平方数,从而进一步简化。

令 F(n) 为不同项 x+y+z 的数量,其可以嵌套为有限数量的平方根的和和/或差,给定附加条件 0<x≤n。也就是说,
x+y+z=∑i=1ksiai
其中k、x、y、z和所有ai都是正整数,所有si=±1和x≤n。
此外y和z不允许是完全平方数。

具有相同值的嵌套根不被视为不同,例如 7+3+27、7+12+12 和 7+27+3,这三个都可以解除嵌套2+3,仅计算一次。

已知 F(10)=17、F(15)=46、F(20)=86、F(30)=213 和 F(100)=2918 以及 F(5000)=11134074。
查找 F(5000000)。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。