A360296 a(1) = 1, and for any n > 1, a(n) is the sum of the terms of the sequence at indices k < n whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.

1, 1, 1, 2, 3, 3, 2, 4, 8, 11, 8, 8, 11, 8, 4, 8, 20, 34, 26, 34, 51, 40, 20, 20, 40, 51, 34, 26, 34, 20, 8, 16, 48, 96, 76, 118, 186, 152, 76, 96, 208, 281, 186, 152, 208, 124, 48, 48, 124, 208, 152, 186, 281, 208, 96, 76, 152, 186, 118, 76, 96, 48, 16, 32

Offset

1,4

Comments

This sequence is a variant of A165418.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..8192

Index entries for sequences related to binary expansion of n

Formula

a(n) = Sum_{k = 1..A301977(n-1)} a(A301983(n, k)) for any n > 1.

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

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

a(n) >= A165418(n).

Example

The first terms, alongside the corresponding k's, are:
  n   a(n)  k's
  --  ----  ------------------
   1     1  N/A
   2     1  {1}
   3     1  {1}
   4     2  {1, 2}
   5     3  {1, 2, 3}
   6     3  {1, 2, 3}
   7     2  {1, 3}
   8     4  {1, 2, 4}
   9     8  {1, 2, 3, 4, 5}
  10    11  {1, 2, 3, 4, 5, 6}
  11     8  {1, 2, 3, 5, 7}
  12     8  {1, 2, 3, 4, 6}
  13    11  {1, 2, 3, 5, 6, 7}
  14     8  {1, 2, 3, 6, 7}
  15     4  {1, 3, 7}
  16     8  {1, 2, 4, 8}

Prog

(PARI) { for (n=1, #a=vector(64), print1 (a[n]=if (n==1, 1, s = [1]; b = binary(n); for (k=2, #b, s = setunion(s, apply(v -> 2*v+b[k], s))); sum(k=1, #s-1, a[s[k]]); )", ")) }

Crossrefs

Cf. A165418, A301983.

Sequence in context: A309076 A343326 A073078 * A034799 A008985 A326699

Adjacent sequences: A360293 A360294 A360295 * A360297 A360298 A360299

Keyword

nonn,look,base

Author

Rémy Sigrist, Feb 02 2023

Status

approved