A064105 -id:A064105 - cp's OEIS frontend

A005374 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).

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

Offset: 0

N. J. A. Sloane

Rule for constructing the sequence: a(n) = An, where An denotes the Lamé antecessor to (or right shift of) n, which is found by replacing each Lm(i) in the Zeckendorffian expansion (obtained by repeatedly subtracting the largest Lamé number (A000930) you can until nothing remains) by Lm(i-1) (A1=1). For example: 58 = 41 + 13 + 4, so a(58)= 28 + 9 + 3 = 40.
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
As is shown on page 137 of Goedel, Escher, Bach, a recursively built tree structure can be obtained from this sequence:
  20.21..22..23.24.25.26.27.28
  .\./.../.../...\./...\./../
  ..14.15..16....17....18..19
  ...\./.../..../.......\./
  ....10.11...12........13
  .....\./.../........./
  ......7...8........9.
  .......\./......./
  ........5......6
  .........\.../
  ...........4
  ........../
  .........3
  ......../
  .......2
  ....\./
  .....1
To construct the tree: node n is connected to the node a(n) below it:
  ...n
  ../
  a(n)
For example:
  ...8
  ../
  .5
since a(8) = 5. If the nodes of the tree are read from bottom-to-top, left-to-right, we obtain the natural numbers: 1, 2, 3, 4, 5, 6, ...
The tree has a recursive structure, since the following construct
  ....../
  .....x
  ..../
  ...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
  ..\./...../
  ...x.....x
  ....\.../
  ......x
(End)
From Pierre Letouzey, Feb 20 2025: (Start)
For all n >= 0, A005206(n) <= a(n) <= A005375(n), as proved in Letouzey-Li-Steiner link. Last equality A005206(n) = a(n) occurs at n = 12; last equality a(n) = A005375(n) occurs at n = 18.
For all n >= 0, |a(n)-c*n| < 0.996, where c is the real root of x^3 + x - 1 = 0, c = 0.682327803828019327369483739... Proved in Letouzey link. (End)
The bound for |a(n)-c*n| is improved to 0.862 in Shallit (2025). - Jeffrey Shallit, Mar 09 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).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Benoit Cloitre, Plot of a(n)-c*n where c=0.6823278...
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.
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
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.
Programming Puzzles & Code Golf Stack Exchange, Hofstadter H-sequence
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.
Eric Weisstein's World of Mathematics, Hofstadter H-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences
Index entries for sequences from "Goedel, Escher, Bach"

Cf. A202340, A202341, A202342.

a005374 n = a005374_list !! n
a005374_list = 0 : 1 : zipWith (-)
   [2..] (map (a005374 . a005374) $ tail a005374_list)
-- Reinhard Zumkeller, Dec 17 2011

A005374 := proc(n) option remember: if n<1 then 0 else n-A005374(A005374(A005374(n-1))) fi end: # Francisco Salinas (franciscodesalinas(AT)hotmail.com), Jan 06 2002
H:=proc(n) option remember; if n=1 then 1 else n-H(H(H(n-1))); fi; end proc;

a[n_]:= a[n]= n - a[a[a[n-1]]]; a[0] = 0; Table[a[n], {n, 0, 73}] (* Jean-François Alcover, Jul 28 2011 *)

first(m)=my(v=vector(m));v[1]=1;for(i=2,m,v[i]=i-v[v[v[i-1]]]);concat([0],v) \\ Anders Hellström, Dec 07 2015

@CachedFunction # a = A005374
def a(n): return 0 if (n==0) else n - a(a(a(n-1)))
[a(n) for n in range(101)] # G. C. Greubel, Nov 14 2022

Conjecture: a(n) = floor(c*n) + 0 or 1, where c is the real root of x^3+x-1 = 0, c=0.682327803828019327369483739... - Benoit Cloitre, Nov 05 2002 [Proved by Letouzey, see Letouzey link. - Pierre Letouzey, Feb 20 2025], [Also proved in Shallit (2025). - Jeffrey Shallit, Mar 09 2025]
a(n) = A020942(n) - 2*A064105(n) + A064106(n) (e.g. for n = 30 we get 20 = 93 - 2*137 + 201), and a(n) = 2*A020942(n) - A064105(n) - A023443(n) (e.g. for n = 30 we get 20 = 2*93 - 137 - 29). [Corrected by N. J. A. Sloane, Apr 29 2024 at the suggestion of A.H.M. Smeets.]
Also: a(n) = a(n-1) + 1 if n-1 belongs to sequence A064105-A020942-A000012, a(n-1) otherwise.
Recurrence: a(n) = a(n-1) if n-1 belongs to sequence A020942, a(n-1) + 1 otherwise.
Recurrence for n>=3: a(n) = Lm(k-1) + a(n-Lm(k)), where Lm(n) denotes Lamé sequence A000930(n) (Lm(n) = Lm(n-1) + Lm(n-3)) and k is such that Lm(k)< n <= Lm(k+1). Special case: a(Lm(n)) = Lm(n-1) for n>=1.
For n > 0: a(A136495(n)) = n. - Reinhard Zumkeller, Dec 17 2011

More terms from James Sellers, Jul 12 2000

Additional comments and formulas from Diego Torres (torresvillarroel(AT)hotmail.com), Nov 23 2002

A136189 The 3rd-order Zeckendorf array, T(n,k), read by antidiagonals.

Original entry on oeis.org

1, 2, 5, 3, 8, 7, 4, 12, 11, 10, 6, 17, 16, 15, 14, 9, 25, 23, 22, 21, 18, 13, 37, 34, 32, 31, 27, 20, 19, 54, 50, 47, 45, 40, 30, 24, 28, 79, 73, 69, 66, 58, 44, 36, 26, 41, 116, 107, 101, 97, 85, 64, 53, 39, 29, 60, 170, 157, 148, 142, 125, 94, 77, 57, 43, 33, 88, 249, 230

Offset: 1

Clark Kimberling, Dec 20 2007

Rows satisfy this recurrence: T(n,k) = T(n,k-1) + T(n,k-3) for all k>=4.
Except for initial terms, (row 1) = A000930 (column 1) = A020942 (column 2) = A064105 (column 3) = A064106.
As a sequence, the array is a permutation of the natural numbers.
As an array, T is an interspersion (hence also a dispersion).

			Northwest corner:
  1  2  3  4  6  9  13  19 ...
  5  8 12 17 25 37  54  79 ...
  7 11 16 23 34 50  73 107 ...
 10 15 22 32 47 69 101 148 ...
 ...

Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Index entries for sequences that are permutations of the natural numbers

Cf. A000930, A035513, A134563, A136175, A136495, A202342.

Row 1 is the 3rd-order Zeckendorf basis, given by initial terms b(1)=1, b(2)=2, b(3)=3 and recurrence b(k) = b(k-1) + b(k-3) for k>=4. Every positive integer has a unique 3-Zeckendorf representation: n = b(i(1)) + b(i(2)) + ... + b(i(p)), where |i(h)-i(j)| >= 3. Rows of T are defined inductively: T(n,1) is the least positive integer not in an earlier row. T(n,2) is obtained from T(n,1) as follows: if T(n,1) = b(i(1)) + b(i(2)) + ... + b(i(p)), then T(n,k+1) = b(i(1+k)) + b(i(2+k)) + ... + b(i(p+k)) for k=1,2,3,... .

A(n, k) = A000930(k)*A202342(n) + A000930(k-2)*A136495(n) + A000930(k-1)*(n-1) for n > 1. - Alan Michael Gómez Calderón, Dec 23 2024

A020942 First column of 3rd-order Zeckendorf array A136189.

Original entry on oeis.org

1, 5, 7, 10, 14, 18, 20, 24, 26, 29, 33, 35, 38, 42, 46, 48, 51, 55, 59, 61, 65, 67, 70, 74, 78, 80, 84, 86, 89, 93, 95, 98, 102, 106, 108, 112, 114, 117, 121, 123, 126, 130, 134, 136, 139, 143, 147, 149, 153, 155, 158, 162, 164, 167, 171, 175, 177, 180, 184

Offset: 1

Clark Kimberling

I would like to get similar sequences where the least term in the representation is 2 [gives 2 8 11 15 21 27 30..., which is now A064105], 3, 4, 6, etc. They are the 2nd, 3rd, etc. columns of the 3rd-order Zeckendorf array. [See cross-references. - N. J. A. Sloane, Apr 29 2024]
These have now been entered in the OEIS as
column 1: A020942.
column 2: A064105.
column 3: A064106.
column 4: A372749.
column 5: A372750.
column 6: A372752.
column 7: A372756.
column 8: A372757.

			1=1; 5=4+1; 7=6+1; 10=9+1; etc.

A.H.M. Smeets, Table of n, a(n) for n = 1..20000
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A000930, A064105, A064106, A136189, A136496, A202342, A372749, A372750, A372752, A372756, A372757.

Any number n has unique representation as a sum of terms from {1, 2, 3, 4, 6, 9, 13, 19, ...} (cf. A000930) such that no two terms are adjacent or pen-adjacent; e.g., 7=6+1. Sequence gives all n where that representation involves 1.
Conjecture: a(n) = A202342(n) + n. - Sean A. Irvine, May 05 2019 [proved in corrected form in Shallit (2025); it should read a(n) = A202342(n) + n-1]
a(n) = A136496(n) - 1. - Jeffrey Shallit, Mar 08 2025

More terms from Naohiro Nomoto, Sep 17 2001

A064106 3rd column of 3rd-order Zeckendorf array A136189.

Original entry on oeis.org

3, 12, 16, 22, 31, 40, 44, 53, 57, 63, 72, 76, 82, 91, 100, 104, 110, 119, 128, 132, 141, 145, 151, 160, 169, 173, 182, 186, 192, 201, 205, 211, 220, 229, 233, 242, 246, 252, 261, 265, 271, 280, 289, 293, 299, 308, 317, 321, 330, 334, 340, 349, 353, 359, 368

Offset: 1

Naohiro Nomoto, Sep 17 2001

A.H.M. Smeets, Table of n, a(n) for n = 1..20000
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A020942, A064105, A136189, A202342.

Any number n has a unique representation as a sum of terms from {3, 4, 6, 9, 13, 19, ...} (cf. A000930) such that no two terms are adjacent or pen-adjacent; e.g. 12=9+3. Sequence gives all n where that representation involves 3.

a(n) = A064105(n) + A202342(n). - Alan Michael Gómez Calderón, Dec 22 2024

Offset corrected by N. J. A. Sloane, Apr 29 2024

A372749 4th column of the 3-Zeckendorf array (A136189).

Original entry on oeis.org

4, 17, 23, 32, 45, 58, 64, 77, 83, 92, 105, 111, 120, 133, 146, 152, 161, 174, 187, 193, 206, 212, 221, 234, 247, 253, 266, 272, 281, 294, 300, 309, 322, 335, 341, 354, 360, 369, 382, 388, 397, 410, 423, 429, 438, 451, 464, 470, 483, 489, 498, 511, 517, 526, 539

Offset: 1

A.H.M. Smeets, May 12 2024

nonn

The 3-Zeckendorf array (A136189) is based on the Narayana (Narayana's cow sequence A000930) weighted representation of n (see A350215).

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.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.

Cf. A000930, A136189, A350215.
The k-th row: A000930(n+2) (k=1)
The k-th column: A020942 (k=1), A064105 (k=2), A064106 (k=3), this sequence (k=4),  A372750 (k=5).
The k-th prepended column: A005374 (k=1), A202342 (k=4)

a(n) = A202342(n) + A136496(n) + A381841(n) - 2. - Jeffrey Shallit, Mar 08 2025

A372750 5th column of the 3-Zeckendorf array (A136189).

Original entry on oeis.org

6, 25, 34, 47, 66, 85, 94, 113, 122, 135, 154, 163, 176, 195, 214, 223, 236, 255, 274, 283, 302, 311, 324, 343, 362, 371, 390, 399, 412, 431, 440, 453, 472, 491, 500, 519, 528, 541, 560, 569, 582, 601, 620, 629, 642, 661, 680, 689, 708, 717, 730, 749, 758, 771

Offset: 1

A.H.M. Smeets, May 12 2024

nonn

The 3-Zeckendorf array (A136189) is based on the Narayana (Narayana's cow sequence A000930) weighted representation of n (see A350215).

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.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A000930, A136189, A350215.
The k-th row: A000930(n+2) (k=1)
The k-th column: A020942 (k=1), A064105 (k=2), A064106 (k=3), A372749 (k=4), this sequence (k=5).
The k-th prepended column: A005374 (k=1), A202342 (k=4)

a(n) = A202342(n) + A136496(n) + 2*A381841(n) - 3. - Jeffrey Shallit, Mar 08 2025

A372752 6th column of the 3-Zeckendorf array (A136189).

Original entry on oeis.org

9, 37, 50, 69, 97, 125, 138, 166, 179, 198, 226, 239, 258, 286, 314, 327, 346, 374, 402, 415, 443, 456, 475, 503, 531, 544, 572, 585, 604, 632, 645, 664, 692, 720, 733, 761, 774, 793, 821, 834, 853, 881, 909, 922, 941, 969, 997, 1010, 1038, 1051, 1070, 1098

Offset: 1

A.H.M. Smeets, May 12 2024

nonn

The 3-Zeckendorf array (A136189) is based on the Narayana (Narayana's cow sequence A000930) weighted representation of n (see A350215).

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.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A000930, A136189, A350215.
The k-th row: A000930(n+2) (k=1)
The k-th column: A020942 (k=1), A064105 (k=2), A064106 (k=3), A372749 (k=4), A372750 (k=5), this sequence (k=6).
The k-th prepended column: A005374 (k=1), A202342 (k=4)

a(n) = 2*A202342(n) + A136496(n) + 3*A381841(n) - 4. - Jeffrey Shallit, Mar 08 2025

A381841 Position of the n-th occurrence of the digit 3 in A105083(n-1) for n>=1.

Original entry on oeis.org

3, 9, 12, 16, 22, 28, 31, 37, 40, 44, 50, 53, 57, 63, 69, 72, 76, 82, 88, 91, 97, 100, 104, 110, 116, 119, 125, 128, 132, 138, 141, 145, 151, 157, 160, 166, 169, 173, 179, 182, 186, 192, 198, 201, 205, 211, 217, 220, 226, 229, 233, 239, 242, 246, 252, 258

Offset: 1

Jeffrey Shallit, Mar 08 2025

nonn

Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A064105, A105083, A136495, A136496, A202342.

a(n) = A064105(n) + 1.

a(n) = A136495(n) + A136496(n).

A372756 7th column of the 3-Zeckendorf array (A136189).

Original entry on oeis.org

13, 54, 73, 101, 142, 183, 202, 243, 262, 290, 331, 350, 378, 419, 460, 479, 507, 548, 589, 608, 649, 668, 696, 737, 778, 797, 838, 857, 885, 926, 945, 973, 1014, 1055, 1074, 1115, 1134, 1162, 1203, 1222, 1250, 1291, 1332, 1351, 1379, 1420, 1461, 1480, 1521

Offset: 1

A.H.M. Smeets, May 12 2024

nonn

The 3-Zeckendorf array (A136189) is based on the Narayana (Narayana's cow sequence A000930) weighted representation of n (see A350215).

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.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A000930, A136189, A350215.
The k-th row: A000930(n+2) (k=1), A372760 (k=2).
The k-th column: A020942 (k=1), A064105 (k=2), A064106 (k=3), A372749 (k=4), A372750 (k=5), A372752 (k=6), this sequence (k=7), A372757 (k=8).
The k-th prepended column: A005374 (k=1), A136495 (k=2), A023443 (k=3), A202342 (k=4), A372758 (k=5), A372759 (k=6).

a(n) = 3*A202342(n) + 2*A136496(n) + 4*A381841(n) - 6. - Jeffrey Shallit, Mar 08 2025

A372757 8th column of the 3-Zeckendorf array (A136189).

Original entry on oeis.org

19, 79, 107, 148, 208, 268, 296, 356, 384, 425, 485, 513, 554, 614, 674, 702, 743, 803, 863, 891, 951, 979, 1020, 1080, 1140, 1168, 1228, 1256, 1297, 1357, 1385, 1426, 1486, 1546, 1574, 1634, 1662, 1703, 1763, 1791, 1832, 1892, 1952, 1980, 2021, 2081, 2141

Offset: 1

A.H.M. Smeets, May 12 2024

nonn

The 3-Zeckendorf array (A136189) is based on the Narayana (Narayana's cow sequence A000930) weighted representation of n (see A350215).

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.
Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
Jeffrey Shallit, The Narayana Morphism and Related Words, arXiv:2503.01026 [math.CO], 2025.

Cf. A000930, A136189, A350215.
The k-th row: A000930(n+2) (k=1), A372760 (k=2).
The k-th column: A020942 (k=1), A064105 (k=2), A064106 (k=3), A372749 (k=4), A372750 (k=5), A372752 (k=6), A372756 (k=7), this sequence (k=8).
The k-th prepended column: A005374 (k=1), A136495 (k=2), A023443 (k=3), A202342 (k=4), A372758 (k=5), A372759 (k=6).

a(n) = 4*A202342(n) + 3*A136496(n) + 6*A381841(n) - 9. - Jeffrey Shallit, Mar 08 2025

cp's OEIS Frontend

A005374 Hofstadter H-sequence: a(n) = n - a(a(a(n-1))).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A136189 The 3rd-order Zeckendorf array, T(n,k), read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A020942 First column of 3rd-order Zeckendorf array A136189.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A064106 3rd column of 3rd-order Zeckendorf array A136189.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A372749 4th column of the 3-Zeckendorf array (A136189).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A372750 5th column of the 3-Zeckendorf array (A136189).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A372752 6th column of the 3-Zeckendorf array (A136189).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A381841 Position of the n-th occurrence of the digit 3 in A105083(n-1) for n>=1.

Views

Author

Keywords

Links

Crossrefs

Formula

A372756 7th column of the 3-Zeckendorf array (A136189).

Views

Author

Keywords

Comments