• 1 Vote(s) - 5 Average
• 1
• 2
• 3
• 4
• 5
 My favorite integer sequence jaydfox Long Time Fellow Posts: 440 Threads: 31 Joined: Aug 2007 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: $ 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]). ~ Jay Daniel Fox « Next Oldest | Next Newest »

 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)