(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:
\(
P_{k,n} = \sum_{j=0}^{\infty} t_j A\left(k - (2j+1)2^{n-1}\right) \\
A(k) = \sum_{n=0}^{\infty} P_{k,n}
\)
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]).
