[math-fun] Looking for a recurrence related to Stern's diatomic array
Stern's diatomic array (A049456) is a triangle in which row n lists the denominators in the n-th row of the table of Farey fractions. Another version of A049456 is the Stern-Brocot sequence (A002487) which has the recurrence a(2n)=a(n), a(2n+1)=a(n)+a(n+1), with a(0)=0, a(1)=1. There are a huge number of references. Someone recently asked me about a sequence which I was able to show was equal to the number of distinct terms in the n-th row of Stern's A049456. Surprisingly, this was not in the OEIS, although it is now - see A293160: 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, ... Can someone find a recurrence? (The smallest positive missing number from row n is A135510, which has an 1850 reference to Eisenstein.)
Quoting Neil Sloane <njasloane@gmail.com>:
Stern's diatomic array (A049456) is a triangle in which row n lists the denominators in the n-th row of the table of Farey fractions. Another version of A049456 is the Stern-Brocot sequence (A002487) which has the recurrence a(2n)=a(n), a(2n+1)=a(n)+a(n+1), with a(0)=0, a(1)=1. There are a huge number of references. Someone recently asked me about a sequence which I was able to show was equal to the number of distinct terms in the n-th row of Stern's A049456. Surprisingly, this was not in the OEIS, although it is now - see A293160: 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, ... Can someone find a recurrence? (The smallest positive missing number from row n is A135510, which has an 1850 reference to Eisenstein.)
Some preliminaries to look for clues ... The ratios of successive terms 2.0 1.5 1.6666666 1.4 1.8571428 1.5384616 1.55 1.548387 1.625 1.5128205 1.6186441 1.5706806 1.55 1.5784947 1.6008174 1.5744681 1.5816216 1.5710868 1.5871221 1.5833334 1.5822369 1.5791115 1.5879153 1.5787222 1.585798 These are mostly an up & down sequence, but with exceptions. The ratios appear to be converging, but slowly, somewhat erraticly. The ratio of term21:term20 is exactly 19:12, rather simple. A simple linear recurrence would have roughly a geometric convergence to the term ratio, similar to the Fibonacci sequence. This sequence doesn't. The remainders mod 2 and 3 are (1 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0) (1 2 0 2 1 1 2 1 0 0 1 2 0 0 2 2 2 1 1 0 2 2 0 1 2 1) with no obvious periodicity. The factorizations are "nothing special", with perhaps a minor excess of small factors 2,3,5, and maybe 19. (1 (1)) (2 (2)) (3 (3)) (5 (5)) (7 (7)) (13 (13)) (20 (2 2 5)) (31 (31)) (48 (2 2 2 2 3)) (78 (2 3 13)) (118 (2 59)) (191 (191)) (300 (2 2 3 5 5)) (465 (3 5 31)) (734 (2 367)) (1175 (5 5 47)) (1850 (2 5 5 37)) (2926 (2 7 11 19)) (4597 (4597)) (7296 (2 2 2 2 2 2 2 3 19)) (11552 (2 2 2 2 2 19 19)) (18278 (2 13 19 37)) (28863 (3 3 3 1069)) (45832 (2 2 2 17 337)) (72356 (2 2 18089)) (114742 (2 103 557)) The balanced remainder of the Nth term mod N looks a little unusual. Random would be |average| of N/4; these are a little less. No obvious pattern of the signs. (1 1 0) (2 2 0) (3 3 0) (4 5 1) (5 7 2) (6 13 1) (7 20 -1) (8 31 -1) (9 48 3) (10 78 -2) (11 118 -3) (12 191 -1) (13 300 1) (14 465 3) (15 734 -1) (16 1175 7) (17 1850 -3) (18 2926 -8) (19 4597 -1) (20 7296 -4) (21 11552 2) (22 18278 -4) (23 28863 -2) (24 45832 -8) (25 72356 6) (26 114742 4) Rich
I didn't mention it, because I'm not sure it helps, but the third Comment in A002487 by Takashi Tokita looks hopeful. It says that the columns (if the triangle is left justified) form arithmetic progressions, and the common difference in column k is simply the k-th term of the sequence! The rows roughly double in length at each step. So the remark means that we can build row k+1 using arithmetic progressions based on all the earlier rows. Here's the start of the left-justified array. Each column is an AP: 1 1,2 1,3,2,3 1,4,3,5,2,5,3,4 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6 Ignoring the left-most column, the common differences are 1, 1, 2, 1, 3, ... which is the sequence itself. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Sun, Oct 15, 2017 at 1:16 AM, <rcs@xmission.com> wrote:
Quoting Neil Sloane <njasloane@gmail.com>:
Stern's diatomic array (A049456) is a triangle in which row n lists the denominators in the n-th row of the table of Farey fractions. Another version of A049456 is the Stern-Brocot sequence (A002487) which has the recurrence a(2n)=a(n), a(2n+1)=a(n)+a(n+1), with a(0)=0, a(1)=1. There are a huge number of references. Someone recently asked me about a sequence which I was able to show was equal to the number of distinct terms in the n-th row of Stern's A049456. Surprisingly, this was not in the OEIS, although it is now - see A293160: 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, ... Can someone find a recurrence? (The smallest positive missing number from row n is A135510, which has an 1850 reference to Eisenstein.)
Some preliminaries to look for clues ...
The ratios of successive terms
2.0 1.5 1.6666666 1.4 1.8571428 1.5384616 1.55 1.548387 1.625 1.5128205 1.6186441 1.5706806 1.55 1.5784947 1.6008174 1.5744681 1.5816216 1.5710868 1.5871221 1.5833334 1.5822369 1.5791115 1.5879153 1.5787222 1.585798
These are mostly an up & down sequence, but with exceptions. The ratios appear to be converging, but slowly, somewhat erraticly. The ratio of term21:term20 is exactly 19:12, rather simple. A simple linear recurrence would have roughly a geometric convergence to the term ratio, similar to the Fibonacci sequence. This sequence doesn't.
The remainders mod 2 and 3 are (1 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0) (1 2 0 2 1 1 2 1 0 0 1 2 0 0 2 2 2 1 1 0 2 2 0 1 2 1) with no obvious periodicity.
The factorizations are "nothing special", with perhaps a minor excess of small factors 2,3,5, and maybe 19. (1 (1)) (2 (2)) (3 (3)) (5 (5)) (7 (7)) (13 (13)) (20 (2 2 5)) (31 (31)) (48 (2 2 2 2 3)) (78 (2 3 13)) (118 (2 59)) (191 (191)) (300 (2 2 3 5 5)) (465 (3 5 31)) (734 (2 367)) (1175 (5 5 47)) (1850 (2 5 5 37)) (2926 (2 7 11 19)) (4597 (4597)) (7296 (2 2 2 2 2 2 2 3 19)) (11552 (2 2 2 2 2 19 19)) (18278 (2 13 19 37)) (28863 (3 3 3 1069)) (45832 (2 2 2 17 337)) (72356 (2 2 18089)) (114742 (2 103 557))
The balanced remainder of the Nth term mod N looks a little unusual. Random would be |average| of N/4; these are a little less. No obvious pattern of the signs.
(1 1 0) (2 2 0) (3 3 0) (4 5 1) (5 7 2) (6 13 1) (7 20 -1) (8 31 -1) (9 48 3) (10 78 -2) (11 118 -3) (12 191 -1) (13 300 1) (14 465 3) (15 734 -1) (16 1175 7) (17 1850 -3) (18 2926 -8) (19 4597 -1) (20 7296 -4) (21 11552 2) (22 18278 -4) (23 28863 -2) (24 45832 -8) (25 72356 6) (26 114742 4)
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Possible guesses at the limiting ratio ... somewhere around 1.58 phi 1.618 too high cbrt(4) 1.5874 a little high log3/log2 1.5849 maybe? but not algebraic 19/12 1.58333 maybe? 12/7 1.5714 too low Rich
participants (2)
-
Neil Sloane -
rcs＠xmission.com