A294991 Let S be the sequence of integer sets defined by the following rules: S(0) = {0}, S(1) = {1} and for any k > 0, S(2*k) = {2*k} U S(k) and S(2*k+1) = {2*k+1} U S(k) U S(k+1) (where X U Y denotes the union of the sets X and Y); a(n) = the number of elements of S(n).

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

Offset

0,3

Comments

For any n >= 0, a(n) corresponds the number of calls to the "fusc" function (defined by Dijkstra) required to compute A002487(n) with an implementation using memoization, and starting with an empty cache.

The sequence A215673 corresponds to the variant without memoization.

For any n > 0, a(n) <= A215673(n) (with equality iff n is a power of 2).

The scatterplot of the ordinal transform of the sequence shows a network of broken lines.

Also: for n >= 1, a(n)+2 is the number of states in the minimal complete deterministic finite automaton that accepts the base-2 representation of m and m+n in parallel, starting with the most significant digit. - Jeffrey Shallit, Jul 22 2023

Links

Table of n, a(n) for n=0..76.

Rémy Sigrist, Scatterplot of the first 100000 terms of the ordinal transform of the sequence

Rémy Sigrist, Illustration of the first terms

Index entries for sequences related to Stern's sequences

Formula

a(n) = 2*floor(log_2 n) - nu_2(n) + [n is a power of 2] + [1st two bits of n in base 2 are 11] = 2*A000523(n) - A007814(n) + A209229(n) + [n belongs to A004755], for n >= 1. - Jeffrey Shallit, Jul 20 2023

a(2*n) = a(n) + 1, n >= 1.

a(4*n+1) = a(2*n+1)+2, n >= 2.

a(4*n+3) = a(2*n+1)+2, n >= 0.

a(2^k) = k + 1 for any k >= 0.

Empirically: a(2*k-1) = 2*A070939(k) - 2*A209229(k) + [(k-1) is in A004760] for any k > 0 (where [P]=1 if P is true and [P]=0 otherwise).

Example

The first terms, alongside the corresponding set S(n), are:
n   a(n)    S(n)
--  ----    -----
0   1       { 0 }
1   1       { 1 }
2   2       { 1, 2 }
3   3       { 1, 2, 3 }
4   3       { 1, 2, 4 }
5   4       { 1, 2, 3, 5 }
6   4       { 1, 2, 3, 6 }
7   5       { 1, 2, 3, 4, 7 }
8   4       { 1, 2, 4, 8 }
9   6       { 1, 2, 3, 4, 5, 9 }
10  5       { 1, 2, 3, 5, 10 }
11  6       { 1, 2, 3, 5, 6, 11 }
12  5       { 1, 2, 3, 6, 12 }
13  7       { 1, 2, 3, 4, 6, 7, 13 }
14  6       { 1, 2, 3, 4, 7, 14 }
15  7       { 1, 2, 3, 4, 7, 8, 15 }
16  5       { 1, 2, 4, 8, 16 }
17  8       { 1, 2, 3, 4, 5, 8, 9, 17 }
18  7       { 1, 2, 3, 4, 5, 9, 18 }
19  8       { 1, 2, 3, 4, 5, 9, 10, 19 }
20  6       { 1, 2, 3, 5, 10, 20 }
See also illustration of the first terms in Links section.

Prog

(PARI) a(n) = my (S = Set(n), u = 1); while (u <= #S, my (v = S[#S-u+1]); if (v>1, if (v%2==0, S = setunion(S, Set(v/2)), S = setunion(S, Set([(v-1)/2, (v+1)/2])))); u++; ); return (#S)

Crossrefs

Cf. A002487, A004760, A070939, A209229, A215673.

Sequence in context: A292127 A227861 A336751 * A300118 A256544 A321211

Adjacent sequences: A294988 A294989 A294990 * A294992 A294993 A294994

Keyword

nonn

Author

Rémy Sigrist, Nov 12 2017

Status

approved