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,7

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.

Links

Table of n, a(n) for n=0..86.

Rémy Sigrist, PARI program for A344339

Wikipedia, Disjunctive normal form

Wikipedia, Karnaugh map

Formula

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

a(n) <= A000120(n).

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

Example

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.

Prog

(PARI) See Links section.

Crossrefs

Cf. A000120, A001196, A332520.

Sequence in context: A052005 A346707 A138702 * A348364 A279620 A278109

Adjacent sequences: A344336 A344337 A344338 * A344340 A344341 A344342

Keyword

nonn,base

Author

Rémy Sigrist, May 15 2021

Status

approved