cp's OEIS Frontend

A375776 Bitwise conflict-free sequence: Each number n is placed into the first set k that contains no element x where n AND x > 0: a(n) = k.

%I A375776 #27 Aug 30 2024 12:21:54
%S A375776 1,1,2,1,3,4,5,1,4,3,6,2,7,8,9,1,8,7,10,6,11,12,13,5,14,15,16,17,18,
%T A375776 19,20,1,12,11,17,10,15,14,21,13,22,23,24,25,26,27,28,2,29,30,31,32,
%U A375776 33,34,35,36,37,38,39,40,41,42,43,1,19,18,25,16,23,22,36,10,30,29,32
%N A375776 Bitwise conflict-free sequence: Each number n is placed into the first set k that contains no element x where n AND x > 0: a(n) = k.
%H A375776 Alois P. Heinz, <a href="/A375776/b375776.txt">Table of n, a(n) for n = 1..16384</a>
%H A375776 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bitwise operation">Bitwise operation</a>
%F A375776 a(n) = 1 <=> n in { A000079 }. - _Andrew Howroyd_, Aug 27 2024
%F A375776 a(n) = 2 <=> n in { A164346 }. - _Alois P. Heinz_, Aug 27 2024
%F A375776 a(n) = A279125(n) + 1. - _Rémy Sigrist_, Aug 30 2024
%e A375776 For n = 1, a(1) = 1 because 1 gets put into the first set.
%e A375776 For n = 2, a(2) = 1 because 2 AND 1 == 0, so 2 can also be put into the first set.
%e A375776 For n = 3, a(3) = 2 because 3 AND 1 == 1, so 3 must be put into a new set.
%p A375776 s:= proc() {} end:
%p A375776 a:= proc(n) option remember; local k; for k
%p A375776       while ormap(x-> Bits[And](x, n)>0, s(k)) do od;
%p A375776       s(k):= {s(k)[], n}; k
%p A375776     end:
%p A375776 seq(a(n), n=1..75);  # _Alois P. Heinz_, Aug 27 2024
%o A375776 (Python)
%o A375776 def seq(n):
%o A375776     L = [0] + [0] * n
%o A375776     for i in range(1, n + 1):
%o A375776         k = next((k for k in range(1, len(L)) if i & L[k] == 0), None)
%o A375776         L[k] |= i
%o A375776         yield k
%o A375776 (PARI) seq(n)={my(a=vector(n), L=vector(n)); for(n=1, n, for(j=1, oo, if(!bitand(n,L[j]), L[j]=bitor(L[j],n); a[n]=j; break))); a} \\ _Andrew Howroyd_, Aug 27 2024
%Y A375776 Cf. A000079, A164346, A279125.
%K A375776 nonn,look,base
%O A375776 1,3
%A A375776 _Matt Donahoe_, Aug 27 2024