cp's OEIS Frontend

A344339 a(n) is the minimal number of terms of A332520 that need to be combined with the bitwise OR operator in order to give n.

%I A344339 #8 May 21 2021 04:18:04
%S A344339 0,1,1,1,1,1,2,2,1,2,1,2,1,2,2,1,1,1,2,2,2,2,3,3,2,2,2,2,2,2,3,2,1,2,
%T A344339 1,2,2,2,2,2,2,3,2,3,2,3,2,2,1,2,2,1,2,2,3,2,2,3,2,2,2,3,3,2,1,2,2,2,
%U A344339 1,2,2,2,2,3,2,3,2,3,2,2,1,2,2,2,2,1,3
%N A344339 a(n) is the minimal number of terms of A332520 that need to be combined with the bitwise OR operator in order to give n.
%C A344339 This sequence is related to Karnaugh maps:
%C A344339 - for any number n with up to 2^k binary digits (possibly with leading zeros),
%C A344339 - we can interpret the binary expansion of n as a truth table for a k-ary Boolean function f,
%C A344339 - a(n) gives the optimal number of products in a disjunctive normal form for f.
%H A344339 Rémy Sigrist, <a href="/A344339/a344339.gp.txt">PARI program for A344339</a>
%H A344339 Wikipedia, <a href="https://en.wikipedia.org/wiki/Disjunctive_normal_form">Disjunctive normal form</a>
%H A344339 Wikipedia, <a href="https://en.wikipedia.org/wiki/Karnaugh_map">Karnaugh map</a>
%F A344339 a(n) = 1 iff n > 0 and n belongs to A332520.
%F A344339 a(n) <= A000120(n).
%F A344339 a(A001196(n)) = a(n).
%e A344339 For n = 32576:
%e A344339 - the binary representation of 13170 is "111111101000000",
%e A344339 - it has 15 bits, so we can take k = 4 (15 <= 2^4),
%e A344339 - the corresponding 4-ary Boolean function f has the following truth table:
%e A344339      CD\AB|  00  01  11  10
%e A344339      -----+----------------
%e A344339         00|   0   0   1   1
%e A344339         01|   0   0   1   1
%e A344339         11|   0   0   0   1
%e A344339         10|   0   1   1   1
%e A344339 - we can express f as AC' + AB' + BCD' in optimal form,
%e A344339 - so a(32576) = 3.
%o A344339 (PARI) See Links section.
%Y A344339 Cf. A000120, A001196, A332520.
%K A344339 nonn,base
%O A344339 0,7
%A A344339 _Rémy Sigrist_, May 15 2021