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

0, 1, 1, 3, 1, 4, 1, 7, 2, 6, 2, 8, 3, 5, 1, 15, 6, 9, 3, 13, 4, 8, 3, 18, 7, 9, 3, 13, 3, 6, 1, 31, 11, 16, 6, 22, 7, 12, 4, 29, 13, 12, 5, 17, 5, 9, 2, 41, 15, 23, 8, 23, 7, 13, 4, 31, 12, 14, 5, 16, 4, 7, 1, 63, 24, 36, 16, 31, 12, 20, 8, 45, 20, 24, 12, 22

Offset

1,4

Comments

This sequence is a binary variant of A096216: here we check for common one bits and there for common prime factors.

Links

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

Rémy Sigrist, Colored scatterplot of the first 2^15 terms (where the color is function of the Hamming weight of n)

Formula

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

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

a(2^n-1) = 1 for any n > 1.

Example

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

Prog

(PARI) a = vector(76); for(n=1, #a, a[n] = sum(i=1, n-1, bitand(a[i], n)==0); print1(a[n] ", "))

Crossrefs

Cf. A096216.

Sequence in context: A210622 A364065 A335113 * A301856 A301829 A006022

Adjacent sequences: A295273 A295274 A295275 * A295277 A295278 A295279

Keyword

nonn,base

Author

Rémy Sigrist, Nov 19 2017

Status

approved