A351887 a(n) is the number of k < n such that a(k) AND n = a(k) (where AND denotes the bitwise AND operator).

0, 1, 1, 3, 1, 4, 2, 7, 1, 5, 2, 8, 3, 8, 6, 15, 1, 6, 3, 11, 2, 8, 7, 18, 4, 9, 8, 19, 7, 14, 14, 31, 1, 7, 4, 13, 4, 12, 10, 24, 5, 12, 9, 21, 11, 22, 19, 40, 1, 8, 5, 17, 5, 18, 13, 35, 8, 19, 15, 34, 15, 32, 28, 63, 1, 9, 4, 15, 6, 18, 12, 31, 7, 18, 11

Offset

0,4

Comments

The definition is recursive: a(n) depends on prior terms (a(0), ..., a(n-1)); a(0) = 0 corresponds to an empty sum.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Example

The first terms, alongside the corresponding k's, are:
  n   a(n)  k's
  --  ----  ------------------------
   0     0  {}
   1     1  {0}
   2     1  {0}
   3     3  {0, 1, 2}
   4     1  {0}
   5     4  {0, 1, 2, 4}
   6     2  {0, 5}
   7     7  {0, 1, 2, 3, 4, 5, 6}
   8     1  {0}
   9     5  {0, 1, 2, 4, 8}
  10     2  {0, 6}
  11     8  {0, 1, 2, 3, 4, 6, 8, 10}
  12     3  {0, 5, 11}

Maple

a:= proc(n) option remember; add(
     `if`(Bits[And](n, a(j))=a(j), 1, 0), j=0..n-1)
    end:
seq(a(n), n=0..80);  # Alois P. Heinz, Feb 28 2022

Prog

(PARI) for (n=1, #a=vector(75), print1 (a[n]=sum(k=1, n-1, bitand(a[k], n-1)==a[k])", "))
(Python)
a = []
[a.append(sum(a[k] & n == a[k] for k in range(n))) for n in range(75)]
print(a) # Michael S. Branicky, Feb 24 2022

Crossrefs

Cf. A088167, A350802, A351886.

Sequence in context: A202154 A115208 A234930 * A273261 A274531 A365434

Adjacent sequences: A351884 A351885 A351886 * A351888 A351889 A351890

Keyword

nonn,base

Author

Rémy Sigrist, Feb 23 2022

Status

approved