Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding longest arithmetic progressions

  1. Dec 29, 2008 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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 Delft University of Technology's Van der Waerden numbers page. 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?
     
  2. jcsd
  3. Dec 29, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    OK, for comparative purposes, here's my direct translation of Erickson's pseudocode into Pari:
    Code (Text):
    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:
    Code (Text):
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Finding longest arithmetic progressions
  1. Arithmetic progression (Replies: 2)

Loading...