A287870 -id:A287870 - cp's OEIS frontend

A035513 Wythoff array read by falling antidiagonals.

1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12, 13, 29, 26, 24, 20, 14, 21, 47, 42, 39, 32, 23, 17, 34, 76, 68, 63, 52, 37, 28, 19, 55, 123, 110, 102, 84, 60, 45, 31, 22, 89, 199, 178, 165, 136, 97, 73, 50, 36, 25, 144, 322, 288, 267, 220, 157, 118, 81, 58, 41, 27, 233, 521

Offset: 1

N. J. A. Sloane

T(0,0)=1, T(0,1)=2,...; y^2-x^2-xy

Inverse of sequence A064274 considered as a permutation of the nonnegative integers. - Howard A. Landman, Sep 25 2001

The Wythoff array W consists of all the Wythoff pairs (x(n),y(n)), where x=A000201 and y=A001950, so that W contains every positive integer exactly once. The differences T(i,2j+1)-T(i,2j) form the Wythoff difference array, A080164, which also contains every positive integer exactly once. - Clark Kimberling, Feb 08 2003

For n>2 the determinant of any n X n contiguous subarray of A035513 (as a square array) is 0. - Gerald McGarvey, Sep 18 2004

From Clark Kimberling, Nov 14 2007: (Start)

Except for initial terms in some cases:

(Row 1) = A000045

(Row 2) = A000032

(Row 3) = A006355

(Row 4) = A022086

(Row 5) = A022087

(Row 6) = A000285

(Row 7) = A022095

(Row 8) = A013655 (sum of Fibonacci and Lucas numbers)

(Row 9) = A022112

(Row 10-19) = A022113, A022120, A022121, A022379, A022130, A022382, A022088, A022136, A022137, A022089

(Row 20-28) = A022388, A022096, A022090, A022389, A022097, A022091, A022390, A022098, A022092

(Column 1) = A003622 = AA Wythoff sequence

(Column 2) = A035336 = BA Wythoff sequence

(Column 3) = A035337 = ABA Wythoff sequence

(Column 4) = A035338 = BBA Wythoff sequence

(Column 5) = A035339 = ABBA Wythoff sequence

(Column 6) = A035340 = BBBA Wythoff sequence

Main diagonal = A020941. (End)

The Wythoff array is the dispersion of the sequence given by floor(n*x+x-1), where x=(golden ratio). See A191426 for a discussion of dispersions. - Clark Kimberling, Jun 03 2011

If u and v are finite sets of numbers in a row of the Wythoff array such that (product of all the numbers in u) = (product of all the numbers in v), then u = v. See A160009 (row 1 products), A274286 (row 2), A274287 (row 3), A274288 (row 4). - Clark Kimberling, Jun 17 2016

All columns of the Wythoff array are compound Wythoff sequences. This follows from the main theorem in the 1972 paper by Carlitz, Scoville and Hoggatt. For an explicit expression see Theorem 10 in Kimberling's paper from 2008 in JIS. - Michel Dekking, Aug 31 2017

The Wythoff array can be viewed as an infinite graph over the set of nonnegative integers, built as follows: start with an empty graph; for all n = 0, 1, ..., create an edge between n and the sum of the degrees of all i < n. Finally, remove vertex 0. In the resulting graph, the connected components are chains and correspond to the rows of the Wythoff array. - Luc Rousseau, Sep 28 2017

Suppose that h < k are consecutive terms in a row of the Wythoff array. If k is in an even numbered column, then h = floor(k/tau); otherwise, h = -1 + floor(k/tau). - Clark Kimberling, Mar 05 2020

From Clark Kimberling, May 26 2020: (Start)

For k > = 0, column k shows the numbers m having F(k+1) as least term in the Zeckendorf representation of m. For n >= 1, let r(n,k) be the number of terms in column k that are <= n. Then n/r(n,k) = n/(F(k+1)*tau + F(k)*(n-1)), by Bottomley's formula, so that the limiting ratio is 1/(F(k+1)*tau + F(k)). Summing over all k gives Sum_{k>=0} 1/(F(k+1)*tau + F(k)) = 1. Thus, in the limiting sense:

38.19...% of the numbers m have least term 1;

23.60...% have least term 2;

14.58...% have least term 3;

9.01...% have least term 5, etc. (End)

Named after the Dutch mathematician Willem Abraham Wythoff (1865-1939). - Amiram Eldar, Jun 11 2021

From Clark Kimberling, Jun 04 2025: (Start)

Let u(n) = (T(n,1),T(n,2)) mod 2. The positive integers (A000027) are partitioned into 4 sets (sequences):

{n : u(n) = (0,0)} = (3, 5, 9, 15, 19, 25, 29,...) = 1 + 2*A190429

{n: u(n) = (0,1)} = (2, 6, 12, 16, 18, 22, 28,...) = A191331

{n : u(n) = (1,0)} = (1, 7, 11, 13, 17, 21, 23,...) = A086843

{n: u(n) = (1,1)} = (4, 8, 10, 14, 20, 24, 26,...) = A191330.

Let v(n) = (T(n,1),T(n,2)) mod 3. The positive integers are partitioned into 9 sets (sequences):

{n : v(n) = (0,0)} = (4, 13, 19, 28, 43, 52,...) = 1 + 3*A190434

{n: v(n) = (0,1)} = (3, 12, 27, 36, 42, 51,...) = 3*A140399

{n : v(n) = (0,2)} = (5, 11, 20, 35, 44, 50,...) = 2 + 3*A190439

{n: v(n) = (1,0)} = (9, 18, 24, 33, 48, 57,...) = 3*A140400

{n: v(n) = (1,1)} = (2, 8, 17, 26, 32, 41,...) = A384601

{n : v(n) = (1,2)} = (1, 10, 16, 25, 34, 40,...) = A384602

{n: v(n) = (2,0)} = (14, 23, 29, 38, 47, 53,...) = 2 + 3*A190438

{n: v(n) = (2,1)} = (7, 22, 31, 37, 46, 61,...) = 1 + 3*A190433

{n : v(n) = (2,2)} = (6, 15, 21, 30, 39, 45,...) = 3*A140398.

Conjecture: If m >= 2, then {(T(n,1), T(n,2)) mod m} has cardinality m^2. (End)

			The Wythoff array begins:
   1    2    3    5    8   13   21   34   55   89  144 ...
   4    7   11   18   29   47   76  123  199  322  521 ...
   6   10   16   26   42   68  110  178  288  466  754 ...
   9   15   24   39   63  102  165  267  432  699 1131 ...
  12   20   32   52   84  136  220  356  576  932 1508 ...
  14   23   37   60   97  157  254  411  665 1076 1741 ...
  17   28   45   73  118  191  309  500  809 1309 2118 ...
  19   31   50   81  131  212  343  555  898 1453 2351 ...
  22   36   58   94  152  246  398  644 1042 1686 2728 ...
  25   41   66  107  173  280  453  733 1186 1919 3105 ...
  27   44   71  115  186  301  487  788 1275 2063 3338 ...
  ...
The extended Wythoff array has two extra columns, giving the row number n and A000201(n), separated from the main array by a vertical bar:
0     1  |   1    2    3    5    8   13   21   34   55   89  144   ...
1     3  |   4    7   11   18   29   47   76  123  199  322  521   ...
2     4  |   6   10   16   26   42   68  110  178  288  466  754   ...
3     6  |   9   15   24   39   63  102  165  267  432  699 1131   ...
4     8  |  12   20   32   52   84  136  220  356  576  932 1508   ...
5     9  |  14   23   37   60   97  157  254  411  665 1076 1741   ...
6    11  |  17   28   45   73  118  191  309  500  809 1309 2118   ...
7    12  |  19   31   50   81  131  212  343  555  898 1453 2351   ...
8    14  |  22   36   58   94  152  246  398  644 1042 1686 2728   ...
9    16  |  25   41   66  107  173  280  453  733 1186 1919 3105   ...
10   17  |  27   44   71  115  186  301  487  788 1275 2063 3338   ...
11   19  |  30   49   79   ...
12   21  |  33   54   87   ...
13   22  |  35   57   92   ...
14   24  |  38   62   ...
15   25  |  40   65   ...
16   27  |  43   70   ...
17   29  |  46   75   ...
18   30  |  48   78   ...
19   32  |  51   83   ...
20   33  |  53   86   ...
21   35  |  56   91   ...
22   37  |  59   96   ...
23   38  |  61   99   ...
24   40  |  64   ...
25   42  |  67   ...
26   43  |  69   ...
27   45  |  72   ...
28   46  |  74   ...
29   48  |  77   ...
30   50  |  80   ...
31   51  |  82   ...
32   53  |  85   ...
33   55  |  88   ...
34   56  |  90   ...
35   58  |  93   ...
36   59  |  95   ...
37   61  |  98   ...
38   63  |     ...
   ...
Each row of the extended Wythoff array also satisfies the Fibonacci recurrence, and may be extended to the left using this recurrence backwards.
From _Peter Munn_, Jun 11 2021: (Start)
The Wythoff array appears to have the following relationship to the traditional Fibonacci rabbit breeding story, modified for simplicity to be a story of asexual reproduction.
Give each rabbit a number, 0 for the initial rabbit.
When a new round of rabbits is born, allocate consecutive numbers according to 2 rules (the opposite of many cultural rules for inheritance precedence): (1) newly born child of Rabbit 0 gets the next available number; (2) the descendants of a younger child of any given rabbit precede the descendants of an older child of the same rabbit.
Row n of the Wythoff array lists the children of Rabbit n (so Rabbit 0's children have the Fibonacci numbers: 1, 2, 3, 5, ...). The generation tree below shows rabbits 0 to 20. It is modified so that each round of births appears on a row.
                                                                 0
                                                                 :
                                       ,-------------------------:
                                       :                         :
                       ,---------------:                         1
                       :               :                         :
              ,--------:               2               ,---------:
              :        :               :               :         :
        ,-----:        3         ,-----:         ,-----:         4
        :     :        :         :     :         :     :         :
     ,--:     5     ,--:     ,---:     6     ,---:     7     ,---:
     :  :     :     :  :     :   :     :     :   :     :     :   :
  ,--:  8  ,--:  ,--:  9  ,--:  10  ,--:  ,--:  11  ,--:  ,--:  12
  :  :  :  :  :  :  :  :  :  :   :  :  :  :  :   :  :  :  :  :   :
  : 13  :  : 14  : 15  :  : 16   :  : 17  : 18   :  : 19  : 20   :
The extended array's nontrivial extra column (A000201) gives the number that would have been allocated to the first child of Rabbit n, if Rabbit n (and only Rabbit n) had started breeding one round early.
(End)

John H. Conway, Posting to Math Fun Mailing List, Nov 25 1996.
Clark Kimberling, "Stolarsky interspersions," Ars Combinatoria 39 (1995) 129-138.

Alois P. Heinz, Table of n, a(n) for n = 1..5151
Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21.
L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Fibonacci representations, Fib. Quart., Vol. 10, No. 1 (1972), pp. 1-28.
Code Golf Stack Exchange, New Order #5: where Fibonacci and Beatty meet at Wythoff.
J. H. Conway, Allan Wechsler, Marc LeBrun, Dan Hoey, and N. J. A. Sloane, On Kimberling Sums and Para-Fibonacci Sequences, Correspondence and Postings to Math-Fun Mailing List, Nov 1996 to Jan 1997.
John Conway and Alex Ryba, The extra Fibonacci series and the Empire State Building, Math. Intelligencer, Vol. 38, No. 1 (2016), pp. 41-48.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18. - _N. J. A. Sloane_, Jun 10 2012
Clark Kimberling, Interspersions.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly, Vol. 33, No. 1 (1995), pp. 3-8.
Clark Kimberling, Complementary equations and Wythoff Sequences, JIS, Vol. 11 (2008), Article 08.3.3.
Clark Kimberling, Lucas Representations of Positive Integers, J. Int. Seq., Vol. 23 (2020), Article 20.9.5.
Clark Kimberling and Kenneth B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123, No. 2 (2016), pp. 267-273.
Stéphane Legendre, Labeled Fibonacci Trees, Fibonacci Quart. 53 (2015), no. 2, 152-167.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 1-2.
Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, Vol. 41 (2013), pp. 175-192.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Classic Sequences
Sam Vandervelde, On the divisibility of Fibonacci sequences by primes of index two, The Fibonacci Quarterly, Vol. 50, No. 3 (2012), pp. 207-216. See Figure 1.
Eric Weisstein's World of Mathematics, Wythoff Array.
Wikipedia, Wythoff array.
Pedro Zanetti, C++ code snippet, for generating this sequence.
Index entries for sequences that are permutations of the natural numbers

See comments above for more cross-references.
Cf. A003622, A064274 (inverse), A083412 (transpose), A000201, A001950, A080164, A003603, A265650, A019586 (row that contains n).
For two versions of the extended Wythoff array, see A287869, A287870.

W:= proc(n,k) Digits:= 100; (Matrix([n, floor((1+sqrt(5))/2* (n+1))]). Matrix([[0,1], [1,1]])^(k+1))[1,2] end: seq(seq(W(n, d-n), n=0..d), d=0..10); # Alois P. Heinz, Aug 18 2008
A035513 := proc(r, c)
    option remember;
    if c = 1 then
        A003622(r) ;
    else
        A022342(1+procname(r, c-1)) ;
    end if;
end proc:
seq(seq(A035513(r,d-r),r=1..d-1),d=2..15) ; # R. J. Mathar, Jan 25 2015

W[n_, k_] := Fibonacci[k + 1] Floor[n*GoldenRatio] + (n - 1) Fibonacci[k]; Table[ W[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // Flatten

T(n,k)=(n+sqrtint(5*n^2))\2*fibonacci(k+1) + (n-1)*fibonacci(k)
for(k=0,9,for(n=1,k, print1(T(n,k+1-n)", "))) \\ Charles R Greathouse IV, Mar 09 2016

from sympy import fibonacci as F, sqrt
import math
tau = (sqrt(5) + 1)/2
def T(n, k): return F(k + 1)*int(math.floor(n*tau)) + F(k)*(n - 1)
for n in range(1, 11): print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Apr 23 2017

from math import isqrt, comb
from gmpy2 import fib2
def A035513(n):
    a = (m:=isqrt(k:=n<<1))+(k>m*(m+1))
    x = n-comb(a,2)
    b, c = fib2(a-x+2)
    return b*(x+isqrt(5*x*x)>>1)+c*(x-1) # Chai Wah Wu, Jun 26 2025

T(n, k) = Fib(k+1)*floor[n*tau]+Fib(k)*(n-1) where tau = (sqrt(5)+1)/2 = A001622 and Fib(n) = A000045(n). - Henry Bottomley, Dec 10 2001

T(n,-1) = n-1. T(n,0) = floor(n*tau). T(n,k) = T(n,k-1) + T(n,k-2) for k>=1. - R. J. Mathar, Sep 03 2016

Comments about the extended Wythoff array added by N. J. A. Sloane, Mar 07 2016

A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.

Original entry on oeis.org

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47

Offset: 0

N. J. A. Sloane

Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58) = 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):
  14  15  16  17  18  19  20  21
    \ /   /     \ /     \ /   /
     9  10      11      12  13
      \ /       /         \ /
       6       7           8
        \     /           /
         \   /           /
          \ /           /
           4           5
            \         /
             \       /
              \     /
               \   /
                \ /
                 3
                /
               2
            \ /
             1
To construct the tree: node n is connected with the node a(n) below
     n
    /
  a(n)
For example, since a(7) = 4:
    7
   /
  4
If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct
      /
     x
  \ /
   x
can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,
              /
             x
      /   \ /
     x     x
  \ /     /
   x     x
    \   /
     \ /
      x
When moving from a node to a lower connected node, one is moving to the parent. Parent node of n: floor((n+1)/tau). Left child of n: floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/2. (See the Sillke link.)
(End)
The number n appears A001468(n) times; A001468(n) = floor((n+1)*Phi) - floor(n*Phi) with Phi = (1 + sqrt 5)/2. - Philippe Deléham, Sep 22 2005
Number of positive Wythoff A-numbers A000201 not exceeding n. - N. J. A. Sloane, Oct 09 2006
Number of positive Wythoff B-numbers < A000201(n+1). - N. J. A. Sloane, Oct 09 2006
From Bernard Schott, Apr 23 2022: (Start)
Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):
-> a(n) >= a(n-1) for any positive integer n,
-> a(n) - a(n-1) belongs to {0,1},
-> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)
For n >= 1, find n in the Wythoff array (A035513). a(n) is the number that precedes n in its row, using the preceding column of the extended Wythoff array (A287870) if n is at the start of the (unextended) row. - Peter Munn, Sep 17 2022
See my 2023 publication on Hofstadter's G-sequence for a proof of the equality of (a(n)) with the sequence A073869. - Michel Dekking, Apr 28 2024
From Michel Dekking, Dec 16 2024: (Start)
Focus on the pairs of duplicate values, i.e., the pairs (a(n-1),a(n)) with a(n-1) = a(n). Directly from Theorem 1 in Kimberling and Stolarsky (2016) one derives that the m-th pair of duplicate values (a(n-1),a(n)) occurs at n = U(m), where U = 2,5,7,10,... is the upper Wythoff sequence. For example, (3,3) is the second pair, and occurs at U(2) = 5.
This property can be used to give a simple construction for (a(n)) -- ignoring the superfluous a(0) = 0.
Let 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,... be the sequence of positive natural numbers. Double all the elements of the lower Wythoff sequence (L(n)) = 1,3,4,6,8,9,11,....:
     (x(n)) := 1,1, 2, 3,3, 4,4, 5, 6,6, 7, 8,8, 9,9, 10,....
Claim: the result is (a(n)). This follows since because of the doubling, the m-th pair of duplicate values (a(n-1),a(n)) occurs in x at n = L(m) + m = U(m). The second equality by a well-known formula.
It follows from this by Theorem 1 of K&S, that a(n-1) = x(n-1), and a(n) = x(n) if n = U(m), for all m. But since L and U are complementary sequences, a(n) = x(n) will also hold if n = L(k), for all k. For example, L(4) = 6, and a(6) = x(6) = 4.
Corollary: for n >= 2 replace every pair of duplicate values (a(n-1),a(n)) by 0, and all the remaining elements of (a(n)) by 1. Then the result is the Fibonacci word 0,1,0,0,1,0,1,0,0... This is implied by the fact that L gives the positions of the 0s, and U the position of the 1's in the Fibonacci word. (End)
For all n >= 0, a(n) <= A005374(n), as proved in Letouzey-Li-Steiner link. Last equality occurs at n = 12, while a(n) < A005374(n) afterwards. - Pierre Letouzey, Feb 20 2025

D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 0..20000 (the first 1000 terms were found by T. D. Noe)
L. Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220. a(n) = e(n) at equation 1.10 or 2.11 and see equation 3.8 recurrence.
M. Celaya and F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013.
M. Celaya and F. Ruskey, Another Property of Only the Golden Ratio, American Mathematical Monthly, Problem 11651, solutions volume 121, number 6, June-July 2014, pages 549-556.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
F. M. Dekking, On Hofstadter's G-sequence, Journal of Integer Sequences 26 (2023), Article 23.9.2, 1-11.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. Also annotated scanned copy.
Martin Griffiths, A formula for an infinite family of Fibonacci-word sequences, Fib. Q., 56 (2018), 75-80.
H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., Sequences associated with t-ary coding of Fibonacci's rabbits, Fib. Quart., 15 (1977), 311-318.
Vincent Granville and Jean-Paul Rasson, A strange recursive relation, J. Number Theory 30 (1988), no. 2, 238--241. MR0961919(89j:11014).
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
Nick Hobson, Python program for this sequence
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991
The IMO Compendium, Problem 1, 45th Czech and Slovak Mathematical Olympiad 1996.
Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
Pierre Letouzey, Hofstadter's problem for curious readers, Technical Report, 2015.
Pierre Letouzey, S. Li and W. Steiner, Pointwise order of generalized Hofstadter functions G,H and beyond, arXiv:2410.00529 [cs.DM], 2024.
Pierre Letouzey, Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy arXiv:2502.12615 [cs.DM], 2025.
Mustazee Rahman, A Combinatorial interpretation of Hofstadter's G-sequence, arXiv:1105.1718 [math.CO], 2011-2013.
B. Schoenmakers, A tight lower bound for top-down skew heaps, Information Processing Letters, 61(5): 279-284, 14 March 1997.
Torsten Sillke, Floor Recurrences
Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - _N. J. A. Sloane_, May 30 2009
Eric Weisstein's World of Mathematics, Hofstadter G-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences
Index entries for sequences from "Goedel, Escher, Bach"
Index to sequences related to Olympiads.

Apart from initial terms, same as A060143. Cf. A123070.
a(n):=Sum{k=1..n} h(k), n >= 1, with h(k):= A005614(k-1) and a(0):=0.
Cf. A060144, A019446, A072649, A213676, A000201.
Cf. A035513, A287870.

a005206 n = a005206_list !! n
a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list)
-- Reinhard Zumkeller, Feb 02 2012, Aug 07 2011

a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1)
-- Reinhard Zumkeller, Mar 10 2013

[Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016

H:=proc(n) option remember; if n=0 then 0 elif n=1 then 1 else n-H(H(n-1)); fi; end proc: seq(H(n),n=0..76);

a[0] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0]
(* Second program: *)
Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* Michael De Vlieger, Nov 13 2017 *)

first(n)=my(v=vector(n)); v[1]=1; for(k=2,n, v[k]=k-v[v[k-1]]); concat(0,v) \\ Charles R Greathouse IV, Sep 02 2015

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

a(n) = floor((n+1)*tau) - n - 1 = A000201(n+1)-n-1, where tau = (1+sqrt(5))/2; or a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2.
a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - Benoit Cloitre, Nov 27 2002
a(n) = A019446(n) - 1. - Reinhard Zumkeller, Feb 02 2012
a(n) = n - A060144(n+1). - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{k=1..A072649(m)} A000045(m)*A213676(m,k): m=A000201(n+1). - Reinhard Zumkeller, Mar 10 2013
From Pierre Letouzey, Sep 09 2015: (Start)
a(n + a(n)) = n.
a(n) + a(a(n+1) - 1) = n.
a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). (End)
a(n) = A293688(n)/(n+1) for n >= 0 (conjectured). - Enrique Navarrete, Oct 15 2017
A generalization of Diego Torres's 2002 comment as a formula: if n = Sum_{i in S} A000045(i+1), where S is a set of positive integers, then a(n) = Sum_{i in S} A000045(i). - Peter Munn, Sep 28 2022
Conjectures from Chunqing Liu, Aug 01 2023: (Start)
a(A000201(n)-1) = n-1.
a(A001950(n)-1) = a(A001950(n)) = A000201(n). (End)

a(0) = 0 added in the Name by Bernard Schott, Apr 23 2022

A356874 Write n as Sum_{i in S} 2^(i-1), where S is a set of positive integers, then a(n) = Sum_{i in S} F_i, where F_i is the i-th Fibonacci number, A000045(i).

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 8, 9, 8, 9, 9, 10, 10, 11, 11, 12, 8, 9, 9, 10, 10, 11, 11, 12, 11, 12, 12, 13, 13, 14, 14, 15, 13, 14, 14, 15, 15, 16, 16, 17, 16, 17, 17, 18, 18, 19, 19, 20, 13, 14, 14, 15, 15, 16, 16, 17, 16, 17, 17, 18, 18, 19, 19, 20

Offset: 0

Peter Munn, Sep 02 2022

This sequence looks on the Fibonacci sequence terms (from F_1 onwards) as an ordered set, considering F_1 and F_2 as distinct members mapped to the same integer value, namely 1. We run through all finite subsets, adding up the integer values from each subset (see table in the examples). In consequence, a number, k, occurs exactly A000121(k) times.
The definition is effectively an amendment of the definition of A022290 so that a(n) is a sum of Fibonacci terms starting with F_1 rather than F_2. If we took this a further step so that a(n) was a sum of Fibonacci terms starting with F_0, we would get this sequence with each term duplicated, that is 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, ... .
Doubling n increments the indices of the Fibonacci terms that sum to a(n), so a(2n) is in this sense a Fibonacci successor to a(n). When n is even, this sense matches the meaning of successor as used in A022342; however, for odd n, the generated successor of a(n) is A000201(a(n)) -- note, in this respect, that A000201 is a column in the extended Wythoff array (A287870).

			n = 13: 13 = 8 + 4 + 1 = 2^(4-1) + 2^(3-1) + 2^(1-1); so a(n) = F_4 + F_3 + F_1 = 3 + 2 + 1 = 6.
Table showing initial terms with Fibonacci subsets:
  n   Fibonacci subset                           a(n)
  0  { }     (empty set)     ->  0              =  0
  1  { F_1 }                 ->  1              =  1
  2  {      F_2 }            ->  0 + 1          =  1
  3  { F_1, F_2 }            ->  1 + 1          =  2
  4  {           F_3 }       ->  0 + 0 + 2      =  2
  5  { F_1,      F_3 }       ->  1 + 0 + 2      =  3
  6  {      F_2, F_3 }       ->  0 + 1 + 2      =  3
  7  { F_1, F_2, F_3 }       ->  1 + 1 + 2      =  4
  8  {                F_4 }  ->  0 + 0 + 0 + 3  =  3
  9  { F_1,           F_4 }  ->  1 + 0 + 0 + 3  =  4

Amiram Eldar, Table of n, a(n) for n = 0..10000

Cf. A000045, A000121, A000201, A022342, A287870.

Even bisection: A022290.

a[n_] := Module[{d = IntegerDigits[n, 2], nd}, nd = Length[d]; Total[d * Fibonacci[Range[nd, 1, -1]]]]; Array[a, 100, 0] (* Amiram Eldar, Aug 08 2023 *)

a(n) = if(n==0,0,if(n%2==1,a(n-1)+1,a(n/2)+a(n\4))); \\ Peter Munn, Sep 06 2022

a(2n) = a(n) + a(floor(n/2)); a(2n+1) = a(2n) + 1.
a(2^k) = A000045(k+1).
For k >= 1, 2^k < n < 2^(k+1), a(n) = a(n - 2^k) + a(2^k).
a(2n) = A022290(n).
a(4n) = A022342(a(2n)+1).
a(4n+2) = A000201(a(2n+1)).

A287869 Wythoff array with one extra column, read by antidiagonals downwards.

Original entry on oeis.org

1, 1, 3, 2, 4, 4, 3, 7, 6, 6, 5, 11, 10, 9, 8, 8, 18, 16, 15, 12, 9, 13, 29, 26, 24, 20, 14, 11, 21, 47, 42, 39, 32, 23, 17, 12, 34, 76, 68, 63, 52, 37, 28, 19, 14, 55, 123, 110, 102, 84, 60, 45, 31, 22, 16, 89, 199, 178, 165, 136, 97, 73, 50, 36, 25, 17

Offset: 1

N. J. A. Sloane, Jun 14 2017

			The extended Wythoff array is the Wythoff array with two extra columns, giving the row number n and A000201(n), separated from the main array by a vertical bar:
0     1  |   1    2    3    5    8   13   21   34   55   89  144   ...
1     3  |   4    7   11   18   29   47   76  123  199  322  521   ...
2     4  |   6   10   16   26   42   68  110  178  288  466  754   ...
3     6  |   9   15   24   39   63  102  165  267  432  699 1131   ...
4     8  |  12   20   32   52   84  136  220  356  576  932 1508   ...
5     9  |  14   23   37   60   97  157  254  411  665 1076 1741   ...
6    11  |  17   28   45   73  118  191  309  500  809 1309 2118   ...
7    12  |  19   31   50   81  131  212  343  555  898 1453 2351   ...
8    14  |  22   36   58   94  152  246  398  644 1042 1686 2728   ...
9    16  |  25   41   66  107  173  280  453  733 1186 1919 3105   ...
10   17  |  27   44   71  115  186  301  487  788 1275 2063 3338   ...
11   19  |  30   49   79   ...
12   21  |  33   54   87   ...
13   22  |  35   57   92   ...
14   24  |  38   62   ...
15   25  |  40   65   ...
16   27  |  43   70   ...
17   29  |  46   75   ...
18   30  |  48   78   ...
19   32  |  51   83   ...
20   33  |  53   86   ...
21   35  |  56   91   ...
22   37  |  59   96   ...
23   38  |  61   99   ...
24   40  |  64   ...
25   42  |  67   ...
26   43  |  69   ...
27   45  |  72   ...
28   46  |  74   ...
29   48  |  77   ...
30   50  |  80   ...
31   51  |  82   ...
32   53  |  85   ...
33   55  |  88   ...
34   56  |  90   ...
35   58  |  93   ...
36   59  |  95   ...
37   61  |  98   ...
38   63  |     ...
   ...
The present sequence presents the array with just the rightmost extra column.

Conway, John; Ryba, Alex; The extra Fibonacci series and the Empire State Building. Math. Intelligencer 38 (2016), no. 1, 41-48.

Cf. A035513 (the Wythoff array), A287870, A000201.

A357097 A multiplication table for the rows of the extended Wythoff array. See comments for definition.

Original entry on oeis.org

0, 1, 1, 2, 15, 2, 3, 8, 8, 3, 4, 12, 4, 12, 4, 5, 44, 18, 18, 44, 5, 6, 19, 24, 27, 24, 19, 6, 7, 62, 28, 96, 96, 28, 62, 7, 8, 26, 34, 42, 128, 42, 34, 26, 8, 9, 30, 14, 51, 56, 56, 51, 14, 30, 9, 10, 91, 44, 57, 180, 65, 180, 57, 44, 91, 10, 11, 37, 50, 66, 76, 79, 79, 76, 66, 50, 37, 11

Offset: 0

Peter Munn, Sep 11 2022

Square array A(x,y), x >= 0, y >= 0, defined as follows:
(1) Extend the Wythoff array infinitely to the left, maintaining the Fibonacci recurrence (see A287870 examples). We denote this extended array as eW(n,m), n >= 0, m any integer, indexed such that eW(n,0) = n. From each row n, form the set of pairs S_n = {(eW(n,m+1),eW(n,m)) : integer m)}.
(2) Define addition and multiplication of pairs by (j1,k1) + (j2,k2) = (j1+j2, k1+k2) and (j1,k1) o (j2,k2) = (j1*j2 + k1*k2, j1*k2 + k1*j2 - k1*k2). (This defines a commutative ring with identity (1,0).)
(3) For nonnegative integers x and y, there is an integer z such that for every pair (j_x,k_x) in S_x and every pair (j_y,k_y) in S_y, (j_x,k_x) o (j_y,k_y) is in S_z. Define A(x,y) = z.
As a binary operation, A(.,.) is analogous to multiplication of coefficients in scientific numeric notation. The column position, m, used to define a pair in (1) above does not affect the eventual outcome, A(x,y), in (3), as no special pairs are selected from the pairs in S_x or S_y. The column position is analogous to the exponent. Notice also A(1,1) = 15 is substantially larger than A(2,2) = 4. This can be seen as analogous to 0.3 * 0.4 = 0.12 requiring more digits than 0.5 * 0.8 = 0.4.

			Calculation for A(1,2). Rows 1 and 2 of A287870 (indexed from 0) start 1, 3, ... and 2, 4, ... . So we may use the pairs (3,1) and (4,2). The defined multiplication gives (3*4 + 1*2, 3*2 + 4*1 - 1*2) = (14,8). 8, 14 , ... is in row 8 of A287870, so A(1,2) = 8.
For A(1,1), we start as above to get (3*3 + 1*1, 3*1 + 3*1 - 1*1) = (10,5). In the more general case, we form a sequence using the Fibonacci recurrence (as ..., 5, 10, ... may be in the extension leftwards of A287870). This starts 5, 10, 5+10=15, 10+15=25, 15+25=40, ... . We observe 15, 25, 40, ... is in row 15. So A(1,1) = 15.
The top left corner of the array:
  0   1   2    3    4    5    6    7    8    9
  1  15   8   12   44   19   62   26   30   91
  2   8   4   18   24   28   34   14   44   50
  3  12  18   27   96   42   51   57   66  198
  4  44  24   96  128   56  180   76   88  264
  5  19  28   42   56   65   79   33  102  116
  6  62  34   51  180   79  253  107  124  371
  7  26  14   57   76   33  107   45  138  157
  8  30  44   66   88  102  124  138  160  182
  9  91  50  198  264  116  371  157  182  544

Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21.
P. Arnoux, Some remarks about Fibonacci multiplication, Appl. Math. Lett. 2 (1989), 319-320.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly, Vol. 33, No. 1 (1995), pp. 3-8.

Cf. A022344 (norm), A035513, A120873, A287870, A348853.

See the formula section for the relationships with A000201, A003622, A019586, A035336, A101330.

lowerw(n) = (n+sqrtint(5*n^2))\2 ; \\ A000201
upperw(n) = (sqrtint(n^2*5)+n*3)\2; \\ A001950
compoundw(n) = (sqrtint(n^2*5)+n*3)\2 - 1; \\ A003622
wpair(p) = {my(x=p[2], y = p[1], z); while(1, my(n=1, ok=1); while(ok, my(xx = lowerw(n), yy = upperw(n)); if ((x == xx) && (y == yy), return([xx, yy])); if (xx > x, ok = 0); n++;); z = y; y += x; x = z;);}
row(p) = {my(x=p[1], y=p[2], u); while (1, my(n=1, ok=1); while(ok, my(xx = lowerw(n), yy = compoundw(n)); if ((x == xx) && (y == yy), return(n)); if (xx > x, ok = 0); n++;); u = x; x = y - u; y = u;);} \\ similar to A120873
wrow(p) = row(wpair(p));
prodpair(v1, v2) = my(j1=v1[1], j2 = v2[1], k1 = v1[2], k2 = v2[2]); [j1*j2 + k1*k2, j1*k2 + k1*j2 - k1*k2];
pair(n) = [lowerw(n+1), n];
T(n, k) = my(pn = pair(n), pk = pair(k), px = prodpair(pn, pk)); wrow(px)-1; \\ Michel Marcus, Sep 18 2022

A(x,y) = g(j1*j2 + k1*k2, j1*k2 + k1*j2 - k1*k2), where j1 = A035336(x+1), j2 = A035336(y+1), k1 = A003622(x+1), k2 = A003622(y+1) and g(j,k) = (if j = A000201(k+1) then k otherwise g(k,j-k)).
A(x,y) = A(y,x).
A(x,0) = x.
A(x, A(y,z)) = A(A(x,y), z).
A022344(A(x,y)) = A022344(x) * A022344(y).
A(A019586(x), A019586(y)) = A019586(A101330(x,y)). (conjectured)

A356875 Square array, n >= 0, k >= 0, read by descending antidiagonals. A(n,k) = A022341(n)*2^k.

Original entry on oeis.org

1, 2, 5, 4, 10, 9, 8, 20, 18, 17, 16, 40, 36, 34, 21, 32, 80, 72, 68, 42, 33, 64, 160, 144, 136, 84, 66, 37, 128, 320, 288, 272, 168, 132, 74, 41, 256, 640, 576, 544, 336, 264, 148, 82, 65, 512, 1280, 1152, 1088, 672, 528, 296, 164, 130, 69, 1024, 2560, 2304, 2176, 1344, 1056, 592, 328, 260, 138, 73

Offset: 0

Peter Munn, Sep 02 2022

The nonzero Fibbinary numbers (A003714) arranged in rows where each successive term is twice the preceding term; a (transposed) Fibbinary equivalent of A054582.
Write the first term in each row as Sum_{i in S} 2^i, where S is a set of nonnegative integers, then n = Sum_{i in S} F_i, where F_i is the i-th Fibonacci number, A000045(i).
More generally, if the terms are represented in binary, and the binary weighting of the digits (2^0, 2^1, 2^2, ...) is replaced with Fibonacci weighting (F_0, F_1, F_2, ...), we get the extended Wythoff array (A287870). If the weighting of the Zeckendorf representation is used (F_2, F_3, F_4, ...), we get the (unextended) Wythoff array (A035513).

			Square array A(n,k) begins:
   1    2    4    8    16    32    64   128 ...
   5   10   20   40    80   160   320   640 ...
   9   18   36   72   144   288   576  1152 ...
  17   34   68  136   272   544  1088  2176 ...
  21   42   84  168   336   672  1344  2688 ...
  33   66  132  264   528  1056  2112  4224 ...
  37   74  148  296   592  1184  2368  4736 ...
  41   82  164  328   656  1312  2624  5248 ...
  65  130  260  520  1040  2080  4160  8320 ...
  69  138  276  552  1104  2208  4416  8832 ...
  ...
The defining characteristic of a Fibbinary number is that its binary representation does not have a 1 followed by another 1. Shown in binary the array begins:
      1      10      100      1000 ...
    101    1010    10100    101000 ...
   1001   10010   100100   1001000 ...
  10001  100010  1000100  10001000 ...
  10101  101010  1010100  10101000 ...
  ...

See the comments for the relationship to: A000045, A003714, A035513, A054582, A287870.

See the formula section for the relationship to: A022290, A022341, A356874.

A(n,0) = A022341(n), otherwise A(n,k) = 2*A(n,k-1).
A287870(n+1,k+1) = A356874(floor(A(n,k)/2)).
A035513(n+1,k+1) = A022290(A(n,k)).

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

Showing 1-8 of 8 results.

cp's OEIS Frontend

A367293 Main diagonal of the extended Wythoff array (A287870).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A035513 Wythoff array read by falling antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A356874 Write n as Sum_{i in S} 2^(i-1), where S is a set of positive integers, then a(n) = Sum_{i in S} F_i, where F_i is the i-th Fibonacci number, A000045(i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A287869 Wythoff array with one extra column, read by antidiagonals downwards.

Views

Author

Keywords

Examples

References

Crossrefs

A357097 A multiplication table for the rows of the extended Wythoff array. See comments for definition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A356875 Square array, n >= 0, k >= 0, read by descending antidiagonals. A(n,k) = A022341(n)*2^k.

Views

Author

Keywords

Comments

Examples