A215673 -id:A215673 - cp's OEIS frontend

A215674 a(1) = 1, a(n) = 2 if 1

1, 2, 2, 4, 4, 3, 5, 5, 3, 7, 7, 5, 9, 9, 5, 8, 8, 4, 9, 9, 6, 11, 11, 6, 9, 9, 4, 11, 11, 8, 15, 15, 8, 13, 13, 6, 15, 15, 10, 19, 19, 10, 15, 15, 6, 14, 14, 9, 17, 17, 9, 13, 13, 5, 14, 14, 10, 19, 19, 10, 16, 16, 7, 18, 18, 12, 23, 23, 12, 18, 18, 7, 16

Offset: 1

Sung-Hyuk Cha, Aug 20 2012

nonn

In the S.-H. Cha reference this is function fog_3(n).

Alois P. Heinz, Table of n, a(n) for n = 1..8192
S.-H. Cha, On Parity based Divide and Conquer Recursive Functions, International Conference on Computer Science and Applications, San Francisco, USA, 24-26 October 2012

Cf. A215673, A215675, A215676.

a:= proc(n) option remember; 1+ `if`(n=1, 0, `if`(n<=3, 1,
      `if`(irem(n, 3, 'r')=0, a(r), a(r)+a(r+1))))
    end:
seq (a(n), n=1..80);  # Alois P. Heinz, Aug 23 2012

a[n_] := a[n] = If[n < 3, n, {q, r} = QuotientRemainder[n, 3];
     Switch[r, 0, a[q] + 1, 1|2, a[q] + a[q+1] + 1]];
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Apr 24 2022 *)

A215675 a(1) = 1, a(n) = 2 if 1

Original entry on oeis.org

1, 2, 2, 4, 3, 5, 3, 7, 5, 8, 4, 9, 6, 9, 4, 11, 8, 13, 6, 14, 9, 13, 5, 14, 10, 16, 7, 16, 10, 14, 5, 16, 12, 20, 9, 22, 14, 20, 7, 21, 15, 24, 10, 23, 14, 19, 6, 20, 15, 25, 11, 27, 17, 24, 8, 24, 17, 27, 11, 25, 15, 20, 6, 22, 17, 29, 13, 33, 21, 30, 10

Offset: 1

Sung-Hyuk Cha, Aug 20 2012

nonn

In the S.-H. Cha reference this is function ~fog_2(n).

Alois P. Heinz, Table of n, a(n) for n = 1..8192
S.-H. Cha, On Parity based Divide and Conquer Recursive Functions, International Conference on Computer Science and Applications, San Francisco, USA, 24-26 October 2012.

Cf. A215673, A215674, A215676.

a:= proc(n) option remember; 1+ `if`(n=1, 0, `if`(n<=3, 1,
      `if`(irem(n-1, 2, 'r')=0, a(r), a(r)+a(r+1))))
    end:
seq (a(n), n=1..80);  # Alois P. Heinz, Aug 23 2012

a[n_] := a[n] = If[n < 3, n, {q, r} = QuotientRemainder[n, 2];
     Switch[r, 1, a[q] + 1, 0, a[q-1] + a[q] + 1]];
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Apr 24 2022 *)

G.f. A(x) satisfies: A(x) = x/(1 - x) + (1 + x + x^2) * A(x^2). - Ilya Gutkovskiy, May 23 2020

A215676 a(1) = 1, a(n) = 2 if 1

Original entry on oeis.org

1, 2, 2, 2, 4, 4, 3, 5, 5, 3, 5, 5, 3, 7, 7, 5, 9, 9, 5, 8, 8, 4, 9, 9, 6, 11, 11, 6, 9, 9, 4, 9, 9, 6, 11, 11, 6, 9, 9, 4, 11, 11, 8, 15, 15, 8, 13, 13, 6, 15, 15, 10, 19, 19, 10, 15, 15, 6, 14, 14, 9, 17, 17, 9, 13, 13, 5, 14, 14, 10, 19, 19, 10, 16, 16, 7

Offset: 1

Sung-Hyuk Cha, Aug 20 2012

nonn

In the S.-H. Cha reference this is function ~fog_3(n).

Alois P. Heinz, Table of n, a(n) for n = 1..8192
S.-H. Cha, On Parity based Divide and Conquer Recursive Functions, International Conference on Computer Science and Applications, San Francisco, USA, 24-26 October 2012

Cf. A215673, A215674, A215675.

a:= proc(n) option remember; 1+ `if`(n=1, 0, `if`(n<=4, 1,
      `if`(irem(n-1, 3, 'r')=0, a(r), a(r)+a(r+1))))
    end:
seq (a(n), n=1..80);  # Alois P. Heinz, Aug 23 2012

a[n_] := a[n] = Switch[n, 1, 0, 2|3|4, 1, _, {q, r} = QuotientRemainder[n-1, 3]; If[r == 0, a[q], a[q]+a[q+1]]]+1;
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Sep 01 2022 *)

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(2k) = {2k} U S(k) and S(2k+1) = {2k+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).

Original entry on oeis.org

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

Rémy Sigrist, Nov 12 2017

nonn

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

			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.

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

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

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)

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

cp's OEIS Frontend

A215674 a(1) = 1, a(n) = 2 if 1

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A215675 a(1) = 1, a(n) = 2 if 1

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A215676 a(1) = 1, a(n) = 2 if 1

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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(2k) = {2k} U S(k) and S(2k+1) = {2k+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).