|
%I #46 Mar 21 2024 06:14:01
%S 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,
%T 34,26,18,21,29,42,47,47,42,29,21,24,34,47,58,55,58,47,34,24,26,39,55,
%U 65,68,68,65,55,39,26,29,42,63,76,76,84,76,76,63,42,29,32,47
%N Array read by antidiagonals: T(n, k) = Knuth's Fibonacci (or circle) product of n and k ("n o k"), n >= 1, k >= 1.
%C 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 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).
%C 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 The papers by Arnoux, Grabner et al. and Messaoudi discuss this sequence and generalizations.
%H T. D. Noe, <a href="/A101330/b101330.txt">First 100 antidiagonals, flattened</a>
%H P. Arnoux, <a href="http://dx.doi.org/10.1016/0893-9659(89)90078-5">Some remarks about Fibonacci multiplication</a>, Appl. Math. Lett. 2 (1989), 319-320.
%H P. Arnoux, <a href="/A101858/a101858.pdf">Some remarks about Fibonacci multiplication</a>, Appl. Math. Lett. 2 (No. 4, 1989), 319-320. [Annotated scanned copy]
%H Vincent Canterini and Anne Siegel, <a href="http://dx.doi.org/10.1090/S0002-9947-01-02797-0">Geometric representation of substitutions of Pisot type</a>, Trans. Amer. Math. Soc. 353 (2001), 5121-5144.
%H P. Grabner et al., <a href="http://dx.doi.org/10.1016/0893-9659(94)90017-5">Associativity of recurrence multiplication</a>, Appl. Math. Lett. 7 (1994), 85-90.
%H D. E. Knuth, <a href="http://dx.doi.org/10.1016/0893-9659(88)90176-0">Fibonacci multiplication</a>, Appl. Math. Lett. 1 (1988), 57-60.
%H W. F. Lunnon, <a href="/A101330/a101330.txt">Proof of formula</a>
%H A. Messaoudi, <a href="http://www.numdam.org/item?id=JTNB_1998__10_1_135_0">Propriétés arithmétiques et dynamiques du fractal de Rauzy</a>, Journal de théorie des nombres de Bordeaux, 10 no. 1 (1998), p. 135-162.
%H A. Messaoudi, <a href="http://almira.math.u-bordeaux.fr/jtnb/1998-1/messaoudi.ps">Propriétés arithmétiques et dynamiques du fractal de Rauzy</a> [alternative copy]
%H A. Messaoudi, <a href="http://dml.cz/handle/10338.dmlcz/136773">Généralisation de la multiplication de Fibonacci</a>, Math. Slovaca, 50 (2) (2000), 135-148.
%H A. Messaoudi, <a href="http://dx.doi.org/10.1016/S0893-9659(02)00073-3">Tribonacci multiplication</a>, Appl. Math. Lett. 15 (2002), 981-985.
%F T(n, k) = 3*n*k - n*floor((k+1)/phi^2) - k*floor((n+1)/phi^2). For proof see link. - _Fred Lunnon_, May 19 2008
%F T(n, k) = 3*n*k - n*h(k) - k*h(n) where h(n) = A060144(n + 1). - _Peter Luschny_, Mar 21 2024
%e Array begins:
%e 3 5 8 11 13 16 18 21 24 ...
%e 5 8 13 18 21 26 29 34 39 ...
%e 8 13 21 29 34 42 47 55 63 ...
%e 11 18 29 40 47 58 65 76 87 ...
%e 13 21 34 47 55 68 76 89 102 ...
%e 16 26 42 58 68 84 94 110 126 ...
%e 18 29 47 65 76 94 105 123 141 ...
%e 21 34 55 76 89 110 123 144 165 ...
%e 24 39 63 87 102 126 141 165 189 ...
%e ...........................................
%p h := n -> floor(2*(n + 1)/(sqrt(5) + 3)): # A060144(n+1)
%p T := (n, k) -> 3*n*k - n*h(k) - k*h(n):
%p seq(print(seq(T(n, k), k = 1..9)), n = 1..7); # _Peter Luschny_, Mar 21 2024
%t 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 *)
%t Flatten[ Table[ kfp[i, n - i], {n, 2, 13}, {i, n - 1, 1, -1}]] (* _Robert G. Wilson v_, Feb 09 2005 *)
%t A101330[n_, k_]:=3*n*k-n*Floor[(k+1)/GoldenRatio^2]-k*Floor[(n+1)/GoldenRatio^2];
%t Table[A101330[n-k+1, k], {n, 15}, {k, n}] (* _Paolo Xausa_, Mar 20 2024 *)
%Y See A101646 and A135090 for other versions.
%Y Main diagonal is A101332.
%Y Rows: A026274 (row 1), A101345 (row 2), A101642 (row 3).
%Y Cf. A035517, A014417, A060144.
%Y Cf. A101385, A101633, A101858 for related definitions of product.
%K nonn,tabl,easy,nice
%O 1,1
%A _N. J. A. Sloane_, Jan 25 2005
%E More terms from _David Applegate_, Jan 26 2005
|
