A004001 -id:A004001 - cp's OEIS frontend

A087686 Elements of A004001 that repeat consecutively.

1, 2, 4, 7, 8, 12, 14, 15, 16, 21, 24, 26, 27, 29, 30, 31, 32, 38, 42, 45, 47, 48, 51, 53, 54, 56, 57, 58, 60, 61, 62, 63, 64, 71, 76, 80, 83, 85, 86, 90, 93, 95, 96, 99, 101, 102, 104, 105, 106, 109, 111, 112, 114, 115, 116, 118, 119, 120, 121, 123, 124, 125, 126, 127

Offset: 1

Roger L. Bagula, Sep 27 2003

nonn

Complement of A088359; A051135(a(n)) > 1. [Reinhard Zumkeller, Jun 03 2011]
From Antti Karttunen, Jan 18 2016: (Start)
This set of numbers is closed with respect to A004001, see A266188.
After 1, one more than the positions of zeros in A093879.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A004001, A051135, A093879.
Cf. A088359 (complement), A188163 (almost complement).
Cf. A080677 (the least monotonic left inverse).
Cf. also A266188, A265901, A265903, A267110, A267111, A267112.

import Data.List (findIndices)
a087686 n = a087686_list !! (n-1)
a087686_list = map succ $ findIndices (> 1) a051135_list
-- Reinhard Zumkeller, Jun 03 2011
(Scheme, with Antti Karttunen's IntSeq-library)
(define A087686 (MATCHING-POS 1 1 (lambda (n) (> (A051135 n) 1))))
;; Antti Karttunen, Jan 18 2016

Conway[n_Integer?Positive] := Conway[n] =Conway[Conway[n-1]] + Conway[n - Conway[n-1]] Conway[1] = Conway[2] = 1 digits=1000 a=Table[Conway[n], {n, 1, digits}]; b=Table[If[a[[n]]-a[[n-1]]==0, a[[n]], 0], {n, 2, digits}]; c=Delete[Union[b], 1]

Other identities. For all n >= 1:

A080677(a(n)) = n. [See comments in A080677.]

A088359 Numbers which occur only once in A004001.

Original entry on oeis.org

3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 28, 33, 34, 35, 36, 37, 39, 40, 41, 43, 44, 46, 49, 50, 52, 55, 59, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 77, 78, 79, 81, 82, 84, 87, 88, 89, 91, 92, 94, 97, 98, 100, 103, 107, 108, 110, 113, 117, 122, 129, 130, 131, 132

Offset: 1

Robert G. Wilson v, Sep 26 2003

nonn

Out of the first one million terms (a(10^6) = 510403), 258661 occur only once.
Complement of A087686; A051135(a(n)) = 1. - Reinhard Zumkeller, Jun 03 2011
From Antti Karttunen, Jan 18 2016: (Start)
In general, out of the first 2^(n+1) terms of A004001, 2^(n-1) - 1 terms (a quarter) occur only once. See also illustration in A265332.
One more than the positions of ones in A093879.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Positions of ones in A051135.
Cf. A188163 (same sequence with prepended 1).
Cf. A087686 (complement).
Cf. A004001, A093879, A265332, A266399.
Cf. also A267110, A267111, A267112.

import Data.List (elemIndices)
a088359 n = a088359_list !! (n-1)
a088359_list = map succ $ elemIndices 1 a051135_list
-- Reinhard Zumkeller, Jun 03 2011
(Scheme, with Antti Karttunen's IntSeq-library)
(define A088359 (ZERO-POS 1 1 (COMPOSE -1+ A051135)))
;; Antti Karttunen, Jan 18 2016

a[1] = 1; a[2] = 1; a[n_] := a[n] = a[ a[n - 1]] + a[n - a[n - 1]]; hc = Table[ a[n], {n, 1, 261}]; RunLengthEncodeOne[x_List] := Length[ # ] == 1 & /@ Split[x]; r = RunLengthEncodeOne[hc]; Select[ Range[ Length[r]], r[[ # ]] == True &]

From Antti Karttunen, Jan 18 2016: (Start)
Other identities.
For all n >= 0, a(A000079(n)) = A000051(n+1), that is, a(2^n) = 2^(n+1) + 1.
For all n >= 1:
a(n) = A004001(A266399(n)).
(End)

A080677 a(n) = n + 1 - A004001(n).

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12, 13, 13, 14, 15, 16, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 21, 22, 22, 22, 23, 23, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 32, 33, 33, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 35, 35, 35

Offset: 1

N. J. A. Sloane, Mar 03 2003

nonn

From Antti Karttunen, Jan 10 2016: (Start)
This is the sequence b(n) mentioned on page 229 (page 5 of PDF) in Kubo & Vakil paper, but using starting offset 1 instead of 2.
The recursive sum formula for A004001, a(n) = a(a(n-1)) + a(n-a(n-1)) can be written also as a(n) = a(a(n-1)) + a(A080677(n-1)).
This is the least monotonic left inverse for sequence A087686. Proof: Taking the first differences of this sequence yields the characteristic function for the complement of A188163, because A188163 gives the positions where A004001 increases, and this sequence increases by one whenever A004001 does not increase (and vice versa). Sequence A188163 is also 1 followed by A088359 (see comment in former), whose complement A087686 is, thus A087686 is also the complement of A188163, apart from the initial one. Note also how A087686 is closed with respect to A004001 (see A266188).
(End)

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.

Antti Karttunen, Table of n, a(n) for n = 1..8192
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Index entries for Hofstadter-type sequences

Cf. A004001, A087686, A088359, A162598, A188163, A265332, A266188, A267111.

(define (A080677 n) (- (+ 1 n) (A004001 n))) ;; Scheme code for A004001 given in that entry. - Antti Karttunen, Jan 10 2016

a(n) = n + 1 - A004001(n).
Other identities. For all n >= 1:
a(A087686(n)) = n. [See comments.] - Antti Karttunen, Jan 10 2016

A267111 Permutation of natural numbers: a(1) = 1, a(A087686(n)) = 2a(n-1), a(A088359(n)) = 1+2a(n), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001, the Hofstadter-Conway $10000 sequence.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 9, 11, 15, 10, 13, 14, 12, 16, 17, 19, 23, 31, 18, 21, 27, 22, 29, 30, 20, 25, 26, 28, 24, 32, 33, 35, 39, 47, 63, 34, 37, 43, 55, 38, 45, 59, 46, 61, 62, 36, 41, 51, 42, 53, 54, 44, 57, 58, 60, 40, 49, 50, 52, 56, 48, 64, 65, 67, 71, 79, 95, 127, 66, 69, 75, 87, 111, 70, 77, 91, 119, 78, 93, 123

Offset: 1

Antti Karttunen, Jan 10 2016

Antti Karttunen, Table of n, a(n) for n = 1..8192
Antti Karttunen, Entanglement Permutations, 2016-2017
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Index entries for Hofstadter-type sequences
Index entries for sequences that are permutations of the natural numbers

Inverse: A267112.
Cf. A004001, A080677, A087686, A088359, A093879, A267108, A267109.
Similar or related permutations: A006068, A054429, A276441, A233275, A233277, A276343, A276345, A276445.
Cf. also permutations A266411, A266412 and arrays A265901, A265903.

a(1) = 1; for n > 1, if A093879(n-1) = 0 [when n is in A087686], a(n) = 2*a(A080677(n)-1), otherwise [when n is in A088359], a(n) = 1 + 2*a(A004001(n)-1).
Equally, for n > 1, if A093879(n-1) = 0, a(n) = 2*a(n - A004001(n)), otherwise a(n) = 1 + 2*a(A004001(n)-1). [Above formula in a more symmetric form.]
As a composition of other permutations:
a(n) = A054429(A276441(n)).
a(n) = A233275(A276343(n)).
a(n) = A233277(A276345(n)).
a(n) = A006068(A276445(n)).
Other identities. For all n >= 0:
a(2^n) = 2^n. [Follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper.]

A055748 A chaotic cousin of the Hofstadter-Conway sequence A004001.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 11, 13, 15, 15, 14, 15, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 18, 18, 18, 19, 21, 23, 21, 20, 24, 25, 26, 28, 27, 26, 30, 30, 29, 30, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33

Offset: 1

N. J. A. Sloane, Jul 13 2000

See FORMULA for definition.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

Martin Møller Skarbiniks Pedersen, Table of n, a(n) for n = 1..10000
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
Martin Møller Skarbiniks Pedersen, Plot of first 100000000 values (pdf)
Martin Møller Skarbiniks Pedersen, Plot of a(n)/n for the first 100000000 values (pdf)
Martin Møller Skarbiniks Pedersen, Plot of a(n) for the first 100,000,000 values (png)
Martin Møller Skarbiniks Pedersen, Plot of a(n)/n for the first 100000000 values (png)
K. Pinn, A chaotic cousin of Conway's recursive sequence, Experimental Mathematics, 9:1 (2000), 55-65.
Index entries for Hofstadter-type sequences

Cf. A004001, A005185.

A055748 := proc(n) option remember; if n<=2 then 1 else A055748(A055748(n-1))+A055748(n-1-A055748(n-2)); fi; end;

a[n_] := a[n] = If[n < 3, 1, a[a[n - 1]] + a[n - a[n - 2] - 1]]; Array[a, 70] (* Michael De Vlieger, Mar 29 2017 *)

a(1) = 1, a(2) = 1, a(n) = a(a(n-1)) + a(n - a(n-2) - 1) for n >= 3. [Jaroslav Krizek, Dec 09 2009]

A093879 First differences of A004001.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0

Offset: 1

N. J. A. Sloane, May 27 2004

All the terms are 0 or 1: it is easy to show that if {b(n)} = A004001, b(n)>=b(n-1) and b(n)Benoit Cloitre, Jun 05 2004

R. J. Mathar, Table of n, a(n) for n = 1..9999
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
D. Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.

Cf. A004001, A051135, A087686, A088359, A188163.

h:=[n le 2 select 1 else Self(Self(n-1)) + Self(n-Self(n-1)): n in [1..160]];
A093879:= func< n | h[n+1] - h[n] >;
[A093879(n): n in [1..120]]; // G. C. Greubel, May 19 2024

a[1] = a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; t = Table[a[n], {n, 110}]; Drop[t, 1] - Drop[t, -1] (* Robert G. Wilson v, May 28 2004 *)

{m=106;v=vector(m,j,1);for(n=3,m,a=v[v[n-1]]+v[n-v[n-1]];v[n]=a);for(n=2,m,print1(v[n]-v[n-1],","))}

@CachedFunction
def h(n): return 1 if (n<3) else h(h(n-1)) + h(n - h(n-1))
def A093879(n): return h(n+1) - h(n)
[A093879(n) for n in range(1,101)] # G. C. Greubel, May 19 2024

(define (A093879 n) (- (A004001 (+ 1 n)) (A004001 n))) ;; Code for A004001 given in that entry. - Antti Karttunen, Jan 18 2016

From Antti Karttunen, Jan 18 2016: (Start)
a(n) = A004001(n+1) - A004001(n).
Other identities. For all n >= 1:
a(A087686(n+1)-1) = 0.
a(A088359(n)-1) = 1.
a(n) = 1 if and only if A051135(n+1) = 1.
(End)

More terms and PARI code from Klaus Brockhaus and Robert G. Wilson v, May 27 2004

A051135 a(n) = number of times n appears in the Hofstadter-Conway $10000 sequence A004001.

Original entry on oeis.org

2, 2, 1, 3, 1, 1, 2, 4, 1, 1, 1, 2, 1, 2, 3, 5, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 7, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3

Offset: 1

Robert Lozyniak (11(AT)onna.com)

If the initial 2 is changed to a 1, the resulting sequence (A265332) has the property that if all 1's are deleted, the remaining terms are the sequence incremented. - Franklin T. Adams-Watters, Oct 05 2006
a(A088359(n)) = 1 and a(A087686(n)) > 1; first differences of A188163. - Reinhard Zumkeller, Jun 03 2011
From Robert G. Wilson v, Jun 07 2011: (Start)
a(k)=1 for k = 3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 28, ..., ; (A088359)
a(k)=2 for k = 1, 2, 7, 12, 14, 21, 24, 26, 29, 38, 42, 45, 47, 51, 53, ..., ; (1 followed by A266109)
a(k)=3 for k = 4, 15, 27, 30, 48, 54, 57, 61, 86, 96, 102, 105, 112, ..., ; (A267103)
a(k)=4 for k = 8, 31, 58, 62, 106, 116, 120, 125, 192, 212, 222, 226, ..., ;
a(k)=5 for k = 16, 63, 121, 126, 227, 242, 247, 253, 419, 454, 469, ..., ;
a(k)=6 for k = 32, 127, 248, 254, 475, 496, 502, 509, 894, 950, 971, ..., ;
a(k)=7 for k = 64, 255, 503, 510, 978, 1006, 1013, 1021, 1872, 1956, ..., ;
a(k)=8 for k = 128, 511, 1014, 1022, 1992, 2028, 2036, 2045, 3864, ..., ;
a(k)=9 for k = 256, 1023, 2037, 2046, 4029, 4074, 4083, 4093, 7893, ..., ;
a(k)=10 for k = 512, 2047, 4084, 4094, 8113, 8168, 8178, 8189, ..., . (End)
Compare above to array A265903. - Antti Karttunen, Jan 18 2016

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Eric Weisstein's World of Mathematics, Hofstadter-Conway $10,000 Sequence.
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences

Cf. A004001, A087686, A093879, A188163, A266109, A267103 and array A265903.
Cf. A088359 (positions of ones).
Cf. A265332 (essentially the same sequence, but with a(1) = 1 instead of 2).

import Data.List (group)
a051135 n = a051135_list !! (n-1)
a051135_list = map length $ group a004001_list
-- Reinhard Zumkeller, Jun 03 2011

nmax:=200;
h:=[n le 2 select 1 else Self(Self(n-1)) + Self(n - Self(n-1)): n in [1..5*nmax]]; // h = A004001
A188163:= function(n)
   for j in [1..3*nmax+1] do
       if h[j] eq n then return j; end if;
   end for;
end function;
A051135:= func< n | A188163(n+1) - A188163(n) >;
[A051135(n): n in [1..nmax]]; // G. C. Greubel, May 20 2024

a[1]:=1: a[2]:=1: for n from 3 to 300 do a[n]:=a[a[n-1]]+a[n-a[n-1]] od: A:=[seq(a[n],n=1..300)]:for j from 1 to A[nops(A)-1] do c[j]:=0: for n from 1 to 300 do if A[n]=j then c[j]:=c[j]+1 else fi od: od: seq(c[j],j=1..A[nops(A)-1]); # Emeric Deutsch, Jun 06 2006

a[1] = 1; a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; t = Array[a, 250]; Take[ Transpose[ Tally[t]][[2]], 105] (* Robert G. Wilson v, Jun 07 2011 *)

@CachedFunction
def h(n): return 1 if (n<3) else h(h(n-1)) + h(n - h(n-1)) # h=A004001
def A188163(n):
    for j in range(1,2*n+1):
        if h(j)==n: return j
def A051135(n): return A188163(n+1) - A188163(n)
[A051135(n) for n in range(1,201)] # G. C. Greubel, May 20 2024

(define (A051135 n) (- (A188163 (+ 1 n)) (A188163 n))) ;; Antti Karttunen, Jan 18 2016

From Antti Karttunen, Jan 18 2016: (Start)
a(n) = A188163(n+1) - A188163(n). [after Reinhard Zumkeller's Jun 03 2011 comment above]
Other identities:
a(n) = 1 if and only if A093879(n-1) = 1. [See A188163 for a reason.]
(End)

More terms from Jud McCranie

Added links (in parentheses) to recently submitted related sequences - Antti Karttunen, Jan 18 2016

A188163 Smallest m such that A004001(m) = n.

Original entry on oeis.org

1, 3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 28, 33, 34, 35, 36, 37, 39, 40, 41, 43, 44, 46, 49, 50, 52, 55, 59, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 77, 78, 79, 81, 82, 84, 87, 88, 89, 91, 92, 94, 97, 98, 100, 103, 107, 108, 110, 113, 117, 122

Offset: 1

Reinhard Zumkeller, Jun 03 2011

nonn

How is this related to A088359? - R. J. Mathar, Jan 09 2013
It is not hard to show that a(n) exists for all n, and in particular a(n) < 2^n. - Charles R Greathouse IV, Jan 13 2013
From Antti Karttunen, Jan 10 & 18 2016: (Start)
Positions of records in A004001. After 1 the positions where A004001 increases (by necessity by one).
An answer to the question of R. J. Mathar above: This sequence is equal to A088359 with prepended 1. This follows because at each of its unique values (terms of A088359), A004001 must grow, but it can grow nowhere else. See Kubo and Vakil paper and especially the illustrations of Q and R-trees on pages 229-230 (pages 5 & 6 in PDF) and also in sequence A265332.
Obviously A004001 can obtain unique values only at points which form a subset (A266399) of this sequence.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
User "Panurge", Frankl's conjecture and Oeis sequence A188163, Mathoverflow.net, Mar 29 2016.
Eric Weisstein's World of Mathematics, Hofstadter-Conway $10,000 Sequence.
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences

Equal to A088359 with prepended 1.
Column 1 of A265901, Row 1 of A265903.
Cf. A051135 (first differences).
Cf. A087686 (complement, apart from the initial 1).
Cf. A004001 (also the least monotonic left inverse of this sequence).
Cf. A093879, A265332.
Cf. A266399 (a subsequence).

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a188163 n = succ $ fromJust $ elemIndex n a004001_list

h:=[n le 2 select 1 else Self(Self(n-1)) + Self(n - Self(n-1)): n in [1..500]]; // h=A004001
A188163:= function(n)
   for j in [1..2*n+1] do
       if h[j] eq n then return j; end if;
   end for;
end function;
[A188163(n): n in [1..100]]; // G. C. Greubel, May 20 2024

A188163 := proc(n)
    for a from 1 do
        if A004001(a) = n then
            return a;
        end if;
    end do:
end proc: # R. J. Mathar, May 15 2013

h[1] = 1; h[2] = 1; h[n_] := h[n] = h[h[n-1]] + h[n - h[n-1]];
a[n_] := For[m = 1, True, m++, If[h[m] == n, Return[m]]];
Array[a, 64] (* Jean-François Alcover, Jan 27 2018 *)

@CachedFunction
def h(n): return 1 if (n<3) else h(h(n-1)) + h(n - h(n-1)) # h=A004001
def A188163(n):
    for j in range(1,2*n+2):
        if h(j)==n: return j
[A188163(n) for n in range(1,101)] # G. C. Greubel, May 20 2024

(define A188163 (RECORD-POS 1 1 A004001))
;; Code for A004001 given in that entry. Uses also my IntSeq-library. - Antti Karttunen, Jan 18 2016

Other identities. For all n >= 1:
A004001(a(n)) = n and A004001(m) < n for m < a(n).
A051135(n) = a(n+1) - a(n).

A267112 Permutation of natural numbers: a(1) = 1; a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 9, 12, 10, 15, 13, 14, 11, 16, 17, 21, 18, 27, 22, 24, 19, 31, 28, 29, 23, 30, 25, 26, 20, 32, 33, 38, 34, 48, 39, 42, 35, 58, 49, 51, 40, 54, 43, 45, 36, 63, 59, 60, 50, 61, 52, 53, 41, 62, 55, 56, 44, 57, 46, 47, 37, 64, 65, 71, 66, 86, 72, 76, 67, 106, 87, 90, 73, 96, 77, 80, 68, 121, 107, 109, 88

Offset: 1

Antti Karttunen, Jan 10 2016

This sequence can be represented as a binary tree. Each left hand child is produced as A087686(1+n), and each right hand child as A088359(n), when their parent contains n:
                                    |
                 ...................1...................
                2                                       3
      4......../ \........5                   7......../ \........6
     / \                 / \                 / \                 / \
    /   \               /   \               /   \               /   \
   /     \             /     \             /     \             /     \
  8       9          12       10         15       13         14       11
16 17   21 18      27  22   24  19     31  28   29  23     30  25   26  20
etc.
The level k of the tree contains all numbers of binary width k, like many base-2 related permutations (A003188, A054429, etc). For a proof, see A267110, which gives the contents of each parent node (for node containing n).
A276442 shows the mirror-image of the same tree.

Antti Karttunen, Table of n, a(n) for n = 1..8192
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Index entries for Hofstadter-type sequences
Index entries for sequences that are permutations of the natural numbers

Inverse: A267111.
Cf. A000079, A000225, A004001, A006127, A087686, A088359, A267110.
Similar or related permutations: A003188, A054429, A276442, A233276, A233278, A276344, A276346, A276446.
Cf. also permutations A266411, A266412 and arrays A265901, A265903.

a(1) = 1; after which, a(2n) = A087686(1+a(n)), a(2n+1) = A088359(a(n)).
As a composition of other permutations:
a(n) = A276442(A054429(n)).
a(n) = A276344(A233276(n)).
a(n) = A276346(A233278(n)).
a(n) = A276446(A003188(n)).
Other identities. For all n >= 0:
a(2^n) = 2^n. [Follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper.]
a(A000225(n)) = A006127(n), i.e., a((2^(n+1)) - 1) = 2^n + n. [Numbers at the right edge.]

A004074 a(n) = 2*A004001(n) - n, where A004001 is the Hofstadter-Conway $10000 sequence.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 4, 5, 4, 5, 4, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 4, 5, 6, 7, 6, 7, 8, 7, 8, 7, 6, 7, 8, 7, 8, 7, 6, 7, 6, 5, 4, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 5, 6, 7, 8, 9, 8, 9, 10, 11, 10, 11, 12, 11, 12, 11, 10, 11, 12, 13, 12, 13, 14, 13, 14, 13, 12

Offset: 1

N. J. A. Sloane

nonn

The sequence is 0 at 2^n for n = 1, 2, 3, ... The maximum value between 2^n and 2^(n+1) appears to be A072100(n). - T. D. Noe, Jun 04 2012

Hofstadter shows the plot of sequence A004001(n)-(n/2) at point 10:52 of the part two of DIMACS lecture. This sequence is obtained by doubling those values, thus producing only integers. Cf. also A249071. - Antti Karttunen, Oct 22 2014

T. D. Noe (first 10000 terms) and Antti Karttunen, Table of n, a(n) for n = 1..16384
D. R. Hofstadter, Analogies and Sequences: Intertwined Patterns of Integers and Patterns of Thought Processes, Lecture in DIMACS Conference on Challenges of Identifying Integer Sequences, Rutgers University, October 10 2014; Part 1, Part 2.
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.
Wikipedia, Blancmange curve
Index entries for Hofstadter-type sequences

Cf. A004001, A082590, A213057.

Cf. also A249071 (gives the even bisection halved), A233270 (also has a similar Blancmange curve appearance).

Clear[a]; a[1] = 1; a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; Table[2*a[n] - n, {n, 100}] (* T. D. Noe, Jun 04 2012 *)

(define (A004074 n) (- (* 2 (A004001 n)) n)) ;; Other code as in A004001. - Antti Karttunen, Oct 22 2014

a(2^n)=0; for n >= 1, Sum_{i=2^(n-1)..2^n} a(i) = A082590(n-2). - Benoit Cloitre, Jun 04 2004

More terms from Benoit Cloitre, Jun 04 2004

cp's OEIS Frontend

A087686 Elements of A004001 that repeat consecutively.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A088359 Numbers which occur only once in A004001.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A080677 a(n) = n + 1 - A004001(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Scheme

Formula

A267111 Permutation of natural numbers: a(1) = 1, a(A087686(n)) = 2*a(n-1), a(A088359(n)) = 1+2*a(n), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001, the Hofstadter-Conway $10000 sequence.

Views

Author

Keywords

Links

Crossrefs

Formula

A055748 A chaotic cousin of the Hofstadter-Conway sequence A004001.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A093879 First differences of A004001.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Scheme

Formula

Extensions

A051135 a(n) = number of times n appears in the Hofstadter-Conway $10000 sequence A004001.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

A267111 Permutation of natural numbers: a(1) = 1, a(A087686(n)) = 2a(n-1), a(A088359(n)) = 1+2a(n), where A088359 and A087686 = numbers that occur only once (resp. more than once) in A004001, the Hofstadter-Conway $10000 sequence.