A101646 Array read by antidiagonals: T(n,k) = variant of Knuth's Fibonacci (or circle) product of n and k (A101330). Sometimes called the "arroba" product.

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 5, 6, 8, 11, 11, 8, 6, 7, 10, 13, 15, 13, 10, 7, 8, 11, 16, 18, 18, 16, 11, 8, 9, 13, 18, 22, 21, 22, 18, 13, 9, 10, 15, 21, 25, 26, 26, 25, 21, 15, 10, 11, 16, 24, 29, 29, 32, 29, 29, 24, 16, 11, 12, 18, 26, 33, 34, 36, 36, 34, 33, 26, 18, 12

Offset: 1

Author

David Applegate and N. J. A. Sloane, Jan 26 2005

Keywords

• nonn
• tabl
• easy

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 product of n and k is defined here to be n x k = Sum_{i,j} eps(i)*eps(j) Fib_{i+j-2} (= T(n,k)). [Comment corrected by R. J. Mathar, Aug 07 2007]

Although now 1 is the multiplicative identity, in contrast to A101330, this multiplication is not associative. For example, as pointed out by Grabner et al., we have (4 x 7 ) x 9 = 25 x 9 = 198 but 4 x (7 x 9 ) = 4 x 54 = 195.

Examples

			Array begins:
  1 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 ...
  2 3  5  7  8 10 11 13 15 16 18 20 21 23 24 26 28 29 31 ...
  3 5  8 11 13 16 18 21 24 26 29 32 34 37 39 42 45 47 50 ...
  4 7 11 15 18 22 25 29 33 36 40 44 47 51 54 58 62 65 69 ...
  5 8 13 18 21 26 29 34 39 42 47 52 55 60 63 68 73 76 81 ...
...
		

Links

• 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

Crossrefs

Cf. A101330, A101385, A035517, A014417. Main diagonal is A101711.

First 4 rows give A000027, A022342, A026274, A101741.

Programs

Mathematica

T[n_, k_] := With[{phi2 = GoldenRatio^2}, n k - Floor[(k + 1)/phi2] Floor[ (n + 1)/phi2]];
Table[T[n - k + 1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 31 2020 *)

PARI

T(n, k) = my(phi2 = ((1+sqrt(5))/2)^2); n*k - floor((k+1)/phi2)*floor((n+1)/phi2); \\ Michel Marcus, Mar 29 2016

Formula

T(n, k) = n*k - [(k+1)/phi^2] [(n+1)/phi^2]. For proof see link. - Fred Lunnon, May 24 2008