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

Author

Rémy Sigrist, Nov 12 2017

Keywords

• nonn

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

Examples

			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.
		

Links

• 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

Crossrefs

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

Programs

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)

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