10/02/2014, 10:53 PM

(09/16/2014, 05:32 AM)jaydfox Wrote: I feel like I'm close to a pattern here that will really speed up calculations. I might be able to ditch the polynomials entirely. I've found some other strange recurrences, one of which uses that Thue-Morse sequence, which Gottfried previously described in post #10 on the first page of this thread. I'll try to detail those later this week.

Regarding the Thue-Morse connection, I first noticed it while trying to come up with a way to calculate the coefficients at powers of 2. I said previously:

(09/16/2014, 05:32 AM)jaydfox Wrote: However, what does seem to bear fruit is to look at the polynomials evaluated at powers of 2. The first few are:

Code:`1`

1 1

1 2 1

1 4 4 1

1 8 16 10 1

1 16 64 84 36 1

1 32 256 680 656 202 1

1 64 1024 5456 10816 8148 1828 1

From left to right, these are the evaluations of the 0th, 1st, 2nd, 3rd, etc. order polynomials. From top to bottom, these are the polynomials evaluated at 2^k, where k is the row number, with the first row being k=-1 (to make the math simpler, so that the second row is evaluated at 2^0 = 1).

When you look at columns, you will note that the left-most column (the zeroeth column, as it corresponds to the 0-order polynomial) is always 1. The first column (2nd from the left) is a power of 2. The second column is a power of 4.

Well, if you look at the right side of the triangle, the diagonal is always 1. The first subdiagonal is A(2^k), i.e., it's a term in the sequence. Specifically, for the row which corresponds to A(2^n), the subdiagonal is A(2^(n-1)).

For example, in the 3rd row--the row corresponding to A(2^3), which is the row with 5 entries (1 8 16 10 1)--the subdiagonal entry is 10, which is A(2^2).

If you look at the second subdiagonal entry, this also follows a pattern. It helps to look a little further down the triangle. In the 5th row (1 32 256 680 656 202 1), the second subdiagonal is 656, which happens to be 692-36. Therefore, 656 = A(24)-A(8)

The third subdiagonal is 680. It took me a while to spot the pattern. I had to reverse engineer it, by comparing how the value was constructed from previous entries. But it turns out that it's equal to 1154-380+94. And 380 is 390 - 10. So it's 1154 - 390 - 94 + 10. This turns out to be A(28) - A(20) - A(12) + A(4).

Restated:

P_{2^5},6 = 1 = A(0)

P_{2^5},5 = 202 = A(2^4)

P_{2^5},4 = 656 = A(3*2^3) - A(1*2^3)

P_{2^5},3 = 680 = A(7*2^2) - A(5*2^2) - A(3*2^2) + A(1*2^2)

(Here, P_{2^k}, 2^k means the row for A(2^k), and n means the term corresponding to the nth degree polynomial.)

When I noticed the last line there resembled the Thue-Morse sequence (+--+), which Gottfried had previously described, I decided to see if the pattern continues: (+--+-++-)

Predicted: P_5,2 = A(15*2) - A(13*2) - A(11*2) + A(9*2) - A(7*2) + A(5*2) + A(3*2) - A(1*2)

And sure enough, 1460 - 900 - 524 + 284 - 140 + 60 + 20 - 4 = 256, as predicted.

After some more investigation, I found that this pattern holds for any row in the table, not just at powers of 2.

For the row corresponding to A(37) = 3074:

1 37 342 1050 1180 450 14

P_37,6 = 14 = A(37-1*2^5)

P_37,5 = 450 = A(37-1*2^4) - A(37-3*2^4)

P_37,4 = 1180 = A(37-1*2^3) - A(37-3*2^3) - A(37-5*2^3) + A(37-7*2^3)

In general:

Here, t_j is the jth term in the Thue-Morse sequence, starting with t_0 = 1, t_1 = -1, and so on. We can take the infinite sums, because A(m) is 0 for any negative m. In practice, of course, we would stop the sum when m goes negative.

I suspect, but have not confirmed, that the reason for the Thue-Morse sequence in the first equation is due to the way that A is constructed in the second equation in terms of P, combined with the recurrence relation that defined A:

A(k) = A(k-1) + A([k/2]).

~ Jay Daniel Fox