A087686 -id:A087686 - cp's OEIS frontend

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

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

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

A267110 If A051135(n) = 1, then a(n) = A004001(n) - 1, otherwise a(n) = n - A004001(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 16 2016

For n > 1, a(n) gives the contents of the parent of the node which contains n in A267112-tree.
Each n > 0 occurs exactly twice, in positions A088359(n) and A087686(n+1).
The sequence maps each n > 1 to a number which is one digit shorter in binary system (cf. "Other identities"). This follows because A004001 is monotonic and A004001(2^n) = 2^(n-1) (see properties (2) and (3) given on page 227 of Kubo & Vakil paper, or page 3 in PDF), and also how the frequency counts Q_n for A004001 are recursively constructed (see Kubo & Vakil paper, p. 229 or A265332 for the illustration).

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, A051135, A070939, A087686, A088359, A265332, A267108, A267109, A267112.

(define (A267110 n) (if (= 1 (A051135 n)) (- (A004001 n) 1) (- n (A004001 n))))

If A051135(n) = 1 [Equally: if A265332(n) = 1], then a(n) = A004001(n) - 1, otherwise a(n) = n - A004001(n).
Other identities. For all n >= 2:
A070939(a(n)) = A070939(n) - 1. [See Comments section.]

A162598 Ordinal transform of A265332.

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Jul 07 2009

This is a fractal sequence.
It appears that each group of 2^k terms starts with 1 and ends with the remaining powers of two from 2^k down to 2^1.
From Antti Karttunen, Jan 09-12 2016: (Start)
This is ordinal transform of A265332, which is modified A051135 (with a(1) = 1, instead of 2). -  after Franklin T. Adams-Watters' original definition for this sequence.
A000079 (powers of 2) indeed gives the positions of ones in this sequence. This follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper (page 3 of PDF), which together also imply the pattern observed above, more clearly represented as:
a(2) = 1.
a(3..4) = 2, 1.
a(6..8) = 4, 2, 1.
a(13..16) = 8, 4, 2, 1.
a(28..31) = 16, 8, 4, 2, 1.
etc.
(End)

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, A051135, A080677, A087686.
Row index of A265901, column index of A265903.
Cf. A265332 (corresponding other index).
Cf. A000079 (positions of ones).
Cf. A000225 (from the term 3 onward the positions of 2's).
Cf. A000325 (from its third term 5 onward the positions of 3's, which occur always as the last term before the next descending subsequence of powers of two).

terms = 100;
h[1] = 1; h[2] = 1;
h[n_] := h[n] = h[h[n - 1]] + h[n - h[n - 1]];
t = Array[h, 2*terms];
A051135 = Take[Transpose[Tally[t]][[2]], terms];
b[_] = 1;
a[n_] := a[n] = With[{t = If[n == 1, 1, A051135[[n]]]}, b[t]++];
Array[a, terms] (* Jean-François Alcover, Dec 19 2021, after Robert G. Wilson v in A051135 *)

Let b(1) = 1, b(n) = A051135(n) for n > 1. Then a(n) is the number of b(k) that equal b(n) for 1 <= k <= n: sum( 1, 1<=k<=n and a(k)=a(n) ).

If A265332(n) = 1, then a(n) = A004001(n), otherwise a(n) = a(A080677(n)-1) = a(n - A004001(n)). - Antti Karttunen, Jan 09 2016

Name amended by Antti Karttunen, Jan 09 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Scheme

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

SageMath

Scheme

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

SageMath

Scheme

Formula

A267110 If A051135(n) = 1, then a(n) = A004001(n) - 1, otherwise a(n) = n - A004001(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A162598 Ordinal transform of A265332.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A267103 Row 3 of A265903; numbers that occur exactly three times in A004001.