08/05/2014, 04:49 PM

(08/01/2014, 11:57 PM)jaydfox Wrote: I'm working on a set of generator polynomials that would allow me to compute an arbitrary term in the sequence in log-polynomial time. For instance, the naive approach requires O(n) calculations to calculate the nth term.

The generator polynomials are a set of log_2(n) polynomials of degree 1 through log_2(n). Calculating the kth polynomial requires calculating k+1 points from the (k-1)th polynomial. I haven't fully worked out the math, but I think it runs in something like O(log_2(n) ^ m) time, where m is a small constant, maybe 3 or 4. So, for example, calculating the 2^100th term in the sequence took about 10 minutes (as opposed to O(2^100) calculations, which would take forever on pretty much any processor).

I'll try to post gp code next week (it's in SAGE at the moment, and I'm not sure who else is using SAGE besides me... Andy and Henryk were using it a few years ago, not sure if they still do...)

I'm not sure that "generator polynomial" is the right word for what I'm developing, because I've seen the term used in other contexts, and I'm not sure if it has a very specific meaning. In my context, I'm using it to generate coefficients for recurrence relationships.

To start with, I need to explain where and why I came up with these. It helps to look at the information flow diagram from an earlier post (post #5 in the current thread).

I was trying to figure out if I could define a given term in the sequence as combination of earlier elements. To do this formally, I suppose we should number the elements, based on the row and column in my diagram. Hopefully it's obvious that the left-most row is actually the row number. So starting with a couple rows over, we have A_0,0 = 1, A_1,0 = 2, A_5,0 = 14, A_6,1 = 6, etc.

So the simplest recurrence is:

We can apply it recursively to get:

Now for the more interesting part. Column 1 only adds the element to its right on the even rows:

Let's look at the recursive version:

Notice that clever use of the floor function has eliminated the need to make explicit cases for either j or k being odd. If [j/2]+1 > [k/2] (e.g., if k is 5 and j is 4, then [j/2]+1 = 3, and [k/2] = 2), then no summation occurs.

What gets more interesting still is when we go back to the first recursive formula, and try to recursively expand it in terms of the second recursive formula:

This representation is a bit unwieldly, especially because we need to continue expanding to the right with further summations. It helps to view it as a matrix, with the nested sums already calculated:

Now a bit of explanation here. Let's pick row 5. In row 5, you will see 1, 5, 6, 2, 0, 0

What this means, is that A_5,0 = 1*A_0,0 + 5*A_0,1 + 6*A_0,2 + 2*A_0,3 + 0*A_0,4 + 0*A_0,5 +..., which yields A_5,0 = 14, which is what we were looking for.

Because the coefficients are non-zero up to the fourth column, I can only apply this recurrence with j = 0 mod 8. (It should become clear with more examples).

So, for A_13,0, I get 1*A_8,0 + 5*A_8,1 + 6*A_8,2 + 2*A_8,3 + 0*A_8,4 + 0*A_8,5 +..., which is 1*36 + 5*10 + 6*4 + 2*2 + 0*1... which yields A_13,0 = 114, which is the value of A_13.

I could also have solved A_13 by using the appropriate coefficients from my table. A_13,0 = 1*A_0,0 + 13*A0,1 + 42*A0,2 + 44*A0,3 + 14*A0,4 + 0*A0,5..., which works out to 114, just as before.

If you want to check the next one, A_21, you will find that 1*202 + 5*36 + 6*10 + 2*4 yields 450, which is correct.

What about using the row 13 coefficients? As it turns out, the coefficients in rows 8 through 15 only are valid if j is a multiple of 16. For example, for A_21, you would get 1*A_8,0 + 13*A_8,1... = 1*36 + 13*10 + 42*4 + 44*2 + 14*1 = 436, which is incorrect (should have been 450).

However, all is right again when we go to A_29, which is equivalent to 5 (mod 8 ) and 13 (mod 16). In both cases (you can check), you get 1294. You can also use the coefficients for row 29 directly, which are 1, 29, 210, 504, 436, and 114. Summing them directly (i.e., using row 0), you get 1294.

Curiously, you'll notice that the second to last term was 436, which just happens to match the incorrect result from applying the row 13 coefficients to row 8. Little patterns like this present themselves all over the place, and I will explore some of those patterns in my next post.

~ Jay Daniel Fox