A004001 -id:A004001 - cp's OEIS frontend

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

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

A283470 a(n) = A004001(A004001(n-1)) XOR A004001(n-A004001(n-1)), a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 0, 0, 3, 0, 0, 0, 1, 0, 7, 7, 0, 0, 0, 0, 1, 0, 3, 2, 2, 1, 14, 14, 15, 15, 15, 0, 0, 0, 0, 0, 1, 0, 3, 2, 5, 5, 6, 7, 4, 4, 5, 4, 4, 3, 3, 3, 2, 29, 29, 30, 30, 30, 31, 31, 31, 31, 0, 0, 0, 0, 0, 0, 1, 0, 3, 2, 5, 4, 4, 7, 4, 5, 10, 10, 11, 10, 9, 9, 14, 15, 15, 14, 14, 14, 13, 10, 11, 11, 10, 9, 9, 6, 6, 6, 7, 6, 6, 5, 5, 5, 4, 4, 4, 4, 3

Offset: 1

Antti Karttunen, Mar 18 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..32768

Cf. A003987, A080677, A283468, A283469, A283472, A283471 (positions of zeros), A283473 (positions where coincides with A004001).

Cf. also A283677.

a[n_] := a[n] = If[n <= 2, 1, a[a[n - 1]] + a[n - a[n - 1]]]; Table[BitXor[a[#], a[n - #]] &@ a[n - 1] + Boole[n <= 2], {n, 107}] (* Michael De Vlieger, Mar 18 2017, after Robert G. Wilson v at A004001 *)

(define (A283470 n) (if (<= n 2) 1 (A003987bi (A004001 (A004001 (- n 1))) (A004001 (- n (A004001 (- n 1)))))))
;; A003987bi implements bitwise-XOR (see A003987). Code for A004001 given under that entry.

a(n) = A004001(A004001(n-1)) XOR A004001(A080677(n-1)), where XOR is bitwise-xor (A003987)
Other identities. For all n >= 1:
a(n) = A283469(n) - A283472(n).
A004001(n) = a(n) + 2*A283472(n).

Erroneous b-file replaced by a correct one - Antti Karttunen, Feb 24 2018

A284019 The "Hofstadter chaotic heart" sequence: a(n) = A004001(n) - A005185(n).

Original entry on oeis.org

0, 0, 0, -1, 0, 0, -1, -1, -1, 0, 1, -1, 0, 0, -2, -1, -1, -1, 0, 0, 0, 1, 2, -2, 1, 1, -1, 0, 0, 0, -4, -1, 0, -2, -2, 1, 1, -1, 1, 1, 1, 1, 1, 2, 2, 3, 3, -5, 4, 4, -1, 2, 4, 0, 1, 3, -1, 1, 0, 0, 0, 0, -8, -1, 2, -4, 0, 3, -2, -2, 1, 1, 0, 2, 2, 3, 1, 4, 4, 2, 2, 4, 4, 2, 4, 3, 2

Offset: 1

Altug Alkan, Mar 18 2017

See also scatterplot in Links section.
From Nathan Fox, Mar 30 2017: (Start)
The pattern in the graph presumably comes from the known pattern in the Conway sequence minus n/2 (A004001) combined with the "sausage" pattern of the Q-sequence (A005185). Since the Q-sequence seems to remain close to n/2, the patterns combine in this way.
This means that the bottoms of the hearts should be roughly at powers of 2 and the joins between them should be where the sausages thin out. (End) [Corrected by Altug Alkan, Apr 01 2017]
Note that this comment says that the indices where the bottoms of the hearts occur (the local minima) are roughly powers of 2. For example, a(8056) = -317 is a local minimum close to 2^13. - N. J. A. Sloane, Apr 01 2017

			a(4) = -1 since a(4) = A004001(4) - A005185(4) = 2 - 3 = -1.

Altug Alkan, Table of n, a(n) for n = 1..100000
Altug Alkan, Alternative Scatterplot of A284019
Altug Alkan, Nathan Fox, and Orhan Ozgur Aybar, On Hofstadter Heart Sequences, Complexity, 2017.
Index entries for Hofstadter-type sequences

Cf. A004001, A005185, A284606, A286560, A286569.

A005185:= proc(n) option remember; procname(n-procname(n-1)) +procname(n-procname(n-2)) end proc:
A005185(1):= 1: A005185(2):= 1:
A004001:= proc(n) option remember; procname(procname(n-1)) +procname(n-procname(n-1)) end proc:
A004001(1):= 1: A004001(2):= 1:
A284019:= map(A004001 - A005185, [$1..1000]):
seq(A284019[i], i=1..1000); # Altug Alkan, Mar 31 2017

a[n_] := a[n] = If[n <= 2, 1, a[a[n - 1]] + a[n - a[n - 1]]]; b[1] = b[2] = 1; b[n_] := b[n] = b[n - b[n - 1]] + b[n - b[n - 2]]; Table[a@ n - b@ n, {n, 87}] (* Michael De Vlieger, Mar 18 2017, after Robert G. Wilson v at A004001 *)

q=vector(1000); h=vector(1000); q[1]=q[2]=1; for(n=3, #q, q[n]=q[n-q[n-1]]+q[n-q[n-2]]); h[1]=h[2]=1; for(n=3, #h, h[n]=h[h[n-1]]+h[n-h[n-1]]); vector(1000, n, h[n]-q[n])

(define (A284019 n) (- (A004001 n) (A005185 n))) ;; Needs also Scheme-code included in those two entries. - Antti Karttunen, Mar 22 2017

Graphically descriptive name added by Antti Karttunen with permission from D. R. Hofstadter, Mar 29 2017

A286560 Compound filter (summands of A004001 & summands of A005185): a(n) = P(A286541(n), A286559(n)), where P(n,k) is sequence A000027 used as a pairing function, with a(1) = a(2) = 0.

Original entry on oeis.org

0, 0, 1, 2, 5, 41, 71, 71, 198, 313, 484, 922, 1153, 1201, 2105, 1565, 2588, 4046, 5001, 7443, 7443, 8851, 10671, 19589, 16570, 16935, 22254, 25313, 25313, 25313, 42891, 28793, 32768, 52795, 65504, 59178, 73355, 89033, 88632, 107660, 129045, 129045, 153471, 167646, 167646, 182446, 182446, 336130, 197244, 233297, 330472, 307358, 270167, 355325, 378466, 332156

Offset: 1

Antti Karttunen, May 18 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Pairing Function

Cf. A004001, A005185, A284019, A286541, A286559, A286569.

(define (A286560 n) (if (<= n 2) 0 (* (/ 1 2) (+ (expt (+ (A286541 n) (A286559 n)) 2) (- (A286541 n)) (- (* 3 (A286559 n))) 2))))

a(1) = a(2) = 0, for n > 2, a(n) = (1/2)*(2 + ((A286541(n)+A286559(n))^2) - A286541(n) - 3*A286559(n)).

A095901 A004001 (mod 2).

Original entry on oeis.org

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

Offset: 1

Robert G. Wilson v, Jun 12 2004

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A000035, A004001.
Cf. A095902 (number of odd entries less than or equal to 2^n).
Cf. A283480 (partial sums).
Characteristic function of A283481.

a[1] = a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; Table[ a[n], {n, 105}]

(define (A095901 n) (A000035 (A004001 n))) ;; Further code found under those two entries, Antti Karttunen, Mar 21 2017

a(n) = A004001(n) mod 2.

A265754 Reduced frequency counts for A004001: a(n) = A265332(n+1) - A036987(n).

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 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, 6, 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, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5

Offset: 1

Antti Karttunen, Jan 10 2016

nonn

Can be generated recursively by first setting R_1 = (1), after which each R_n is obtained by replacing in R_{n-1} each term k with terms 1 .. k, followed by final n. This sequence is then obtained by concatenating all levels R_1, R_2, ..., R_inf together. See page 230 in Kubo-Vakil paper (page 6 in PDF).
Deleting all 1's and decrementing the remaining terms by one gives the sequence back.
Comment from N. J. A. Sloane, Nov 05 2017: (Start)
The following simple Pascal-like triangle produces the same sequence.  Construct a triangle T(n,k) of strings (with 0 <= k <= n), where T(0,0) = {1}, T(n,n) = {n+1}, and otherwise T(n,k) is the concatenation of T(n-1,k-1) and T(n-1,k). The first few rows of the triangle (where the strings T(n,k) are shown without spaces for legibility) are:
1
1,2
1,12,3
1,112,123,4
1,1112,112123,1234,5
1,11112,1112112123,1121231234,12345,6
...
Now read the strings across the rows to get the sequence. T(n,k) has length binomial(n,k). (End)

			Illustration of the sequence as a tree:
             1
            / \
           1   2
          /   /|\
         1   1 2 3_________
        /   / /| | \  \    \
       1   1 1 2 1  2  3__  4________
      /   / / /| | / \ |\ \  \ \ \ \ \
     1   1 1 1 2 1 1 2 1 2 3  1 2 3 4 5
etc.
Compare with the illustration in A265332.

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

Cf. A004001, A036987, A054429, A070939, A265332, A266348, A266349.
Cf. A000225 (positions of records, where n appears first time).
Cf. A266640 (obtained from the mirror image of the same tree).
See A293959 for another version.

a(n) = A265332(n+1) - A036987(n).
As a recurrence: If A036987(n) = 1 [when n is of the form 2^k -1], a(n) = A070939(n), else if a(n+1) = 1, a(n) = a(2^A000523(n) - A266349(n)), otherwise a(n) = a(n+1)-1.
Other identities. For all n >= 1:
a(n) = A266640(A054429(n)).
a(A000225(n)) = n.

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

Original entry on oeis.org

1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 8, 13, 10, 9, 11, 31, 30, 28, 24, 16, 29, 26, 20, 25, 18, 17, 27, 22, 21, 19, 23, 63, 62, 60, 56, 48, 32, 61, 58, 52, 40, 57, 50, 36, 49, 34, 33, 59, 54, 44, 53, 42, 41, 51, 38, 37, 35, 55, 46, 45, 43, 39, 47, 127, 126, 124, 120, 112, 96, 64, 125, 122, 116, 104, 80, 121, 114, 100, 72, 113, 98

Offset: 1

Antti Karttunen, Sep 03 2016

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

Inverse: A276442.
Cf. A000079, A000225, A004001, A080677, A087686, A088359, A093879.
Related or similar permutations: A006068, A054429, A233275, A233277, A267111, A276343, A276345, A276443.
Cf. also arrays A265901, A265903.

(definec (A276441 n) (cond ((< n 2) n) ((zero? (A093879 (- n 1))) (+ 1 (* 2 (A276441 (+ -1 (A080677 n)))))) (else (* 2 (A276441 (+ -1 (A004001 n)))))))

a(1) = 1; for n > 1, if A093879(n-1) = 0 [when n is in A087686], a(n) = 1 + 2*a(A080677(n)-1), otherwise [when n is in A088359], a(n) = 2*a(A004001(n)-1).
As a composition of other permutations:
a(n) = A054429(A267111(n)).
a(n) = A233277(A276343(n)).
a(n) = A233275(A276345(n)).
a(n) = A006068(A276443(n)).
Other identities. For all n >= 1:
a(A000079(n-1)) = A000225(n).

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

Original entry on oeis.org

1, 3, 2, 6, 7, 5, 4, 11, 14, 13, 15, 10, 12, 9, 8, 20, 26, 25, 30, 23, 29, 28, 31, 19, 24, 22, 27, 18, 21, 17, 16, 37, 47, 46, 57, 44, 56, 55, 62, 41, 53, 52, 61, 50, 60, 59, 63, 36, 45, 43, 54, 40, 51, 49, 58, 35, 42, 39, 48, 34, 38, 33, 32, 70, 85, 84, 105, 82, 104, 103, 120, 79, 101, 100, 119, 98, 118, 117, 126, 75, 95, 94

Offset: 1

Antti Karttunen, Sep 03 2016

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

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

Inverse: A276441.
Cf. A004001, A087686, A088359, A267110.
Related or similar permutations: A003188, A054429, A233276, A233278, A267112, A276344, A276346, A276444.

(definec (A276442 n) (cond ((< n 2) n) ((even? n) (A088359 (A276442 (/ n 2)))) (else (A087686 (+ 1 (A276442 (/ (- n 1) 2)))))))

a(1) = 1; after which, a(2n) = A088359(a(n)), a(2n+1) = A087686(1+a(n)).
As a composition of other permutations:
a(n) = A267112(A054429(n)).
a(n) = A276344(A233278(n)).
a(n) = A276346(A233276(n)).
a(n) = A276444(A003188(n)).

A276445 Permutation of natural numbers: a(1) = 1, a(A087686(n)) = A001969(1+a(n-1)), a(A088359(n)) = A000069(1+a(n)), where A088359 & A087686 = numbers that occur only once & more than once in A004001, and A000069 & A001969 are odious & evil numbers.

Original entry on oeis.org

1, 3, 2, 6, 7, 4, 5, 12, 13, 14, 8, 15, 11, 9, 10, 24, 25, 26, 28, 16, 27, 31, 22, 29, 19, 17, 30, 21, 23, 18, 20, 48, 49, 50, 52, 56, 32, 51, 55, 62, 44, 53, 59, 38, 57, 35, 33, 54, 61, 42, 63, 47, 45, 58, 37, 39, 34, 60, 41, 43, 46, 36, 40, 96, 97, 98, 100, 104, 112, 64, 99, 103, 110, 124, 88, 101, 107, 118, 76, 105, 115, 70

Offset: 1

Antti Karttunen, Sep 03 2016

Inverse: A276446.
Cf. A000069, A001969, A004001, A080677, A087686, A088359, A093879.
Similar or related permutations: A003188, A267111, A276443 (compare the scatter plots).

(definec (A276445 n) (cond ((< n 2) n) ((zero? (A093879 (- n 1))) (A001969 (+ 1 (A276445 (+ -1 (A080677 n)))))) (else (A000069 (+ 1 (A276445 (+ -1 (A004001 n))))))))

a(1) = 1; for n > 1, if A093879(n-1) = 0 [when n is in A087686], a(n) = A001969(1+a(A080677(n)-1)), otherwise [when n is in A088359], a(n) = A000069(1+a(A004001(n)-1)).
As a composition of other permutations:
a(n) = A003188(A267111(n)).

A282891 Remainder when sum of first n terms of A004001 is divided by n.

Original entry on oeis.org

0, 0, 1, 2, 4, 1, 3, 5, 8, 2, 6, 10, 2, 6, 10, 14, 2, 7, 13, 0, 6, 13, 21, 5, 13, 21, 2, 10, 18, 26, 3, 10, 18, 27, 2, 12, 23, 34, 7, 19, 32, 3, 16, 30, 44, 13, 27, 41, 7, 22, 37, 1, 16, 31, 47, 7, 22, 37, 53, 9, 24, 39, 54, 5, 20, 36, 53, 3, 21, 40, 59, 7, 27, 48, 70, 16, 38, 61, 6, 29, 53, 78, 20, 45, 70, 9, 34, 60, 87, 24

Offset: 1

Altug Alkan, Feb 24 2017

Numbers n such that a(n) = 0 are 1, 2, 20, 4743, 10936, ...

			a(5) = 4 since Sum_{k=1..5} A004001(k) = 1 + 1 + 2 + 2 + 3 = 9 and remainder when 9 is divided by 5 is 4.

Altug Alkan, Table of n, a(n) for n = 1..10000
Altug Alkan, Alternative Scatterplot of A282891
Altug Alkan, Illustration Of Residue Classes Modulo 4

Cf. A004001, A282894, A283025.

A004001:= proc(n) option remember; procname(procname(n-1)) +procname(n-procname(n-1)) end proc:
A004001(1):= 1: A004001(2):= 1:
L:= ListTools[PartialSums](map(A004001, [$1..1000])):
seq(L[i] mod i, i=1..1000); # Robert Israel, Feb 24 2017

a[1] = 1; a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; MapIndexed[Last@ QuotientRemainder[#1, First@ #2] &, Accumulate@ Table[a@ n, {n, 90}]] (* Michael De Vlieger, Feb 24 2017, after Robert G. Wilson v at A004001 *)

first(n)=my(v=vector(n),s); v[1]=v[2]=1; for(k=3, n, v[k]=v[v[k-1]]+v[k-v[k-1]]); for(k=1,n, s+=v[k]; v[k]=s%k); v \\ Charles R Greathouse IV, Feb 26 2017

a(n) = (Sum_{k=1..n} A004001(k)) mod n.

cp's OEIS Frontend

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

A283470 a(n) = A004001(A004001(n-1)) XOR A004001(n-A004001(n-1)), a(1) = a(2) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

Extensions

A284019 The "Hofstadter chaotic heart" sequence: a(n) = A004001(n) - A005185(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Scheme

Extensions

A286560 Compound filter (summands of A004001 & summands of A005185): a(n) = P(A286541(n), A286559(n)), where P(n,k) is sequence A000027 used as a pairing function, with a(1) = a(2) = 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A095901 A004001 (mod 2).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A265754 Reduced frequency counts for A004001: a(n) = A265332(n+1) - A036987(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A276441 Permutation of natural numbers: a(1) = 1, a(A087686(1+n)) = 1 + 2*a(n), a(A088359(n)) = 2*a(n), where A088359 & A087686 = numbers that occur only once & more than once in A004001.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

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