The x taking 1, 2, 3, 4, ... is a time eater, Ilian's In[2] is
latev1[l_] := Module[{b = {}, i, k, m = 1, s, x},
For[i = 1, i < Length[l], i++,
For[x = 1, x < (Last[l] - l[[i]])/m, x++,
s = {l[[i]]};
k = 1;
While[MemberQ[l, l[[i]] + k x], AppendTo[s, l[[i]] + k x]; k++];
If[Length[s] >= m, b = s; m = Length[s]]
]
];
b
] /; VectorQ[l, IntegerQ] && OrderedQ[l]
take the x at real differences only instead
latevAP[l_] := Module[{b = {}, i, j, k, m = 1, s, x},
For[i = 1, i < Length[l], i++,
For[j = i + 1, j <= Length[l], j++,
x = l[[j]] - l[[i]];
If[x < 1 || x >= (Last[l] - l[[i]])/m, Break[]];
s = {l[[i]], l[[j]]};
k = 2;
While[MemberQ[l, l[[i]] + k x], AppendTo[s, l[[i]] + k x]; k++];
If[Length[s] >= m, b = s; m = Length[s]]
]
];
b
] /; VectorQ[l, IntegerQ] && OrderedQ[l]
and try some data
In[5]:= a2 = FoldList[Plus, 3, 23 RandomInteger[5, 500]];
In[7]:= Length[a2]
Out[7]= 501
In[8]:= OrderedQ[a2]
Out[8]= True
In[9]:= Timing[latev1[a2]]
Out[9]= {39.733455, {6604, 8812, 11020, 13228, 15436, 17644, 19852, 22060, 24268, 26476}}
In[20]:= Timing[latevAP[a2]]
Out[20]= {0.811205, {6604, 8812, 11020, 13228, 15436, 17644, 19852, 22060, 24268, 26476}}