Thread Rating:
  • 1 Vote(s) - 5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
My favorite integer sequence
#62
(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
Reply


Messages In This Thread
My favorite integer sequence - by tommy1729 - 07/27/2014, 08:44 PM
RE: My favorite integer sequence - by jaydfox - 07/31/2014, 01:51 AM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 01:53 AM
RE: My favorite integer sequence - by Gottfried - 08/01/2014, 03:25 PM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 05:04 PM
RE: My favorite integer sequence - by sheldonison - 08/01/2014, 11:36 PM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 11:57 PM
RE: My favorite integer sequence - by jaydfox - 08/05/2014, 04:49 PM
RE: My favorite integer sequence - by jaydfox - 08/05/2014, 05:57 PM
RE: My favorite integer sequence - by Gottfried - 08/06/2014, 04:38 PM
RE: My favorite integer sequence - by jaydfox - 08/07/2014, 01:19 AM
RE: My favorite integer sequence - by jaydfox - 08/07/2014, 01:34 AM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 09:42 AM
RE: My favorite integer sequence - by Gottfried - 08/09/2014, 02:27 PM
RE: My favorite integer sequence - by tommy1729 - 09/09/2014, 12:55 AM
RE: My favorite integer sequence - by jaydfox - 08/08/2014, 12:55 AM
RE: My favorite integer sequence - by Gottfried - 08/08/2014, 02:27 AM
RE: My favorite integer sequence - by jaydfox - 09/09/2014, 07:43 PM
RE: My favorite integer sequence - by jaydfox - 09/09/2014, 09:45 PM
RE: My favorite integer sequence - by jaydfox - 08/02/2014, 12:08 AM
RE: My favorite integer sequence - by tommy1729 - 08/03/2014, 11:38 PM
RE: My favorite integer sequence - by sheldonison - 08/04/2014, 11:49 PM
RE: My favorite integer sequence - by jaydfox - 09/16/2014, 05:32 AM
RE: My favorite integer sequence - by Gottfried - 09/17/2014, 07:39 PM
RE: My favorite integer sequence - by jaydfox - 10/02/2014, 10:53 PM
RE: My favorite integer sequence - by Gottfried - 08/03/2014, 03:32 PM
RE: My favorite integer sequence - by tommy1729 - 08/03/2014, 11:44 PM
RE: My favorite integer sequence - by sheldonison - 08/02/2014, 05:48 AM
RE: My favorite integer sequence - by tommy1729 - 09/10/2014, 08:57 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 07:43 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 09:29 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 09:36 PM
RE: My favorite integer sequence - by tommy1729 - 08/05/2014, 11:16 PM
RE: My favorite integer sequence - by tommy1729 - 08/08/2014, 11:02 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 07:02 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 10:51 PM
RE: My favorite integer sequence - by sheldonison - 08/11/2014, 04:51 PM
RE: My favorite integer sequence - by jaydfox - 08/11/2014, 05:19 PM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 01:36 AM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 02:05 AM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 05:31 PM
RE: My favorite integer sequence - by sheldonison - 08/19/2014, 07:56 PM
RE: My favorite integer sequence - by jaydfox - 08/20/2014, 07:42 AM
RE: My favorite integer sequence - by sheldonison - 08/20/2014, 02:11 PM
RE: My favorite integer sequence - by jaydfox - 08/20/2014, 07:57 PM
RE: My favorite integer sequence - by jaydfox - 08/21/2014, 01:15 AM
RE: My favorite integer sequence - by jaydfox - 08/21/2014, 05:25 AM
RE: My favorite integer sequence - by jaydfox - 08/22/2014, 05:39 PM
RE: My favorite integer sequence - by jaydfox - 09/11/2014, 01:33 AM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 09:16 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 10:19 PM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 10:52 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 11:46 PM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 11:10 PM
RE: My favorite integer sequence - by jaydfox - 08/10/2014, 12:30 AM
RE: My favorite integer sequence - by tommy1729 - 08/11/2014, 12:17 PM
RE: My favorite integer sequence - by Gottfried - 08/22/2014, 12:30 AM
Amazing variant - by tommy1729 - 08/26/2014, 08:57 PM
RE: My favorite integer sequence - by tommy1729 - 09/01/2014, 10:37 PM
RE: My favorite integer sequence - by tommy1729 - 10/02/2014, 11:24 PM
RE: My favorite integer sequence - by jaydfox - 10/02/2014, 11:29 PM
RE: My favorite integer sequence - by tommy1729 - 02/10/2015, 12:15 AM
RE: My favorite integer sequence - by tommy1729 - 02/15/2015, 05:19 PM
RE: My favorite integer sequence - by tommy1729 - 10/07/2015, 08:22 AM
RE: My favorite integer sequence - by tommy1729 - 10/07/2015, 09:10 PM
RE: My favorite integer sequence - by tommy1729 - 03/13/2016, 12:31 AM

Possibly Related Threads...
Thread Author Replies Views Last Post
  My favorite theorem tommy1729 0 3,999 08/15/2015, 09:58 PM
Last Post: tommy1729



Users browsing this thread: 1 Guest(s)