A101642 -id:A101642 - cp's OEIS frontend

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.

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

Offset: 1

N. J. A. Sloane, Jan 25 2005

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.

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

T. D. Noe, First 100 antidiagonals, flattened
P. Arnoux, Some remarks about Fibonacci multiplication, Appl. Math. Lett. 2 (1989), 319-320.
P. Arnoux, Some remarks about Fibonacci multiplication, Appl. Math. Lett. 2 (No. 4, 1989), 319-320. [Annotated scanned copy]
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.

See A101646 and A135090 for other versions.
Main diagonal is A101332.
Rows: A026274 (row 1), A101345 (row 2), A101642 (row 3).
Cf. A035517, A014417, A060144.
Cf. A101385, A101633, A101858 for related definitions of product.

h := n -> floor(2*(n + 1)/(sqrt(5) + 3)):  # A060144(n+1)
T := (n, k) -> 3*n*k - n*h(k) - k*h(n):
seq(print(seq(T(n, k), k = 1..9)), n = 1..7);  # Peter Luschny, Mar 21 2024

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 *)
A101330[n_, k_]:=3*n*k-n*Floor[(k+1)/GoldenRatio^2]-k*Floor[(n+1)/GoldenRatio^2];
Table[A101330[n-k+1, k], {n, 15}, {k, n}] (* Paolo Xausa, Mar 20 2024 *)

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

T(n, k) = 3*n*k - n*h(k) - k*h(n) where h(n) = A060144(n + 1). - Peter Luschny, Mar 21 2024

More terms from David Applegate, Jan 26 2005

A101345 a(n) = Knuth's Fibonacci (or circle) product "2 o n".

Original entry on oeis.org

5, 8, 13, 18, 21, 26, 29, 34, 39, 42, 47, 52, 55, 60, 63, 68, 73, 76, 81, 84, 89, 94, 97, 102, 107, 110, 115, 118, 123, 128, 131, 136, 141, 144, 149, 152, 157, 162, 165, 170, 173, 178, 183, 186, 191, 196, 199, 204, 207, 212, 217, 220, 225, 228, 233, 238, 241, 246

Offset: 1

N. J. A. Sloane, Jan 26 2005

nonn

Numbers whose Zeckendorf representation ends with 000. - Benoit Cloitre, Jan 11 2014

The asymptotic density of this sequence is sqrt(5)-2. - Amiram Eldar, Mar 21 2022

Amiram Eldar, Table of n, a(n) for n = 1..10000
Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, Fibonacci-like partitions and their associated piecewise-defined permutations, arXiv:2503.19696 [math.CO], 2025. See p. 4.
Donald E. Knuth, Fibonacci multiplication, Appl. Math. Lett., Vol. 1, No. 1 (1988), pp. 57-60.

Second row of array in A101330.
Cf. A000201, A014417, A101642, A095085.
Set-wise difference of A026274 - A035337.

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]}]];
Table[kfp[2, n], {n, 60}] (* Robert G. Wilson v, Feb 04 2005 *)
With[{r = Map[Fibonacci, Range[2, 14]]}, Rest[-1 + Position[#, Integer][[All, 1]]] &@ Table[1/1000 * Total@ Map[FromDigits@ PadRight[{1}, Flatten@ #] &@ Reverse@ Position[r, #] &, Abs@ Differences@ NestWhileList[Function[k, k - SelectFirst[Reverse@ r, # < k &]], n + 1, # > 1 &]], {n, 0, 250}]] (* _Michael De Vlieger, Jun 08 2017 *)
Array[2*Floor[(#+1)*GoldenRatio]+#-2 &, 100] (* Paolo Xausa, Mar 20 2024 *)

from sympy import fibonacci
def a(n):
    k=0
    x=0
    while n>0:
        k=0
        while fibonacci(k)<=n: k+=1
        x+=10**(k - 3)
        n-=fibonacci(k - 1)
    return x
def ok(n): return 1 if str(a(n))[-3:]=="000" else 0 # Indranil Ghosh, Jun 08 2017

from math import isqrt
def A101345(n): return (n+1+isqrt(5*(n+1)**2)&-2)+n-2 # Chai Wah Wu, Aug 29 2022

a(n) = floor(phi^3*(n+1)) - 3 - floor(2*phi*(n+1)) + 2*floor(phi*(n+1)) where phi = (1+sqrt(5))/2. - Benoit Cloitre, Jan 11 2014

a(n) = 2*A000201(n+1) + n - 2. See the comments in A101642. - Michel Dekking, Dec 23 2019

More terms from David Applegate, Jan 26 2005

More terms from Robert G. Wilson v, Feb 04 2005

A357316 A distension of the Wythoff array by inclusion of intermediate rows. Square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals. If S is the set such that Sum_{i in S} F_i is the Zeckendorf representation of n then A(n,k) = Sum_{i in S} F_{i+k-2}.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 2, 1, 0, 3, 3, 3, 3, 2, 0, 5, 5, 5, 4, 3, 2, 0, 8, 8, 8, 7, 5, 4, 3, 0, 13, 13, 13, 11, 8, 6, 4, 3, 0, 21, 21, 21, 18, 13, 10, 7, 5, 3, 0, 34, 34, 34, 29, 21, 16, 11, 8, 6, 4, 0, 55, 55, 55, 47, 34, 26, 18, 13, 9, 6, 4

Offset: 0

Peter Munn, Sep 23 2022

Note the Zeckendorf representation of 0 is taken to be the empty sum.
The Wythoff array A035513 is the subtable formed by rows 3, 11, 16, 24, 32, ... (A035337). If, instead, we use rows 2, 7, 10, 15, 20, ... (A035336) or 1, 4, 6, 9, 12, ... (A003622), we get the Wythoff array extended by 1 column (A287869) or 2 columns (A287870) respectively.
Similarly, using A035338 truncates by 1 column; and in general if S_k is column k of the Wythoff array then the rows here numbered by S_k form an array A_k that starts with column k-2 of the Wythoff array. (A_0 and A_1 are the 2 extended arrays mentioned above.) As every positive integer occurs exactly once in the Wythoff array, every row except row 0 of A(.,.) is a row of exactly one such A_k.
Columns 4 onwards match certain columns of the multiplication table for Knuth's Fibonacci (or circle) product (extended variant - see A135090 and formula below).
For k > 0, the first row to contain k is A348853(k).

			Example for n = 4, k = 3. The Zeckendorf representation of 4 is F_4 + F_2 = 3 + 1. So the values of i in the sums in the definition are 4 and 2; hence A(4,3) = Sum_{i = 2,4} F_{i+k-2} = F_{4+3-2} + F_{2+3-2} = F_5 + F_3 = 5 + 2 = 7.
Square array A(n,k) begins:
   n\k| 0   1    2    3    4    5    6
  ----+--------------------------------
   0  | 0   0    0    0    0    0    0  ...
   1* | 0   1    1    2    3    5    8  ...
   2  | 1   1    2    3    5    8   13  ...
   3  | 1   2    3    5    8   13   21  ...
   4* | 1   3    4    7   11   18   29  ...
   5  | 2   3    5    8   13   21   34  ...
   6* | 2   4    6   10   16   26   42  ...
   7  | 3   4    7   11   18   29   47  ...
   8  | 3   5    8   13   21   34   55  ...
   9* | 3   6    9   15   24   39   63  ...
  10  | 4   6   10   16   26   42   68  ...
  11  | 4   7   11   18   29   47   76  ...
  12* | 4   8   12   20   32   52   84  ...
  ...
The asterisked rows form the start of the extended Wythoff array (A287870).

Encyclopedia of Mathematics, Zeckendorf representation

Columns, some differing initially: A005206 (1), A022342 (3), A026274 (4), A101345 (5), A101642 (6).
Rows: A000045 (1), A000204 (4).
Related to subtable A287870 as A130128 (as a square) is to A054582.
Other subtables: A035513, A287869.
See the comments for the relationship to A003622, A035336, A035337, A035338, A348853.
See the formula section for the relationship to A003714, A022342, A135090, A356874.

A5206(m) = if(m>0,m-A5206(A5206(m-1)),0)
A(n,k) = if(k==2,n, if(k==1,A5206(n), if(k==0,n-A5206(n), A(n,k-2)+A(n,k-1)))) \\ simple encoding of formulas, not efficient

For n >= 0, k >= 0 unless stated otherwise:
A(n,k) = A356874(floor(A003714(n)*2^(k-1))).
A(n,1) = A005206(n).
A(n,2) = n.
A(n,k+2) = A(n,k) + A(n,k+1).
A(A022342(n+1),k) = A(n,k+1).
For k >= 4, A(n,k) = A135090(n,A000045(k-2)).

A372302 Numbers k for which the Zeckendorf representation A014417(k) ends with "1001".

Original entry on oeis.org

6, 19, 27, 40, 53, 61, 74, 82, 95, 108, 116, 129, 142, 150, 163, 171, 184, 197, 205, 218, 226, 239, 252, 260, 273, 286, 294, 307, 315, 328, 341, 349, 362, 375, 383, 396, 404, 417, 430, 438, 451, 459, 472, 485, 493, 506, 519, 527, 540, 548, 561, 574, 582, 595, 603

Offset: 1

A.H.M. Smeets, Apr 25 2024

nonn

A.H.M. Smeets, Table of n, a(n) for n = 1..20000

Cf. A000045, A005614, A014417.
Tree of Zeckendorf subsequences of positive integers partitioned by their suffix part S (except initial term or offset in some cases). $ is the empty string. length(S) =
0        1        2        3        4        5        6       7
----------------------------------------------------------------------
$:       0:       00:      000:     0000:    00000:   000000:
A000027  A022342  A026274  A101345  A101642  notOEIS  notOEIS
                                                      100000: 0100000:
                                                      A035340  <------
                                             10000:
                                             A035339
                                    1000:    01000:
                                    A035338  <------
                  10:      010:     0010:
                  A035336  <------  A134861
                                    1010:    01010:
                                    A134863  <------
                           100:     0100:
                           A035337  <------
         1:       01:      001:     0001:
         A003622  <------  A134859  A151915
                                    1001:    01001:
                                    A372302  <------
                           101:     0101:
                           A134860  <------
Suffixes 10^n, where ^ means n times repeated concatenation, are the (n+1)-th columns in the Wythoff array A083412 and A035513 (n >= 0).

Equals {A134859}\{A151915}.
a(n) = A134863(n) - 1 = A035338(n) + 1.
a(n) = a(n-1) + 8 + 5*A005614(n-2) = a(n-1) + F(6) + F(5)*A005614(n-2), n > 1, where F(k) is the k-th Fibonacci number (A000045).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A101345 a(n) = Knuth's Fibonacci (or circle) product "2 o n".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Python

Formula

Extensions

A357316 A distension of the Wythoff array by inclusion of intermediate rows. Square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals. If S is the set such that Sum_{i in S} F_i is the Zeckendorf representation of n then A(n,k) = Sum_{i in S} F_{i+k-2}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A372302 Numbers k for which the Zeckendorf representation A014417(k) ends with "1001".

Views

Author

Keywords

Links

Crossrefs

Formula