cp's OEIS Frontend

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)

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)

On Jul 15 1988 during a colloquium talk at Bell Labs, John Conway stated that he could prove that a(n)/n -> 1/2 as n approached infinity, but that the proof was extremely difficult. He therefore offered $100 to someone who could find an n_0 such that for all n >= n_0, we have |a(n)/n - 1/2| < 0.05, and he offered $10,000 for the least such n_0. I took notes (a scan of my notebook pages appears below), plus the talk - like all Bell Labs Colloquia at that time - was recorded on video. John said afterwards that he meant to say $1000, but in fact he said $10,000. I was in the front row. The prize was claimed by Colin Mallows, who agreed not to cash the check. - N. J. A. Sloane, Oct 21 2015

a(n) - a(n-1) = 0 or 1 (see the D. Newman reference). - Emeric Deutsch, Jun 06 2005

a(A188163(n)) = n and a(m) < n for m < A188163(n). - Reinhard Zumkeller, Jun 03 2011

From Daniel Forgues, Oct 04 2019: (Start)

Conjectures:

a(n) = n/2 iff n = 2^k, k >= 1.

a(n) = 2^(k-1): k times, for n = 2^k - (k-1) to 2^k, k >= 1. (End)

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)

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)

Square array A(n,k) [where n is row and k is column] is read by descending antidiagonals: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

For n >= 3, each row n lists the numbers that appear n times in A004001. See also A051135.

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

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)

Square array read by descending antidiagonals: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

The topmost row (row 1) of the array is A000079 (powers of 2), and in general each row 2^k contains the sequence (2^n - k), starting from the term (2^(k+1) - k). This follows from the properties (3) and (4) of A004001 given on page 227 of Kubo & Vakil paper (page 3 in PDF).

Moreover, each row 2^k - 1 (for k >= 2) contains the sequence 2^n - n - (k-2), starting from the term (2^(k+1) - (2k-1)). To see why this holds, consider the definitions of sequences A162598 and A265332, the latter which also illustrates how the frequency counts Q_n for A004001 are recursively constructed (in the Kubo & Vakil paper).

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