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

Author

Rémy Sigrist, Feb 02 2023

Keywords

• nonn
• look
• base

Comments

This sequence is a variant of A165418.

Examples

			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}
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A165418, A301983.

Programs

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]]);)", ")) }

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