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

Author

Rémy Sigrist, Apr 03 2022

Keywords

• nonn
• base

Comments

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

Examples

			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]
		

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

Crossrefs

Cf. A109812, A352884.

Formula

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