A352791 a(n) is the number of numbers k < n such that A109812(k) AND A109812(n) = 0 (where AND denotes the bitwise AND operator).

0, 1, 2, 1, 4, 2, 3, 7, 3, 4, 5, 5, 6, 3, 14, 3, 8, 10, 8, 4, 11, 5, 12, 5, 11, 5, 14, 3, 28, 7, 8, 18, 8, 8, 18, 8, 9, 21, 5, 26, 5, 21, 9, 11, 11, 11, 25, 6, 15, 49, 7, 16, 29, 8, 16, 31, 8, 17, 33, 14, 14, 15, 16, 16, 16, 15, 15, 18, 8, 40, 9, 18, 21, 11

Offset

1,3

Comments

The magnitude of a(n) is related to A352884(n), the Hamming weight of A109812(n) (see illustration in Links section).

Links

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

Rémy Sigrist, Colored logarithmic scatterplot of the first 100000 terms (where the color is function of the Hamming weight of A109812(n))

Rémy Sigrist, C++ program

Formula

a(n) <= n-1 with equality iff A109812(n) is a power of 2.

Example

The first terms, alongside the binary expansion of A109812(n) and the corresponding k's, are:
  n   a(n)  bin(b(n))  k's
  --  ----  ---------  -----------------------------------------------
   1     0          1  []
   2     1         10  [1]
   3     2        100  [1, 2]
   4     1         11  [3]
   5     4       1000  [1, 2, 3, 4]
   6     2        101  [2, 5]
   7     3       1010  [1, 3, 6]
   8     7      10000  [1, 2, 3, 4, 5, 6, 7]
   9     3        110  [1, 5, 8]
  10     4       1001  [2, 3, 8, 9]
  11     5      10010  [1, 3, 5, 6, 10]
  12     5       1100  [1, 2, 4, 8, 11]
  13     6      10001  [2, 3, 5, 7, 9, 12]
  14     3       1110  [1, 8, 13]
  15    14     100000  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
  16     3        111  [5, 8, 15]

Prog

(C++) See Links section.

Crossrefs

Cf. A109812, A352884.

Sequence in context: A121464 A090278 A256143 * A274455 A153279 A278425

Adjacent sequences: A352788 A352789 A352790 * A352792 A352793 A352794

Keyword

nonn,base

Author

Rémy Sigrist, Apr 03 2022

Status

approved