iteration - 迭代计算递归序列 - 代码优化

Question

我必须计算给定序列的前 3000 个项目，如下所示：

a_1=1，a_n+1 = 最小整数 > a_n，对于每个（不一定不同）1<= i,j,k <= n+1 适用（a_i+a_j 不等于 3*a_k）

我已经编写了可以正常工作的代码（在 Magma 中），但它的时间复杂度显然太大了。我在问是否有办法降低时间复杂度。我有一个想法，以某种方式将内部 for 循环（这是造成破坏的循环）移出，以制作一个包含所有总和的数组，但我无法让它正常工作。在下面附上我的代码：

S:=[1];
for n:=2 to 3000 do
    new:=S[n-1];
    repeat
        flag:=0;
        new+:=1;
        for i,j in S do
            if (i+j eq 3*new) or (i+new eq 3*j) then
                flag:=1;
                break i;
            end if;
        end for;
    until flag eq 0;
    S[n]:=new;
end for;
print S[2015];

PS：如果它有帮助，我也知道 Python、Pascal 和 C，如果你喜欢这些语言中的任何一种。

Answer 1

我在 MAGMA 中复制了您的程序。运行时间为n=2978几4712.766秒钟。我改变了你的程序如下，结果是惊人的。更改版本的运行时间为n=3000几41.250秒钟。

S:=[1];
for n:=2 to 3000 do
    new:=S[n-1];
    repeat
        flag:=0;
        new+:=1;
        for i in S do
            if ((3*new-i) in S) or ((i+new)/3 in S) then
                flag:=1;
                break i;
            end if;
        end for;
    until flag eq 0;
    S[n]:=new;
end for;