A295277 a(n) = number of distinct earlier terms that have no common one bit with n in binary representation.

0, 1, 1, 2, 2, 2, 1, 3, 2, 2, 1, 4, 2, 2, 1, 5, 3, 4, 2, 4, 2, 2, 1, 6, 4, 4, 2, 4, 2, 2, 1, 7, 4, 4, 2, 4, 2, 2, 1, 8, 4, 4, 2, 4, 2, 2, 1, 9, 5, 6, 3, 6, 3, 4, 2, 8, 4, 4, 2, 4, 2, 2, 1, 10, 6, 6, 3, 7, 4, 4, 2, 8, 4, 4, 2, 4, 2, 2, 1, 11, 6, 6, 3, 8, 4, 4

Offset

1,4

Comments

This sequence is a variant of A295276: here we count earlier terms without multiplicity, there with multiplicity.

The scatterplot of the first terms has fractal features (see scatterplot in Links section); see also A295283 for a variant of this sequence.

Links

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

Rémy Sigrist, Scatterplot of the first 2^20 terms

Rémy Sigrist, Colored scatterplot of the first 2^20 terms (where the color is function of min(A000120(a(n)), A000120((Max_{k=1..n-1} a(k))+1-a(n))))

Formula

a(n) = #{ a(k) such that 0 < k < n and a(k) AND n = 0 } (where AND stands for the bitwise AND operator).

Example

The first terms, alongside the distinct earlier terms with no common one bit with n, are:
  n   a(n)    Distinct earlier terms with no common one bit with n
  --  ----    ----------------------------------------------------
   1     0    {}
   2     1    {0}
   3     1    {0}
   4     2    {0, 1}
   5     2    {0, 2}
   6     2    {0, 1}
   7     1    {0}
   8     3    {0, 1, 2}
   9     2    {0, 2}
  10     2    {0, 1}
  11     1    {0}
  12     4    {0, 1, 2, 3}
  13     2    {0, 2}
  14     2    {0, 1}
  15     1    {0}
  16     5    {0, 1, 2, 3, 4}
  17     3    {0, 2, 4}
  18     4    {0, 1, 4, 5}
  19     2    {0, 4}
  20     4    {0, 1, 2, 3}

Prog

(PARI) mx=-1; for (n=1, 86, v=sum(i=0, mx, bitand(i, n)==0); print1(v ", "); mx=max(mx, v))

Crossrefs

Cf. A000120, A295276, A295283.

Sequence in context: A133138 A348193 A194326 * A194290 A329028 A257079

Adjacent sequences: A295274 A295275 A295276 * A295278 A295279 A295280

Keyword

nonn,base

Author

Rémy Sigrist, Nov 19 2017

Status

approved