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.

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, 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, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 2, 1, 3

Offset: 0

Author

Rémy Sigrist, May 15 2021

Keywords

• nonn
• base

Comments

This sequence is related to Karnaugh maps:

- for any number n with up to 2^k binary digits (possibly with leading zeros),

- we can interpret the binary expansion of n as a truth table for a k-ary Boolean function f,

- a(n) gives the optimal number of products in a disjunctive normal form for f.

Examples

			For n = 32576:
- the binary representation of 13170 is "111111101000000",
- it has 15 bits, so we can take k = 4 (15 <= 2^4),
- the corresponding 4-ary Boolean function f has the following truth table:
     CD\AB|  00  01  11  10
     -----+----------------
        00|   0   0   1   1
        01|   0   0   1   1
        11|   0   0   0   1
        10|   0   1   1   1
- we can express f as AC' + AB' + BCD' in optimal form,
- so a(32576) = 3.
		

Links

• Rémy Sigrist, PARI program for A344339
• Wikipedia, Disjunctive normal form
• Wikipedia, Karnaugh map

Crossrefs

Cf. A000120, A001196, A332520.

Programs

PARI

See Links section.

Formula

a(n) = 1 iff n > 0 and n belongs to A332520.

a(n) <= A000120(n).

a(A001196(n)) = a(n).