login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A101330 Array read by antidiagonals: T(n,k) = Knuth's Fibonacci (or circle) product of n and k ("n o k"), n >= 1, k >= 1. 10
3, 5, 5, 8, 8, 8, 11, 13, 13, 11, 13, 18, 21, 18, 13, 16, 21, 29, 29, 21, 16, 18, 26, 34, 40, 34, 26, 18, 21, 29, 42, 47, 47, 42, 29, 21, 24, 34, 47, 58, 55, 58, 47, 34, 24, 26, 39, 55, 65, 68, 68, 65, 55, 39, 26, 29, 42, 63, 76, 76, 84, 76, 76, 63, 42, 29, 32, 47 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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)).

The Zeckendorf expansion can be written n=Sum_{i=1..k} F(a_i), where a_{i+1} >= a_i + 2. In this formulation, the product becomes: if n = Sum_{i=1..k} F(a_i) and m = Sum_{j=1..l} F(b_j) then n o m = Sum_{i=1..k} Sum_{j=1..l} F(a_i + b_j).

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.

The papers by Arnoux, Grabner et al. and Messaoudi discuss this sequence and generalizations.

LINKS

T. D. Noe, Rows n=1..100 of array, flattened

P. Arnoux, Some remarks about Fibonacci multiplication, Appl. Math. Lett. 2 (1989), 319-320.

Vincent Canterini and Anne Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001), 5121-5144.

P. Grabner et al., Associativity of recurrence multiplication, Appl. Math. Lett. 7 (1994), 85-90.

D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.

W. F. Lunnon, Proof of formula

A. Messaoudi, Propriétés arithmétiques et dynamiques du fractal de Rauzy, Journal de théorie des nombres de Bordeaux, 10 no. 1 (1998), p. 135-162.

A. Messaoudi, Propriétés arithmétiques et dynamiques du fractal de Rauzy [alternative copy]

A. Messaoudi, Généralisation de la multiplication de Fibonacci, Math. Slovaca, 50 (2) (2000), 135-148.

A. Messaoudi, Tribonacci multiplication, Appl. Math. Lett. 15 (2002), 981-985.

FORMULA

x o y = 3 x y - x [(y+1)/phi^2] - y [(x+1)/phi^2]. For proof see link. - Fred Lunnon, May 19 2008

EXAMPLE

Array begins:

   3   5   8  11   13   16   18   21   24 ...

   5   8  13  18   21   26   29   34   39 ...

   8  13  21  29   34   42   47   55   63 ...

  11  18  29  40   47   58   65   76   87 ...

  13  21  34  47   55   68   76   89  102 ...

  16  26  42  58   68   84   94  110  126 ...

  18  29  47  65   76   94  105  123  141 ...

  21  34  55  76   89  110  123  144  165 ...

  24  39  63  87  102  126  141  165  189 ...

  ...........................................

MATHEMATICA

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]}]]; (* Robert G. Wilson v, Feb 09 2005 *)

Flatten[ Table[ kfp[i, n - i], {n, 2, 13}, {i, n - 1, 1, -1}]] (* Robert G. Wilson v, Feb 09 2005 *)

CROSSREFS

See A101646 and A135090 for other versions.

Cf. A035517, A014417. See A101385, A101633, A101858 for related definitions of product.

Main diagonal is A101332. First row equals A026274. Second row is A101345. Third row is A101642.

Sequence in context: A021285 A138575 A263209 * A063285 A112507 A229428

Adjacent sequences:  A101327 A101328 A101329 * A101331 A101332 A101333

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane, Jan 25 2005

EXTENSIONS

More terms from David Applegate, Jan 26 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 16:22 EDT 2016. Contains 276546 sequences.