From and.Princeton.EDU!conway Sat Nov 23 13:59 EST 1996 Return-Path: Date: Sat, 23 Nov 1996 13:43:37 -0500 (EST) From: John Conway Subject: Re: parFibs. To: njas@research.att.com In-Reply-To: <199611221536.KAA28194@and.Princeton.EDU> Will you please put the name "para-Fibonacci sequence" in the entry for my version? Correspondingly, perhaps something like "Fibonacci paraphrase" should be in Kimberling's. I've been continuing my study of these matters, and thinking about the terminology, the most important new pieces of which are the word "parameter" for the index of a sequence, and (Fibonacci) "successor" for the number Sn you get from a given n by bumping up all terms of its Zeckendorff expansion. Thus the sequence with parameter i can be started from i 1+Si and after that has the shape j Sj SSj SSSj SSSSj ... where j = i + 1 + Si. On Fri, 22 Nov 1996 njas@research.att.com wrote: > >From njas Fri Nov 22 10:31 EST 1996 > To: ck6@cedar.evansville.edu > Cc: njas@research.att.com > Status: R > > hi! some time ago you sent me a paper with the following sequence in it: > > %I A003603 M0138 > %S A003603 1,1,1,2,1,3,2,1,4,3,2,5,1,6,4,3,7,2,8,5,1,9,6,4,10,3,11,7,2,12,8,5,13,1, > %T A003603 14,9,6,15,4,16,10,3,17,11,7,18,2,19,12,8,20,5,21,13,1,22,14,9,23,6,24 > %N A003603 Fractal sequence obtained from Fibonacci numbers. > %R A003603 Kimb94a. > %O A003603 0,4 From and.Princeton.EDU!conway Sun Nov 24 15:41 EST 1996 Return-Path: Date: Sun, 24 Nov 1996 15:13:11 -0500 (EST) From: John Conway Subject: Re: your mail To: njas@research.att.com In-Reply-To: <199611240009.TAA17271@and.Princeton.EDU> On Sat, 23 Nov 1996 njas@research.att.com wrote: > its 7pm saturday, can you give me a call? I've been thinking further about Fibs and Buds. 1) numeration: It seems to me that the columns of Kimberling's array should be numbered as in:- -1 0| 1 2 3 4 5 -------------------- 0 1| 1 2 3 5 8 1 3| 4 7 11 18 29 2 4| 6 10 16 3 6| 9 15 4 8|12 20 5 9|14 23 and that the row with parameter i should be called the ith extra Fibonacci (or extra-Fibonacci) sequence, the numbers after the bar being the ith extraFib numbers. Idea - these sequences (for i > 0) are indeed "extra" Fibonacci sequences, and their terms (after the bar) are "extra-Fibonacci" - that is, outside the Fibonacci sequence. Now I want to point out the relationship with the budding sequences. The table shows n followed by the nth terms of the paraFib sequence Pn and the Left and Right budding sequences Ln and Rn: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Pn 0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 2 6 1 7 4 0 8 5 3 Ln 1 1 3 2 1 5 3 8 5 2 9 5 1 10 5 15 9 3 15 8 21 13 5 20 Rn 1 2 1 3 5 2 5 1 5 9 3 8 13 5 11 2 9 16 5 13 1 10 19 5 Xn 1 1 1 3 1 2 3 1 5 2 3 8 1 5 5 2 9 3 5 8 1 10 5 5 The number Xn is Ln or Rn if Pn is occurring for the kth time and k is respectively odd or even, and you see that Xn is a function of Pn, namely Xn = 1 3 2 5 8 5 9 5 10 15 9 15 21 13 20 ... (***) for Pn = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... I found a recursion for this sequence (***), but am scared of writing it down wrongly, so will stop for now. It's easy to see that each of the budding sequences Ln and Rn consists of the values of (***) repeated in finitely often in a certain way. J WYTHOFF ARRAY From cs.arizona.edu!rcs Mon Nov 25 16:29 EST 1996 Date: Mon, 25 Nov 1996 14:20:11 MST From: "Richard Schroeppel" To: math-fun@cs.arizona.edu Subject: Fibonacci note from Conway This came up on another list. I think it's of more interest here on Math-Fun. My apologies to the common membership for a double-post. --Rich ---------------------- From: John Conway Subject: Re: Fibonacci correction from Achim Date: Mon, 25 Nov 1996 12:51:57 -0500 (EST) This mention of Fibonacci counting prompts me to pass on something about the Fibonacci's that very much excited me when I found it about a week ago. I've since learned that Clark Kimberling found the essential point about 20 years ago. I start with the Zeckendorff expansion of a positive integer, obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains, for example 100 = 89 + 8 + 3. By replacing each Fib in the Zeckendorff expansion of n, you get what I'll call the Fibonacci successor Sn, eg.: S100 = 144 + 13 + 5 = 162. Now the positive integers are linked by this function into an infinity of sequences each satisfying the Fibonacci recursion, namely those after the bar in the table below, which covers all numbers below 100: 0 1| 1 2 3 5 8 13 21 34 55 89 1 3| 4 7 11 18 29 47 76 2 4| 6 10 16 26 42 68 3 6| 9 15 24 39 63 4 8|12 20 32 52 84 5 9|14 23 37 60 97 6 11|17 28 45 73 7 12|19 31 50 81 8 14|22 36 58 94 9 16|25 41 66 10 17|27 44 71 11 19|30 49 79 12 21|33 54 87 13 22|35 57 92 14 24|38 62 15 25|40 65 16 27|43 70 17 29|46 75 18 30|48 78 19 32|51 83 20 33|53 86 21 35|56 91 22 37|59 96 23 38|61 99 24 40|64 25 42|67 26 43|69 27 45|72 28 46|74 29 48|77 30 50|80 31 51|82 32 53|85 33 55|88 34 56|90 35 58|93 36 59|95 37 61|98 38 63| The topmost series is the Fibonacci series itself: I call the n'th one beneath it the n'th extra Fibonacci sequence. It occurs to me that "n'th higher Fibonacci sequence" might be better. The 0'th higher Fib sequence is of course the Fib sequence itself. Of course each of these sequences can be continued indefinitely far to the left, and I continued them two places left in the table, because then, as you can see, the leftmost column contains the parameter n just defined. It's a very nice fact that EVERY sequence that satisfies the Fibonacci recurrence and ends up with positive integers is one of this neatly-parameterized family. This leads us to what I call the "para-Fibonacci sequence), which for every positive integer gives the parameter of the Fib-sequence that contains that integer (after the bar): (A019586) 0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 2 6 1 7 4 0 8 5 3 9 2 10 6 1 11 7 4 12 0 13 0,0,0,1,0,2,1,0,3,2,1,4,0,5,3,2,6,1,7,4,0,8,5,3,9,2,10,6,1,11,7,4,12,0,13 Kimberling called the sequence whose terms are 1 larger than these "the paraphrase of the Fibonnaci numeration system". (A003603) This (A019586) has very nice properties - for example between any two 0's we see a permutation of the first few positive integers, and these nest, so we can read the paraFib sequence from: 0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 2 6 1 7 4 0 8 5 3 9 2 10 6 1 11 7 4 12 Also - if you delete the first occurrence of each number [from A019586], the sequence is unchanged. There are many intriguing problems here, of which I'll mention just two: 1) Reading the nth sequence backwards, we obtain the negative of another. Which? 2) Multiplying the terms of the nth sequence by some positive integer d, we obtain those of another. Which? (The reason I prefer my version to Kimberling's is that the answer to this must be some multiple of d.) I only just thought of 1). About 2) I note that multiplying the Fib sequence by 2,3,4, 5, 6, 7, 8, 9,10,11 we get sequences numbers 2,3,4,15,18,21,24,27,30,33, A269725 and that the double of the 7th sequence comes before that of the 5th. I have long been interested in what I call the "budding sequences", which tell you where the successive buds on suitable kinds of plant are located. The paraFib sequence helps to explain many properties of these, and shows that they each consist of the terms of the rather mysterious sequence 1, 3, 2, 5, 8, 5, 9, 5, 10, 15, 9, 15, 21, 13, 20, ... repeated infinitely often in systematic ways. However, to explain these matters here would take me as much time again, and I want to have some lunch now! John Conway From and.Princeton.EDU!conway Mon Dec 2 17:02 EST 1996 Return-Path: Date: Mon, 2 Dec 1996 15:52:17 -0500 (EST) From: John Conway Subject: Fibs and postFibs To: Allan Wechsler Cc: math-fun@cs.arizona.edu [For new readers: this is about a remarkable parametrization of all the sequences of integers satisfying the Fibonacci recurrence and tending to infinity. To be precise, the ith "post-Fibonacci sequence" Fi has i and S(i) + 1, where to get S(i) you express i as a sum of minimally many Fibonacci numbers, and then replace each of these by the next higher one. For instance, 10 = 8+2, and so S(10) = 13+3 = 16, and so the 10th postFib sequence F10 is ... 11, -6, 5, -1, 4, 3, 7, 10, 17, 27 44, 71, 115, 186, ... ^^^^^^ obtained from the underlined terms 10, S(10)+1. I raised two questions: 1) For any m, we obtain a postFib sequence by multiplying Fi by m. What is the rule governing the parameters of these? Thus on multiplying the standard Fib sequence F0 by 1 2 3 4 5 6 7 8 9 10 11 12 13 we get F0, F2, F3, F4, F15, F18, F21, F24, F27, F30, F33, F96, F104,... and in a similar way we get F1 F8 F12 F44 F55 F66 F77 F88 F261 F290 F319 F348 F377 1,8,12,44,55,66,77,88,261,290,319,348,377 A269726. from the Lucas sequence F1. 2) If we reverse Fi and negate alternate terms we again get some postFib sequence Fj. How does j relate to i?] Now read on: About the sequence mFi = FM. In the two examples, we see that M is always a multiple of m, namely M/m = 0 1 1 1 3 3 3 3 3 3 3 8 8 ... for the Fib sequence, and 1 4 4 11 11 11 11 11 29 29 29 29 29 ... for the Lucas sequence. More generally, we can prove that in general when we write mFi = FM, for some M = M(i,m), then always M/m will be a member of the Fi sequence, that only alternate terms of the Fi sequence are so used, and that M/m stays constant for longer and longer stretches. This follows by thinking about the diagram whose (x,y) entry is the parameter of the postFib sequence defined by the two consecutive terms x, y :- >88 >77 >66 0 5 10 15 20/ 9 11 13 15/ 6 7/(0) 5/15 16 17/49 52>55 58 61 64 67/ 2 7/ 4 6 8 10/ 4 5/ 2( 1) 4/13 14/41>44 47 50 53 56 59/ 1 3 5 7/ 3/ 1( 0) 3/10 11>12/36 39 42 45 48 51/ 5,8 0 2/ 1 2/(0) 2/ 7 >8 9/28 31 34 37 40 43 46/ 0/ 0( 0)>1/ 5 6/20 23 26 29 32 35 38/ 2,3 (*) 0/ 2 3 4/15 18 21 24 27 30 33/96 0 1/ 7 10 13 16 19 22 25/75 83 91 99 1,1 2 5 8 11 14 17/54 62 70 1,0 0 3 6 9 12/41 49 57 65 73 0,1 1 4/20 28 36 44 52 60 1,2 7 15 23 31 39 47 2 10 18 26 34 3,5 5 13 21 0 8 8,13 I've drawn "straight" lines to indicate various strips, in each of which the entry takes a fixed form ax+by, and have indicated the values (a,b) beneath these. Since it can be hard to see which /'s belong to which lines, the central "lane" is indicated instead by brackets. The entire picture is invariant under squashing by a factor of tau = (1+root5)/2 in the (1,tau) direction and simultaneously expanding by a factor of -tau in the orthogonal (-tau,1) direction. Each strip except the central one, which I'm therefore calling a lane rather than a strip, has one copy of each natural number 0,1,2,3,..., these being entered according to their distance from the boundary line y = -x/tau. I forgot to say that (*) marks the origin. To see how this implies the statements, consider the multiples of (for example) the vector (2,1). I've picked out the corresponding entries with > marks, which march by knight's moves rightwards across the successive strips. You'll see that for the two values m = 2 and m = 3 these land in the (1,2) strip, yielding F8 and F12 for the 2nd and 3rd multiples of F1, but then that the next five are in the (3,5) strip, yielding F44, F55, F66, F77, F88, after which we land for quite same time in the (8,13) strip, yielding various FM for M/m = 29, and so on. That's all for now. I hope someone can understand it! Forthcoming attraction: we explain why the sequence 0,1,2,3,4,7,10,5,8,11,6,9,12,20,28,15,23,31,,, that gives the parameter values for reversed Fib sequences, has differences 1,1,1,1,3,3,-5,3,3,-5,3,3,8,8,-13,8,8,-13,... that are all Fibonacci numbers (up to sign). John Conway From spork.bbn.com!awechsle Wed Dec 4 16:44 EST 1996 Date: Wed, 4 Dec 1996 16:31:27 -0500 (EST) From: Allan Wechsler Here are some thoughts on generalized Fibonacci sequences. Consider the field Q[phi]. Since phi is irrational, any element p + q phi is uniquely determined by p and q. Now consider the function K(x) = phi x. If x = p + q phi, then K(x) = p phi + q phi^2 = q + (p+q) phi. In other words, multiplying by phi performs the Fibonacci transform on p and q. (This is where our intuition comes from, that stepping down the Fibonacci sequence is "like" multiplying by phi.) Now consider the function J : Q[phi] -> Q defined by J(p + q phi) = pp + pq - qq [= p^2 +p*q - q^2] A little arithmetic reveals that J(K(x)) = -J(x). Intuitively, every generalized Fibonacci sequence rides a "J track", with |J| fixed. The classical Fibonacci sequence has |J| = 1. Its multiples have |J| in {1, 4, 9, 16, 25, ...}. The Lukas sequence has |J| = 5. It would be nice if |J| _characterized_ a given sequence. Unfortunately, this is not the case. Even among integer sequences, the 3, 1, 4, 5, 9, ... and 3, 2, 5, 7, 12 ... share |J| = 11. It is interesting that J preserves multiplication, that is, that J(xy) = J(x)J(y). I don't have any real sense for how Conway's parameterization of Fibonacci sequences relates to J. Here is a brief table of the J's for the first few Fi's. n |J(Fn)| 0 1 1 5 2 4 3 9 4 16 5 11 6 19 7 11 8 20 9 31 10 19 11 31 12 45 13 29 14 44 15 25 16 41 17 59 18 36 19 55 Notice the multiplicative relationship: F1.F5=F19. -A From well.com!mlb Wed Jan 8 20:44 EST 1997 Date: Wed, 08 Jan 1997 17:32:45 -0800 To: John Conway From: Marc Le Brun Subject: Re: Fibs Cc: math-fun@cs.arizona.edu > Sorry I've been away for so long. I like your comments below, >which effectively replace a fixed Fib sequence with a number >from the "Golden ring", multiplied by all units, if we identify >a sequence with its negative. So (in this new sense) the Fib >sequences correspond one for one with Golden integers modulo >units. However, there is another way to parametrize these, >namely by choosing "the simplest" totally positive unit. I must >think about the relation between this way and "my" (really >Kimberling's) way. JHC Multiples of the sequences are a sub-case of adding sequences, so perhaps it might make sense to look at their "addition table"? But note that there are really two parameters that describe the result of such an addition: the Kimberling index of the sum, and also the amount by which the sum sequence is shifted. That is, K0+K1 (ie Fibbonacci + Lukas) is K5, but it's shifted over 2 places from its "index position"--that is, K0[n]+K1[n]=K5[n-2]. So to fully describe additions, we would want to account for the index and shift of both sums and summands: Ix,Sx + Iy,Sy = Iz,Sz. (I've been meaning to compute and post tables of these I and S values ever since this thread appeared, but the process keeps producing new sequences I feel compelled to send to superseeker! I'll try to do it Real Soon...) Anyway, if we use pairs to desribe these sequences, there are of course a lot of alternatives to the "standard" registration. For example, I think another pretty property is that every a,b appears just once. So we could, for example, instead "register" them by lining up each Ki on the smallest pairs such that 0<=Ki[n]<=Ki[n+1]. Question: can we somehow describe the shift distance between this "least positive pair" and the Kimberling index? Whatever, we might want to restate the problem as that of characterizing a relationship between I,S pairs and a,b pairs in such a way that we can describe the I,S of sums a+c,b+d. From well.com!mlb Fri Jan 10 19:15 EST 1997 Date: Fri, 10 Jan 1997 16:01:59 -0800 To: math-fun@cs.arizona.edu From: Marc Le Brun Subject: kim-sum Here's the "Kimberling sum" addition table from K0+K0 up to K25+K25 (with row and column labels) It also seems that the shift is ALWAYS by 2 places (I'm not sure why I thought it varied). Kim+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39 41 44 47 49 52 54 57 60 62 65 68 1 5 8 10 13 16 18 21 23 26 29 31 34 37 39 42 44 47 50 52 55 57 60 63 65 68 71 2 7 10 4 15 18 20 23 9 28 31 12 36 39 41 44 17 49 52 54 57 22 62 65 25 70 73 3 10 13 15 18 21 23 26 28 31 34 36 39 42 44 47 49 52 55 57 60 62 65 68 70 73 76 4 13 16 18 21 24 26 29 31 34 37 39 42 45 47 50 52 55 58 60 63 65 68 71 73 76 79 5 15 18 20 23 26 28 31 12 36 39 41 44 47 49 52 54 57 60 62 65 25 70 73 75 78 81 6 18 21 23 26 29 31 34 36 39 42 44 47 50 52 55 57 60 63 65 68 70 73 76 78 81 84 7 20 23 9 28 31 12 36 14 41 44 17 49 52 54 57 22 62 65 25 70 27 75 78 30 83 86 8 23 26 28 31 34 36 39 41 44 47 49 52 55 57 60 62 65 68 70 73 75 78 81 83 86 89 9 26 29 31 34 37 39 42 44 47 50 52 55 58 60 63 65 68 71 73 76 78 81 84 86 89 92 10 28 31 12 36 39 41 44 17 49 52 54 57 60 62 65 25 70 73 75 78 30 83 86 33 91 94 11 31 34 36 39 42 44 47 49 52 55 57 60 63 65 68 70 73 76 78 81 83 86 89 91 94 97 12 34 37 39 42 45 47 50 52 55 58 60 63 66 68 71 73 76 79 81 84 86 89 92 94 97 100 13 36 39 41 44 47 49 52 54 57 60 62 65 68 70 73 75 78 81 83 86 33 91 94 96 99 102 14 39 42 44 47 50 52 55 57 60 63 65 68 71 73 76 78 81 84 86 89 91 94 97 99 102 105 15 41 44 17 49 52 54 57 22 62 65 25 70 73 75 78 30 83 86 33 91 35 96 99 38 104 107 16 44 47 49 52 55 57 60 62 65 68 70 73 76 78 81 83 86 89 91 94 96 99 102 104 107 110 17 47 50 52 55 58 60 63 65 68 71 73 76 79 81 84 86 89 92 94 97 99 102 105 107 110 113 18 49 52 54 57 60 62 65 25 70 73 75 78 81 83 86 33 91 94 96 99 38 104 107 109 112 115 19 52 55 57 60 63 65 68 70 73 76 78 81 84 86 89 91 94 97 99 102 104 107 110 112 115 118 20 54 57 22 62 65 25 70 27 75 78 30 83 86 33 91 35 96 99 38 104 40 109 112 43 117 120 21 57 60 62 65 68 70 73 75 78 81 83 86 89 91 94 96 99 102 104 107 109 112 115 117 120 123 22 60 63 65 68 71 73 76 78 81 84 86 89 92 94 97 99 102 105 107 110 112 115 118 120 123 126 23 62 65 25 70 73 75 78 30 83 86 33 91 94 96 99 38 104 107 109 112 43 117 120 46 125 128 24 65 68 70 73 76 78 81 83 86 89 91 94 97 99 102 104 107 110 112 115 117 120 123 125 128 131 25 68 71 73 76 79 81 84 86 89 92 94 97 100 102 105 107 110 113 115 118 120 123 126 128 131 134 From well.com!mlb Wed Jan 15 12:23 EST 1997 Date: Wed, 15 Jan 1997 08:58:32 -0800 To: math-fun@cs.arizona.edu From: Marc Le Brun Subject: More about Kimberling sums This is a consolidated report on some stuff I and others (eg ACW, NJAS et al) have observed about the interesting Fibonaccioid recurrences JHC introduced us to back on 25 Nov 96. Definitions: Let Kn be the n-th Kimberling sequence, defined by Kn[0] = n Kn[1] = An Kn[i] = Kn[i-1] + Kn[i-2] for all non-negative integers n and all integers i, where An = floor[(n+1)*tau]. Also, let KnSs be the n-th Kimberling sequence shifted by the integer s, that is, KnSs[i] = Kn[i-s] (thus (the unshifted) Kn is KnS0 etc). (K0[i] is the Fibbonacci numbers, K1[i] is the Lukas sequence, Kn[1]=An, Kn[2] is the "odd Fibbinary" ie Zeckendorf expansions with ...+F1=...+1 etc). Specifics: I swipe JHC's tableaux, decorating and shortening it a little, extending it to the left, and retaining the "bar" between Kn[1] and Kn[2]: i ...-2 -1 0 1 2 3 4 5 6 7 8 9 10 11 ... Kn: n: An: * * * * * ... K0 ... 0 1| 1 2 3 5 8 13 21 34 55 89 ... K1 ... 1 3| 4 7 11 18 29 47 76 ... K2 ... 0 2 2 4| 6 10 16 26 42 68 ... K3 ... 0 3 3 6| 9 15 24 39 63 ... K4 ... 0 4 4 8|12 20 32 52 84 ... K5 ... 1 4 5 9|14 23 37 60 97 ... K6 ... 1 5 6 11|17 28 45 73 ... K7 ... 2 5 7 12|19 31 50 81 ... K8 ... 2 6 8 14|22 36 58 94 ... K9 ... 2 7 9 16|25 41 66 ... K10 ... 3 7 10 17|27 44 71 ... K11 ... 3 8 11 19|30 49 79 ... K12 ... 3 9 12 21|33 54 87 ... K13 ... 4 9 13 22|35 57 92 ... K14 ... 4 10 14 24|38 62 ... K15 ... 5 10 15 25|40 65 ... K16 ... 5 11 16 27|43 70 ... K17 ... 5 12 17 29|46 75 ... K18 ... 6 12 18 30|48 78 ... K19 ... 6 13 19 32|51 83 ... K20 ... 7 13 20 33|53 86 ... K21 ... 7 14 21 35|56 91 ... K22 ... 7 15 22 37|59 96 ... K23 ... 8 15 23 38|61 99 ... K24 ... 8 16 24 40|64 ... K25 ... 8 17 25 42|67 ... K26 ... 9 17 26 43|69 ... ... (Warning: error-prone, manually transcribed!) Kimberling Sum: As a baby step towards understanding things like scaling (ie m*KnS0=KpSs), we construct Kimbering sum sequences of unshifted summands Kp+Kq=KrSs, and attempt to characterize r,s in terms of p,q. Conjecture: Usually, r = p + q + Ap + Aq s = 2 but in certain exceptional cases (defined below) r = p + q s = 0. (Apology: I recently wrongly implied that there weren't exceptions--sorry!) Exceptions: Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,... (Z may connote the opposite of A, zero shift, or Zeckendorf). * The exceptions are when BOTH p and q ARE in Zn, BUT p+q is NOT in Zn. (Thus K2+K2=K4S0 *is* an exception, because 2+2=4 *isn't* in Zn, but K2+K5=K20S2 *isn't* an exception, because 2+5=7 *is* in Zn). Caveat: One might assume that the scalar multiple m*Kn is determined by the foregoing, but we've only treated the case where the summands are unshifted. However a sum is *usually* shifted, so iterating an incrementation needs to address shifting... These cases aren't covered by the conjecture here! Fun things to find or prove: * That the definition of An implies that every positive integer appears "to the right of the bar" exactly once (that is, An as defined really does generate the Kimberling sequences!) * The conjecture above. * The general case where the summand's relative shift is non-zero. * That Zn is the union of the starred columns (ie Zn = U Kn[2*i+1], i>0) From AIC.NRL.Navy.Mil!hoey Thu Jan 16 19:08 EST 1997 Return-Path: Date: Thu, 16 Jan 97 18:54:27 EST From: Dan Hoey To: math-fun@cs.arizona.edu Subject: Re: More about Kimberling sums Marc Le Brun summarized the directions in which he, ACW, NJAS, have been Kimberled: > Let Kn be the n-th Kimberling sequence, defined by > Kn[0] = n > Kn[1] = An > Kn[i] = Kn[i-1] + Kn[i-2] > for all non-negative integers n and all integers i, where > An = floor[(n+1)*tau]. Thank you thank you! I was hoping for a closed-form expression for Kn[1]--John uses methods that seem to require looking over the earlier sequences for missing elements. > Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,... > (Z may connote the opposite of A, zero shift, or Zeckendorf). Zn seems to be just those n for which (n+1)tau - An < 1/tau--i.e. (n+1)tau mod 1 is less than 1/tau. Now I'd think it should be possible to show why A[p+q] = Ap + Aq exactly when p,q but not p+q are in Zn, and otherwise A[p + q + Ap + Aq] = p + q + 2Ap + 2Aq, which would yield the conjecture. But I'm not getting anywhere with it. Allan's J function easy to calculate here, too. He wrote J(p + q phi) = pp + pq - qq but did you notice J(p + q phi) = (p + q phi)(p - q/phi). The latter may interact better with the closed form for An. Allan mentioned that J(F5)=J(F7)=11, and somehow I hoped that was some sort of pairing instead of an arbitrary multiplicity. Unfortunately J(F33)=J(F45)=J(F65)=121, and 6061 is the J of sequences 1860, 1941, 2171, 2388, 2932, 3225, 3607, and 3764. There are more examples of all multiplicities up to 8 among the first 10000 sequences. Dan Hoey@AIC.NRL.Navy.Mil From well.com!mlb Thu Jan 16 22:48 EST 1997 Date: Thu, 16 Jan 1997 19:33:30 -0800 To: John Conway From: Marc Le Brun Subject: Re: More about Kimberling sums Cc: math-fun@cs.arizona.edu > I'm sorry, I thought I'd given the closed forms for >the general "Kimberling sequence". I certainly knew them. (I've hoped that if I sent junk mail long enough it would provoke you into divulging such secrets! <;-) >but may I say that I still prefer my name "(higher) Fibonacci >sequence", because it's more likely to suggest the meaning, >and because these sequences have long been called the "other" >Fibonacci sequences. I'm easy (as long as the name doesn't include parentheses!). I'd also like to settle on a symbol to use for the n-th sequence, and Fn is already taken for the n-th term of the 0-th sequence (ie the "vanilla" Fibonaccis). OK, let's call them the Higher Fibonaccis and use Hn[k] to mean the k-th term of the n-th sequence. >really GREAT sequence that Kimberling found is his "parafibonacci" >sequence. This is my name, intended to recall the fact that it gives >the parameter of the appropriate (higher) Fib sequence. Yes! But I (and maybe others) have wanted to get sufficient understanding of the HFs before moving on to the later stuff in your message, such as "Pn". This may all be obvious, but it sure felt like you pulled a rabbit out of a hat! You constructed the HFs by crafting sequences to cover the integers, took them two steps backwards and... Fibonacadabra! there's the parameter! > I think I defined the Fibonacci inflation function n+ by >pumping up the terms in Zeckendorff's expansion as a sum of >Fib numbers? You can also define it by multiplying n by >the golden number tau (= phi) and then rounding this >"goldenly" (you should be able to work out what this means). Right, generating the stuff "after the bar" is pretty straightforward. >The two terms "before" the n'th fib sequence are n and 1 + n+, >from which you can work out the general term. Also. What is only slowly becoming clear is *why* this is so. That is, why should exactly this choice of the term after the parameter result in this tidy covering of the integers? I'm groping towards something expressed via Beatty sequences, but I'm certainly not there yet. Do you have a nice explanation (or could you pass on Kimberling's?) Note that, in Zeckendorfland, the way to get the first two terms right after the parameter is a different construction than just the inflating that you do from then on. And, in fact, while there *may* be a "construction" that takes you further to the *left* of the parameter, there's clearly no inverse to take you back to the parameter, because you start to get repeated values in those columns. > When I saw the conjecture about adding these sequences, it >was obvious that something like it should be easily provable. >A given sequence "starts" at the first term for which the error >satifies certain inequalities, and you just have to see what >inequalities for the sum follow from those for the summands. >I bet there's a very clean exact determinantion of the shift. Oh, feel free to supply one anytime; I'm still plodding toward it. I note that the "exceptional" sequence is the "Beatty-dual" of the first column, so there's a complement of the conjecture in terms of [n*tau] instead of [n*tau^2], but I don't know if this is of any more use than a dog biscuit. Really, isn't this is all pretty provocative? It implies that, for example, adding two Hn(x)=(n+xAn)/(1-x-x^2) will have one of exactly two forms (ie the vanilla or the shifted one), as determined by this wacky rule. The addition operation commutes but apparently doesn't associate. I was hoping by including a shift it would have some nice structure (recall that this would extend the wackiness to cover *all* such recurrences). > Did I send out the "Empire State" table? This defines >a natural "central term" for a doubly-infinite fib sequence, >and shows how to find this from the "starting term". The >central term is midway between the starting terms of the sequence >and its "reverse" (with alternate signs changed). Unfortunately, >the central term of a doubled sequence (say) need not be the >double of the central term of the original. This all sounds new--please send whatever you have! > I don't know if I sent out my stuff on how to find the >parameters of multiplied sequences? If not, I'll try to >dig it up. By multiplied I assume you mean as in your original question--which I'd now prefer to call "scaled", if it's OK with you to ask a terminological return favor. (There's at least one other kind of "multiplied" that you can get when you represent them as homographic (aka bilinear rational) functions <--> 2x2 matrices, where function composition corresponds to matrix multiply.) (OK, I'll confess, my secret desire is that HF addition will suggest some new kind of HF multiplication HF*HF that distributes etc) > What I like about all this is that it's really not very often >that one sees anything really new and interesting about Fibonacci >numbers and the like. This not only feels new, but it's also >a large and interesting theory, rather than an isolated observation! > > John Conway From and.Princeton.EDU!conway Thu Jan 16 20:08 EST 1997 Return-Path: Date: Thu, 16 Jan 1997 19:20:38 -0500 (EST) From: John Conway Subject: Re: More about Kimberling sums To: Dan Hoey Cc: math-fun@cs.arizona.edu In-Reply-To: <9701162354.AA17256@sun13.aic.nrl.navy.mil> I'm sorry, I thought I'd given the closed forms for the general "Kimberling sequence". I certainly knew them. By the way, I don't want to deprive Clark Kimberling of his credit, but may I say that I still prefer my name "(higher) Fibonacci sequence", because it's more likely to suggest the meaning, and because these sequences have long been called the "other" Fibonacci sequences. In general naming things after people is less helpful than naming them by their properties. Of course "Fibonacci" is a name, but so standard that it already suggests a meaning! The really GREAT sequence that Kimberling found is his "parafibonacci" sequence. This is my name, intended to recall the fact that it gives the parameter of the appropriate (higher) Fib sequence. I think I defined the Fibonacci inflation function n+ by pumping up the terms in Zeckendorff's expansion as a sum of Fib numbers? You can also define it by multiplying n by the golden number tau (= phi) and then rounding this "goldenly" (you should be able to work out what this means). The two terms "before" the n'th fib sequence are n and 1 + n+, from which you can work out the general term. When I saw the conjecture about adding these sequences, it was obvious that something like it should be easily provable. A given sequence "starts" at the first term for which the error satifies certain inequalities, and you just have to see what inequalities for the sum follow from those for the summands. I bet there's a very clean exact determinantion of the shift. Did I send out the "Empire State" table? This defines a natural "central term" for a doubly-infinite fib sequence, and shows how to find this from the "starting term". The central term is midway between the starting terms of the sequence and its "reverse" (with alternate signs changed). Unfortunately, the central term of a doubled sequence (say) need not be the double of the central term of the original. I don't know if I sent out my stuff on how to find the parameters of multiplied sequences? If not, I'll try to dig it up. What I like about all this is that it's really not very often that one sees anything really new and interesting about Fibonacci numbers and the like. This not only feels new, but it's also a large and interesting theory, rather than an isolated observation! John Conway On Thu, 16 Jan 1997, Dan Hoey wrote: > Marc Le Brun summarized the directions in which he, > ACW, NJAS, have been Kimberled: > > > Let Kn be the n-th Kimberling sequence, defined by > > Kn[0] = n > > Kn[1] = An > > Kn[i] = Kn[i-1] + Kn[i-2] > > for all non-negative integers n and all integers i, where > > An = floor[(n+1)*tau]. > > Thank you thank you! I was hoping for a closed-form expression for > Kn[1]--John uses methods that seem to require looking over the earlier > sequences for missing elements. > > > Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,... > > (Z may connote the opposite of A, zero shift, or Zeckendorf). > > Zn seems to be just those n for which (n+1)tau - An < 1/tau--i.e. > (n+1)tau mod 1 is less than 1/tau. Now I'd think it should be > possible to show why A[p+q] = Ap + Aq exactly when p,q but not p+q are > in Zn, and otherwise A[p + q + Ap + Aq] = p + q + 2Ap + 2Aq, which > would yield the conjecture. But I'm not getting anywhere with it. > > Allan's J function easy to calculate here, too. He wrote > > J(p + q phi) = pp + pq - qq > > but did you notice > > J(p + q phi) = (p + q phi)(p - q/phi). > > The latter may interact better with the closed form for An. Allan > mentioned that J(F5)=J(F7)=11, and somehow I hoped that was some sort > of pairing instead of an arbitrary multiplicity. Unfortunately > J(F33)=J(F45)=J(F65)=121, and 6061 is the J of sequences 1860, 1941, > 2171, 2388, 2932, 3225, 3607, and 3764. There are more examples of > all multiplicities up to 8 among the first 10000 sequences. > > (P.S. Allan is evidently a phi-lologist. Is there a name for the > folks who say tau? Me, I want to stay neutral, even if it costs me > two Greek letters.) > > Dan > Hoey@AIC.NRL.Navy.Mil From AIC.NRL.Navy.Mil!hoey Fri Jan 17 19:11 EST 1997 Return-Path: Date: Fri, 17 Jan 97 19:02:16 EST From: Dan Hoey To: math-fun@cs.arizona.edu Subject: Inverse higher-fib/Kimberling table For those of us who may not have found all the neat things in the table John Conway posted on 2 December, here's a slight extension, mostly done by computer. For a given x,y it shows the index of the unique higher Fibonacci sequence that contains ...,x,y,.... Blanks spaces to the north and east are sequences above H99. The blank southwest halfplane is for the sequences below H0 (they would be unreversed negatives of the positive sequences, I guess, but I'm not sure they fit the scheme). \x -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 y\ 23 / '85 87 89 91/35 36'(5)23' 22 / '80 82 84 86/33 34'13 (8)22' 21 / '77 79 81 83/32'12 (0)21'57 20 / '72 74 76 78/30 31'(4)20'54 55 19 / '67 69 71 73 75/29'11 (7)19'52 53/ 18 / '64 66 68 70/27 28'(1)18'49 50 51/ 17 / '59 61 63 65/25 26'10 (6)17'47 48/ 16 /88 93 98 '56 58 60 62/24' 9 (2)16'44 45 46/ 15 /80 85 90 95 '51 53 55 57/22 23'(3)15'41 42 43/ 14/67 72 77 82 87 92 97 '46 48 50 52 54/21' 8 (5)14'39 40/ 13/59 64 69 74 79 84 89 94 99 '43 45 47 49/19 20'(0)13'36 37 38/ 12 51 56 61 66 71 76 81 86 91 96'38 40 42 44/17 18' 7 (4)12'34 35/96 99 11 43 48 53 58 63 68 73 78 83'33 35 37 39 41/16' 6 (1)11'31 32 33/91 94 97 10 35 40 45 50 55 60 65 70 75'30 32 34 36/14 15'(2)10'28 29 30/83 86 89 92 95 9 27 32 37 42 47 52 57 62'25 27 29 31/12 13' 5 (3) 9'26 27/75 78 81 84 87 90 8 19 24 29 34 39 44 49 54'22 24 26 28/11' 4 (0) 8'23 24 25/70 73 76 79 82 85 7 11 16 21 26 31 36 41'17 19 21 23/ 9 10'(1) 7'20 21 22/62 65 68 71 74 77 80' 6 3 8 13 18 23 28'12 14 16 18 20/ 8' 3 (2) 6'18 19/54 57 60 63 66 69 72' 5 0 5 10 15 20' 9 11 13 15/ 6 7'(0) 5'15 16 17/49 52 55 58 61 64 67' 4 2 7' 4 6 8 10/ 4 5' 2 (1) 4'13 14/41 44 47 50 53 56 59' 3 ' 1 3 5 7/ 3' 1 (0) 3'10 11 12/36 39 42 45 48 51' 2 5,8 ' 0 2/ 1 2'(0) 2' 7 8 9/28 31 34 37 40 43 46' 1 ' / 0' 0 (0) 1' 5 6/20 23 26 29 32 35 38' 0 ' 2,3 / '(*) 0' 2 3 4/15 18 21 24 27 30 33'96 -1 ' / 1,1 '( ) ' 0 1/ 7 10 13 16 19 22 25'75 83 91 99 -2 ' / '1,0( ) ' / 2 5 8 11 14 17'54 62 70 78 86 94 -3 ' / '( )0,1' 1,2 / 0 3 6 9 12'41 49 57 65 73 81 -4' / ' ( ) ' / 1 4'20 28 36 44 52 60 68 -5' / ' ( ) ' / 3,5 ' 7 15 23 31 39 47 55 -6 / '( ) ' / ' 2 10 18 26 34 42 -7 / ' ( ) ' / ' 5 13 21 29 -8 / '( ) ' / ' 8,13 0 8 16 Star * marks the origin. The strips are demarcated by / and ' in lines of slope tau to make it easier to track them near the center. Remember each strip contains all the nonnegative integers, once, as a linear function of the coordinates. The most important item in the extension is that I've continued the central lane (in parens()) far enough to see the nice surprise it contains. Apologies for the spoiler to anyone else who hasn't noticed it in the last month and a half. Dan