Finding longest arithmetic progressions

[CRGreathouse]

Meta-note: This post includes both computer science and computational number theory. I could have posted it in the Programming forum, the CS forum, the NT forum, or here; I felt that this was the best place, especially since the CS forum does not actually deal with computer science these days.

I was looking to verify some of the bounds on van der Waerden numbers, in particular the new ones posted at the http://www.st.ewi.tudelft.nl/sat/waerden.php. I thought this would be a good exercise for me, and that's what the certificates are for, right?

Apart from checking that numbers appear exactly once, the problem comes down to checking that there are no long arithmetic progressions in each of the sequences. I started by coding a direct implementation of Jeff Erickson's quadratic algorithm: Finding longest arithmetic progressions. The trouble is that the method requires an n x n array to find the longest progression in a list of length n, so verifying a lower bound of L for W(r, k) requires at least ceil(L/r)^2 memory. As I was using Pari (where a number takes at least 128 bits, I believe), this limited me to about 16,000 (in theory, with r = 2 and 1 GB of free memory) and only about 9,000 in practice (for r = 2 -- more for larger r).

Is there a good way to go further? Quadratic time and space won't let me verify large bounds. Is there a more memory-efficient algorithm, or perhaps a time-space tradeoff I can use?

 

[CRGreathouse]

OK, for comparative purposes, here's my direct translation of Erickson's pseudocode into Pari:

longestProgression1(v)={
	my(L=matrix(#v,#v),Lstar=2,i,k,tmp);
	if(#v<3,return(#v));
	forstep(j=#v-1,1,-1,
		i=j-1;
		k=j+1;
		while(i>0 && k <= #v,
			tmp=v[i]+v[k]-2*v[j];
			if(tmp<0,
				k++
			,
				if(tmp>0,
					L[i,j]=2;
					i--
				,
					L[i,j]=L[j,k]+1;
					Lstar=max(Lstar,L[i,j]);
					i--;
					k++
				)
			)
		);
		while(i>0,
			L[i,j] = 2;
			i--
		)
	);
	Lstar
};

Here's a totally naive snippet that uses linear space:

longestProgression(v)={
	my(r=0,s,t,d);
	if(#v<3,return(#v));
	s=Set(v);
	for(i=1,#v-1,
		for(j=i+1,#v,
			t=2;
			d=v[j]-v[i];
			while(setsearch(s,v[i]+d*t), t++);
			r=max(r, t)
		)
	);
	r
};

I'm going to test the second to see if it's fast enough to work, but I doubt it. A standard language would do this better, though -- maybe I'll try this in C. I may also be able to use heuristics relating the the fact that I expect the numbers to be tightly packed to speed the binary search.