Calculating a recursive sequence iteratively - code optimization

Question

I have to calculate first 3000 items of a sequence given as follows:

a_1=1, a_n+1 = smallest integer > a_n, for which for every (not necessarily different) 1<= i,j,k <= n+1 applies (a_i+a_j not equal 3*a_k)

I have written code (in Magma) that works correctly, but its time complexity is obviously way too large. I am asking if there is a way to reduce the time complexity. I had an idea to somehow move the inner for loop (which is the one causing havoc) out in a way of making an array of all the sums, but I cant get it to work right. Attaching my code below:

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];

P.S.: If it helps, I also know Python, Pascal and C if you prefer any of those languages.

Answer 1

I copied your program in MAGMA. Run time for n=2978 was 4712.766 seconds. I changed your program as follow and result was amazing. Run time for changed version for n=3000 was 41.250 seconds.

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;