Re: [math-fun] Smallest term in Zeckendorf representation
Fred wrote [of the Wikipedia article on Zeckendorf's theorem]: << Also mentioned there is a "Fibonacci product", . . . with x = \sum_i a_i F_i, y = \sum_j b_j F_j, (*) x(*)y = \sum_{i,j} a_i b_j F_{i+j} . Knuth reputedly proved this operation to be associative, which Wikipedia finds surprising. Apparently it follows immediately from . . . . . . --- so after all, Knuth's theorem is surprising!
I, too, first thought this associativity obvious, merely because addition (of indices) is associative . . . but this is specious (I think) since there's nothing to guarantee the RHS of (*) is in Zeckendorf form (which requires no repeated or consecutive indices). --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
On 5/16/08, Dan Asimov <dasimov@earthlink.net> wrote:
I, too, first thought this associativity obvious, merely because addition (of indices) is associative . . . but this is specious (I think) since there's nothing to guarantee the RHS of (*) is in Zeckendorf form (which requires no repeated or consecutive indices).
A couple of errors (surprise, surprise) crept into a proof I gave, which should read: Uniqueness of the representation is proved by induction: given natural x with F_n <= x < F_{n+1}, assume every natural y < F_n is uniquely representable as a sum of non-consecutive F_k with 1 < k < n; note that no y >= F_n is so representable; apply assumption to y = x - F_n, noting that y < F_{n-1}. The case x = 0 is plainly representable by the empty sum; however, see below ... The theorem on Fibonacci product associativity in Wikipedia turns out even more surprising than I earlier appreciated --- as quoted there, it's false! More precisely for x > 1, (1(*)1) (*) x <> 1 (*) (1(*)x) , x (*) (1(*)1) <> (x(*)1) (*) 1 . I don't know whether Knuth's paper mentions this irritating anomaly, or how to fix it; but the following "base-F'" kludge seems to work. Though the convention k >= 2 employed earlier is the natural one, an alternative is to attach two further digits at the less-significant end, that is summing over k >= 0: with this scheme, we might instead represent (including redundant left-hand zeros) in base-10, 20 = 13+5+2 = F_7 + F_5 + F_3 = ...010101000 in base-F' . There is some arbitrariness about the value of the extra pair --- define them to be 00 for x > 1, but in base-10, 1 = ...0101 in base-F' ; in base-10, 0 = ...0001 in base-F' . [0 could instead be represented by ...0000 --- this would in turn redefine Fibonacci product, from x(*)0 = x to x(*)0 = 0 as originally.] Fred Lunnon
PS --- Fibonacci product table, as defined using base-F' above: __0___1___2___3___4____5____6____7____8____9 __1___3___5___8__11___13___16___18___21___24 __2___5___8__13__18___21___26___29___34___39 __3___8__13__21__29___34___42___47___55___63 __4__11__18__29__40___47___58___65___76___87 __5__13__21__34__47___55___68___76___89__102 __6__16__26__42__58___68___84___94__110__126 __7__18__29__47__65___76___94__105__123__141 __8__21__34__55__76___89__110__123__144__165 __9__24__39__63__87__102__126__141__165__189 WFL
[Allowing x(*)0 = x was a dumb idea, which subsequently turns out to create exceptions to explicit expressions: better to retain the original x(*)0 = 0, by redefining in base-10, 1 = ...0101 in base-F" ; in base-10, 0 = ...0000 in base-F" ; with all other natural numbers ending ...00 . Our third attempt at multiplication x(*)y looks like ____y__0___1___2___3___4____5____6____7____8____9 __x______________________________________________ __0____0___0___0___0___0____0____0____0____0____0 __1____0___3___5___8__11___13___16___18___21___24 __2____0___5___8__13__18___21___26___29___34___39 __3____0___8__13__21__29___34___42___47___55___63 __4____0__11__18__29__40___47___58___65___76___87 __5____0__13__21__34__47___55___68___76___89__102 __6____0__16__26__42__58___68___84___94__110__126 __7____0__18__29__47__65___76___94__105__123__141 __8____0__21__34__55__76___89__110__123__144__165 __9____0__24__39__63__87__102__126__141__165__189 remaining associative without exception.] Looking at column x = 1, it becomes quickly apparent that 1(*)y approximates tau^2*y; with some algebra, it can be shown that explicitly 1(*)y = [tau^2 y + 1/tau] = floor(tau^2*y + 1/tau). [This is just the 2-place left-shift mentioned in connection with Penrose tiling inflation.] Column x = 2 is harder to crack. Subtracting [tau^3 y] gives a sequence with just three values, and tinkering with the offset leads to the binary sequence f(y) = 2(*)y - [tau^3 y - 1/tau^3] = 2(*)y - floor(tau^3*y - 1/tau^3) = 0101101001 0110100101 0010110100 1011010110 1001011010 0101001011 0100101101 0110100101 1010010110 1011010010 ... Sniffing around in OEIS soon turns up A078588, which I'll christen the Chow-Long sequence, with the handy explicit formula CL(y) = 2*{y tau} - {2 y tau} = 2*frac(y*tau)-frac(2*y*tau). Unfortunately, CL(y) is not our sequence f(y). They are locally equal, in the sense that every finite segment of either sequence occurs infinitely often in the other, but globally they are distinct: for instance, the segments (f(0),...,f(70)) = (CL(18),...,CL(89)) coincide maximally. More generally, the earliest occurrence of the initial segment (f(0),...,f(w-1)) occurs at (CL(z),...,CL(z+w-1)), where z = F_{3k}/2 + 1 , w = F_{3k+2} - y . Although the sequences are not integer shifts of one another, their quasi- periodicity and the previous observation permit a striking irrational shift relation to emerge: f(y) = CL(y + 1/(2*tau^4)) ; whence finally 2(*)y = [tau^3 y - 1/tau^3] + CL(y + 1/(2*tau^4)) . Column x = 3 may be reduced in a similar fashion to the ternary sequence g(y) = 3(*)y - [tau^4 y + 1/tau^4] = 1201202012 0121201201 0120120201 2012120120 1012012120 1201012012 0201201212 0120101201 2020120121 2012020120 1212012010 1201202012 0121201201 0120120201 2010120120 2012012120 1201012012 0201201212 0120101201 2120120101 2012020120 1212012010 1201202012 0121 ... which, needless to say, does not appear in OEIS. Well, anyone got any ideas? [Looking in Knuth, perhaps?] Fred Lunnon
On 5/17/08, Fred lunnon <fred.lunnon@gmail.com> wrote:
[Allowing x(*)0 = x was a dumb idea, which subsequently turns out to create exceptions to explicit expressions: better to retain the original x(*)0 = 0, by redefining in base-10, 1 = ...0101 in base-F" ; in base-10, 0 = ...0000 in base-F" ; with all other natural numbers ending ...00 .
Dumber than I imagined. The fiddling about with the final digit turns out to be due to a minor code bug. In fact, _all_ base-F" numbers without exception should end with ...00; fortunately, the table and the rest of the stuff following it above is unaffected. WFL
participants (2)
-
Dan Asimov -
Fred lunnon