May 2008 - mathfun@mailman.xmission.com

Re: [math-fun] Smallest term in Zeckendorf representation
by N. J. A. Sloane 18 May '08

18 May '08

WFL said on May 16: 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 Me: I am reading these messages in reverse order. This looks like an interesting array that should be in the OEIS (converted to a sequence by being read by antidaigonals). Fred, is it correct? If so, could you please linearize it and send it in the OEIS along with a definition? (In return for my telling you about A101330!) Thanks! Best regards Neil

2 1

Re: [math-fun] Smallest term in Zeckendorf representation
by N. J. A. Sloane 17 May '08

17 May '08

WFL said: 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 Me: Isn't that Knuth's product? Remember that arrays are stored in the OEIS by antidiabgonals. Neil %I A101330 %S A101330 3,5,5,8,8,8,11,13,13,11,13,18,21,18,13,16,21,29,29,21,16,18,26,34, %T A101330 40,34,26,18,21,29,42,47,47,42,29,21,24,34,47,58,55,58,47,34,24,26, %U A101330 39,55,65,68,68,65,55,39,26,29,42,63,76,76,84,76,76,63,42,29,32,47 %N A101330 Array read by antidiagonals: T(n,k) = Knuth's Fibonacci (or circle) product of n and k ("n o k"). %C A101330 Let n = Sum_{i >= 2} eps(i) Fib_i and k = Sum_{j >= 2} eps(j) Fib_j be the Zeckendorf expansions of n and k, respectively (cf. A035517, A014417). (The eps(i) are 0 or 1, and no two consecutive eps(i) are both 1.) Then the Fibonacci (or circle) product of n and k is n o k = Sum_{i,j} eps(i)*eps(j) Fib_{i+j} (= T(n,k)). %C A101330 The Zeckendorf expansion can be written n=sum_{1<=i<=k} F(a_i), where a_{i+1} >= a_i + 2. In this formulation, the product becomes: if n = sum_{1<=i<=k} F(a_i) and m = sum_{1<=j<=l} F(b_j) then n o m = sum_{i=1}^k sum_{j=1}^l F(a_i + b_j). %C A101330 Knuth shows that this multiplication is associative. This is not true if we change the product to n x k = Sum_{i,j} eps(i)*eps(j) Fib_{i+j-2}, see A101646. Of course 1 is not a multiplicative identity here, whereas it is in A101646. %C A101330 The papers by Arnoux, Grabner et al. and Messaoudi discuss this sequence and generalizations. %D A101330 P. Arnoux, Some remarks about Fibonacci multiplication, Appl. Math. Lett. 2 (1989), 319-320. %D A101330 P. Grabner et al., Associativity of recurrence multiplication, Appl. Math. Lett. 7 (1994), 85-90. %D A101330 D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60. %D A101330 A. Messaoudi, Generalisation de la multiplication de Fibonacci, Math. Slovaca, 50 (2) (2000), 135-148. %D A101330 A. Messaoudi, Tribonacci multiplication, Appl. Math. Lett. 15 (2002), 981-985. %H A101330 T. D. Noe, <a href="http://www.research.att.com/~njas/sequences/b101330.txt">Rows n=1..100 of array, flattened</a> %H A101330 Ali Messaoudi, <a href="http://almira.math.u-bordeaux.fr/jtnb/1998-1/messaoudi.ps">Title?</a> %H A101330 Vincent Canterini and Anne Siegel, <a href="http://www.ams.org/tran/2001-353-12/S0002-9947-01-02797-0/home.html">Geometric representation of substitutions of Pisot type</a>, Trans. Amer. Math. Soc. 353 (2001), 5121-5144. %e A101330 Array begins: %e A101330 3 5 8 11 13 ... %e A101330 5 8 13 18 ... %e A101330 8 13 21 ... %e A101330 11 18 ... %e A101330 13 ... %t A101330 zeck[n_Integer] := Block[{k = Ceiling[ Log[ GoldenRatio, n*Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; FromDigits[fr]]; kfp[n_, m_] := Block[{y = Reverse[ IntegerDigits[ zeck[ n]]], z = Reverse[ IntegerDigits[ zeck[ m]]]}, Sum[ y[[i]]*z[[j]]*Fibonacci[i + j + 2], {i, Length[y]}, {j, Length[z]}]]; (from Robert G. Wilson v Feb 09 2005) %t A101330 Flatten[ Table[ kfp[i, n - i], {n, 2, 13}, {i, n - 1, 1, -1}]] (from Robert G. Wilson v Feb 09 2005) %Y A101330 Cf. A035517, A014417. See A101385, A101633, A101858 for related definitions of product. %Y A101330 Main diagonal is A101332. First row appears to equal A026274 - proof? Second row is A101345. Third row is A101642. %K A101330 nonn,tabl,easy,nice %O A101330 1,1 %A A101330 njas, Jan 25 2005 %E A101330 More terms from David Applegate (david(AT)research.att.com) Jan 26 2005

2 1

Re: [math-fun] Smallest term in Zeckendorf representation
by Dan Asimov 17 May '08

17 May '08

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

2 4

[math-fun] Cabtaxi(10) = 933528127886302221000
by Christian Boyer 17 May '08

17 May '08

After his recent work on Taxicab(6) confirming the number found as an upper bound by Randall Rathbun in 2002, Uwe Hollerbach (USA) confirmed this week that my upper bound 933528127886302221000 = 8387730^3 + 7002840^3 (1) = 8444345^3 + 6920095^3 (2) = 9773330^3 - 84560^3 (3) = 9781317^3 - 1318317^3 (4) = 9877140^3 - 3109470^3 (5) = 10060050^3 - 4389840^3 (6) = 10852660^3 - 7011550^3 (7) = 18421650^3 - 17454840^3 (8) = 41337660^3 - 41154750^3 (9) = 77480130^3 - 77428260^3 (10) constructed in Dec 2006 is really Cabtaxi(10). See his announcement at http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0805&L=nmbrthry&T=0&P=1284 See also http://cboyer.club.fr/Taxicab.htm, with updated tables of Taxicab and Cabtaxi numbers. You can also freely access to my paper published in Journal of Integer Sequences, with explanations on how this number was constructed, before to be proved the real Cabtaxi(10) number. Reminder: -Taxicab(n) is the smallest number expressible as a sum of two cubes in n different ways. -Cabtaxi(n) is the smallest number expressible as a sum or difference of two cubes in n different ways. Christian.

1 0

[math-fun] Arithmetic sub-series of Zeta(s)
by rwg＠sdf.lonestar.org 16 May '08

16 May '08

>Given integers 0 =< r < k, is there a standard way to relate the series >Z(s; k,r) := Sum{n=1..oo} 1/(kn+r)^s >to >Zeta(s) := Sum{n=1..oo} 1/n^s >? >(Of course for r = 0 this is trivial.) >--Dan No, you need Hurwitz zeta or polygammas: (c9) (sum((k+1/3)^-2,k,0,inf),%% = closedform(%%)) inf ==== \ 1 1 (d9) > -------- = Psi (-) / 1 2 1 3 ==== (k + -) k = 0 3 (c10) (sum((k+1/4)^-2,k,0,inf),%% = closedform(%%)) inf ==== \ 1 2 (d10) > -------- = %pi + 8 %catalan / 1 2 ==== (k + -) k = 0 4 (c11) (sum((k+1/3)^-3,k,0,inf),%% = closedform(%%)) inf ==== 3 \ 1 2 %pi (d11) > -------- = 13 zeta(3) + --------- / 1 3 3 sqrt(3) ==== (k + -) k = 0 3 (c12) (sum((k+1/4)^-3,k,0,inf),%% = closedform(%%)) inf ==== \ 1 3 (d12) > -------- = 28 zeta(3) + %pi / 1 3 ==== (k + -) k = 0 4 Look, Ma, no Yahoo spamdangles.

1 0

[math-fun] Arithmetic sub-series of Zeta(s)
by Dan Asimov 16 May '08

16 May '08

Given integers 0 =< r < k, is there a standard way to relate the series Z(s; k,r) := Sum{n=1..oo} 1/(kn+r)^s to Zeta(s) := Sum{n=1..oo} 1/n^s ? (Of course for r = 0 this is trivial.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Smallest term in Zeckendorf representation
by Michael Reid 16 May '08

16 May '08

oops, it looks like i AM overlooking something! i wrote: > even without this condition. indeed, any two such expressions for x > can be transformed to one another by a sequence of replacing > a_i F_{i+2} by a_i (F_{i+1} + F_i) or vice-versa; the corresponding this is not true, sorry. wishful thinking (or lack of thinking) on my part. however, i think there might be something here. perhaps it is the case that the expression \sum_{i,j} a_i b_j F_{i+j} can be transformed into Zeckendorf form by a linear combination of those basic transformations. i will think about it before posting further! mike

1 0

Re: [math-fun] Smallest term in Zeckendorf representation
by Michael Reid 16 May '08

16 May '08

> 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). unless i'm overlooking something, this is (almost) obvious. the definition of "Fibonacci product" does not really necessitate that the expressions x = \sum_i a_i F_i and y = \sum_j b_j F_j are in Zeckendorf form; that is, the operation is well-defined even without this condition. indeed, any two such expressions for x can be transformed to one another by a sequence of replacing a_i F_{i+2} by a_i (F_{i+1} + F_i) or vice-versa; the corresponding term a_i b_j F_{i+j+2} in the product is then replaced by a_i b_j (F_{i+j+1} + F_{i+j}) . (i'm supposing here that the coefficients are all integers, but i'm not sure of their significance; in view of Zeckendorf's theorem, might one want them all to be 1 ?) and then of course, either parenthesization of x(*)y(*)z gives \sum_{i,j,k} a_i b_j c_k F_{i+j+k} . mike

1 0

Re: [math-fun] Smallest term in Zeckendorf representation
by Fred lunnon 16 May '08

16 May '08

On 5/15/08, Steve Witham <sw(a)tiac.net> wrote: > In OEIS terms, is this sequence interesting? > I guess "nonn" and "easy". Is it "nice"? > > Name(?): Smallest term in Zeckendorf representation of n > http://en.wikipedia.org/wiki/Zeckendorf's_theorem > ... I made heavy use of this "Fib-adic" representation when investigating the Penrose tiling in the 1970's, though I didn't associate it with the name Zeckendorf. The analogy with positional (binary, etc) notation is easier to appreciate if the F_n are detached and only their coefficients retained --- e.g. in base-10, 20 = 13+5+2 = F_7 + F_5 + F_3 = 101010 in base-F [the final digit corresponding to F_2]. Each half-kite or half-dart in the tiling has a base-F coordinate associated (very nearly uniquely) with it, so that "inflation" of faces corresponds to shifting coordinates left two places, then appending 00, 01 or 10 (kite only) for respective subfaces. The Wikipedia page makes heavy weather of uniqueness, obvious 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. [x = 0 is trivially the empty sum.] Also mentioned there is a "Fibonacci product", defined by analogy with binary 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 the basic result F_n = ((tau)^n - (taubar)^n)/sqrt5 where (sqrt5)^2 = 5, tau = (1 + sqrt5)/2 is the usual golden section number, and taubar = (1 - sqrt5)/2 is its conjugate. Substituting into the definition, x(*)y = (1/5)\sum_{i,j} a_i b_j tau^{i+j} + ... = f_1(x,y) + ... + f_4(x,y), where each of the functions f_k(x,y) is trivially associative. Finally, note that the sum of associative functions is also associative. But this reasoning has a gap: supposing x(*)y or y(*)z within x(*)y(*)z is first reduced again to canonical form, will the final product have the same value as when not so reduced? Relaxing the uniqueness constraint to the extreme, we could set a_2 = x, a_i = 0 for i > 2; then x(*)y evaluates to 3 x y, which is certainly not correct --- so after all, Knuth's theorem is surprising! Fred Lunnon

1 0

[math-fun] Smallest term in Zeckendorf representation
by Steve Witham 15 May '08

15 May '08

In OEIS terms, is this sequence interesting? I guess "nonn" and "easy". Is it "nice"? Name(?): Smallest term in Zeckendorf representation of n http://en.wikipedia.org/wiki/Zeckendorf's_theorem 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1, 2... Example: The Zeckendorf representation of 7 = 5 + 2, so a(7) = 2. Formulas: a(n) = n if n is a Fibonacci number, else a( n - (largest Fibonacci number < n) ) a(n) = the value of the (exactly one) digit that turns on between the Fibonacci-base representations of n-1 and n. E.g. from 6 (1001) to 7 (1010), the two's digit turns on. a(n) = top element of the column of the Wythoff array that contains n http://mathworld.wolfram.com/WythoffArray.html a(n) = Fibonacci( A035614(n) + 1 ) Related to http://www.research.att.com/~njas/sequences/A035614 : 0, 1, 2, 0, 3, 0, 1, 4, 0, 1, 2, 0, 5, 0, 1, 2, 0, 3, 0, 1... "which column of Wythoff array (starting column count at 0) contains n." a(n) is also (Google translation:) "the numbers of matches to withdraw to win up to 55 matches (which is the first number of following Fibonacci greater than or equal to 50). " from "La stratgie des allumettes" ("The 'Matches' Strategy") http://mathematiques.ac-bordeaux.fr/elv/clubs/mej/mej2005/allumettes.pdf http://tinyurl.com/5sfgw8 (Google French pdf-->html-->English) It's also called a "Fibonacci fractal" on this page, in a section apparently about a stone-taking game: http://gifted.msquare.or.kr/lib/2003/2003bcamp.pdf http://tinyurl.com/5cy28c (Google Korean pdf-->html-->English) The frequencies of occurrences of the values in both these sequences are related by the golden ratio. You can see that the part of a() shown has eight 1's, five 2's, three 3's, two 5's, one 8, and one 13. I want to clock some processes at roughly golden-ratio-related frequencies, and I'm looking for the simplest way to generate A035614, basically. I was thinking boolean operations on long words, but maybe just generating Fibonacci numbers is easiest. A035614 is more useful but a(n) seems prettier and more mnemonic. I started with this picture: 1111111111111111111111111111111111 34 x 1 = 34 1 11 1 11 11 1 11 1 11 11 1 11 11 21 x 1 = 21 2 2 2 2 2 2 2 2 2 2 2 2 2 13 x 2 = 26 3 3 3 3 3 3 3 3 8 x 3 = 24 5 5 5 5 5 5 x 5 = 25 8 8 8 3 x 8 = 24 13 13 2 x 13 = 26 21 1 x 21 = 21 34 1 x 34 = 34 Maybe this way is better: 1 11 1 11 11 1 11 1 11 11 1 11 11 21 x 1 = 21 2 2 2 2 2 2 2 2 2 2 2 2 2 13 x 2 = 26 3 3 3 3 3 3 3 3 8 x 3 = 24 5 5 5 5 5 5 x 5 = 25 8 8 8 3 x 8 = 24 13 13 2 x 13 = 26 21 1 x 21 = 21 --Steve reminding myself to see also http://www.research.att.com/~njas/sequences/A107017 "Second largest term in Zeckendorf representation of n, a(n)=0 if n itself is a Fibonacci number." http://www.research.att.com/~njas/sequences/A014417 base fibo numbers http://www.research.att.com/~njas/sequences/A006519 highest power of two dividing n

1 0