A101345 -id:A101345 - 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

A101642 a(n) = Knuth's Fibonacci (or circle) product "3 o n".

Original entry on oeis.org

8, 13, 21, 29, 34, 42, 47, 55, 63, 68, 76, 84, 89, 97, 102, 110, 118, 123, 131, 136, 144, 152, 157, 165, 173, 178, 186, 191, 199, 207, 212, 220, 228, 233, 241, 246, 254, 262, 267, 275, 280, 288, 296, 301, 309, 317, 322, 330, 335, 343, 351, 356, 364, 369, 377

Offset: 1

N. J. A. Sloane, Jan 26 2005

nonn

Let phi be the golden ratio. Using Fred Lunnon's formula in A101330 for Knuth's circle product, and the fact that phi^{-2} = 2-phi, plus [-x] = -[x]-1 for non-integer x, one obtains the formula below, expressing this sequence in terms of the lower Wythoff sequence. It follows in particular that the sequence of first differences 5,8,8,5,8,5,8,8,5,8,... of this sequence is the Fibonacci word A003849 on the alphabet {8,5}, shifted by 1. - Michel Dekking, Dec 23 2019
Also numbers with suffix string 0000, when written in Zeckendorf representation. - A.H.M. Smeets, Mar 20 2024
The asymptotic density of this sequence is 1/phi^4 = A094214^4 = 0.145898... . - Amiram Eldar, Mar 24 2025

A.H.M. Smeets, Table of n, a(n) for n = 1..20000
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. 5.
W. F. Lunnon, Proof of formula, 2008.

Third row of array in A101330.
Cf. A101345 = Knuth's Fibonacci (or circle) product "2 o n".
Cf. A000201, A003849, A094214.

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[z1]}, {j, Length[z2]}]]; (* Robert G. Wilson v, Feb 04 2005 *)
Table[ kfp[3, n], {n, 50}] (* Robert G. Wilson v, Feb 04 2005 *)
Array[3*Floor[(# + 1)*GoldenRatio] + 2*# - 3 &, 100] (* Paolo Xausa, Mar 23 2024 *)

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

From Michel Dekking, Dec 23 2019: (Start)
a(n) = 3*A000201(n+1) + 2n - 3.
a(n) = A101345(n) + A000201(n+1) + n + 1. (End)

More terms from David Applegate, Jan 26 2005

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

A095085 Fib000 primes, i.e., primes p whose Zeckendorf-expansion A014417(p) ends with three zeros.

Original entry on oeis.org

5, 13, 29, 47, 73, 89, 97, 107, 131, 149, 157, 173, 191, 199, 233, 241, 251, 293, 317, 419, 461, 479, 487, 521, 547, 563, 631, 673, 683, 691, 733, 751, 809, 827, 877, 911, 919, 937, 953, 971, 1013, 1021, 1039, 1063, 1097, 1123, 1249, 1259

Offset: 1

Antti Karttunen, Jun 01 2004

Antti Karttunen and John Moyer, C-program for computing the initial terms of this sequence.

Intersection of A000040 and A101345.

Cf. A014417, A095065.

from sympy import fibonacci, primerange
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 str(a(n))[-3:]=="000"
print([n for n in primerange(1, 1261) if ok(n)]) # Indranil Ghosh, Jun 08 2017

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

A095097 Erroneous version of A101345.

Views

Author

Keywords

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

A101642 a(n) = Knuth's Fibonacci (or circle) product "3 o n".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A095085 Fib000 primes, i.e., primes p whose Zeckendorf-expansion A014417(p) ends with three zeros.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

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