08/05/2014, 05:57 PM

(08/05/2014, 04:49 PM)jaydfox Wrote:(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'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.

...I will explore some of those patterns in my next post.

Okay, time to look at the patterns. The first picture shows how the coefficients can be calculated by a recurrence relation that's actually quite similar to the basic recurrence relation for the sequence itself:

Now, let's take a look at a semi-random sampling of such recurrences, all plotted together:

This recurrence relation is not particularly useful, however. To calculate the coefficients for the kth row, you have to calculate all k-1 rows before it. It calculates in O(n*log(n)) time (the log(n) factor is due to requiring log(n) columns of data for each row).

A more useful pattern is the following:

Notice that I can calculate entries spaced out at multiple of 2^m for the mth column. If you look closely, you should also notice that those entries follow polynomial growth.

In column 0, the entries are 1, which is a constant:

F_k,0 = 1

In column 1, the entries are 0, 1, 2, 3, 4, etc., which fit a linear polynomial:

F_k,1 = k

In column 2, the even entries are 0, 1, 4, 9, 16, etc., which fit a quadratic polynomial:

F_k,2 = [k/2]^2

In column 3, the 4th entries are 0, 1, 10, 35, 84, etc., which fit a cubic polynomial:

F_k,3 = 4/3*[k/4]^3 - 1/3*[k/4]).

In column 4, the 8th entries are 0, 1, 36, 201, 656, 1625, etc., which fit a degree 4 polynomial:

F_k,4 = 8/3*[k/8]^4 - 5/3*[k/8]^2)

In column 5, the 16th entries are 0, 1, 202, 1827, 8148, 25509, etc., which fit a degree 5 polynomial:

F_k,5 = 128/15*[k/16]^5 - 28/3*[k/16]^3 + 9/5*[k/16]

The polynomials can be calculated using your preferred method of polynomial interpolation (Lagrange, Newton, divided differences, etc.). To get the points, use the pattern from the image above.

For example, here is SAGE (python) code which calculates the polynomials (which still need to be rescaled by appropriate powers of 2, but this is just to demonstrate a proof of concept).

Code:

`max_degree = 7`

fs = []

f0(x) = 1

fs.append(f0)

for n in xrange(max_degree):

pts = [0]

diffs = [0]

for k in xrange(n+1):

pts.append(pts[-1]+fs[n](x=k*2+1))

fn(x) = 0

print pts

for deg in xrange(n+1, -1, -1):

diffs = [pts[i]-fn(x=i) for i in xrange(deg+1)]

for itr in xrange(deg):

for k in xrange(deg-itr):

diffs[k] = diffs[k+1] - diffs[k]

fn += diffs[0]/factorial(deg) * x^deg

print fn

fs.append(fn)

And here is the output:

Code:

`[0, 1]`

x |--> x

[0, 1, 4]

x |--> x^2

[0, 1, 10, 35]

x |--> 4/3*x^3 - 1/3*x

[0, 1, 36, 201, 656]

x |--> 8/3*x^4 - 5/3*x^2

[0, 1, 202, 1827, 8148, 25509]

x |--> 128/15*x^5 - 28/3*x^3 + 9/5*x

[0, 1, 1828, 27337, 167568, 664665, 2026564]

x |--> 2048/45*x^6 - 680/9*x^4 + 1397/45*x^2

[0, 1, 27338, 692003, 5866452, 29559717, 109082974, 326603719]

x |--> 131072/315*x^7 - 43648/45*x^5 + 30044/45*x^3 - 11843/105*x

I'll work on converting this to PARI/gp code, since I know that several of the active members of this forum seem to use that.

~ Jay Daniel Fox