A295283 a(n) = 1 + number of distinct earlier terms that have common one bits with n in binary representation.

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

Offset

1,3

Comments

This sequence is a variant of A295277: here we count earlier terms with common one bits, there without common one bits.

The scatterplot of this sequence shares features with that of A295277 (see scatterplot in Links section).

Empirically, this sequence and A295277 have tight connections:

- let c be the sequence defined for any n > 0 by c(n) = a(n) + A295277(n),

- we have for any n > 0, c(n) <= c(n+1) <= c(n) + 1,

- let u be the sequence defined for any n > 0 by u(n) = least k such that a(k) = n,

- let v be the sequence defined for any n >= 0 by v(n) = least k such that A295277(k) = n,

- we have for any n > 0, u(n) + 1 = v(n).

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))+2-a(n))))

Rémy Sigrist, Scatterplot of (n, a(n) + A295277(n)) for n=1..2^20

Formula

a(2^n) = 0 for any n >= 0.

Example

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

Prog

(PARI) mx = 0; for (n=1, 85, v = 1 + sum(i=1, mx, bitand(i, n)!=0); print1 (v ", "); mx = max(mx, v))

Crossrefs

Cf. A000120, A295277.

Sequence in context: A316848 A139124 A024160 * A103284 A071287 A355731

Adjacent sequences: A295280 A295281 A295282 * A295284 A295285 A295286

Keyword

nonn,base

Author

Rémy Sigrist, Nov 19 2017

Status

approved