A332520 -id:A332520 - 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.

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

Rémy Sigrist, May 15 2021

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.

			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.

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

Cf. A000120, A001196, A332520.

PARI
```
See Links section.
```

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

A331364 If the set of nonzero digits of n in some base of the form 2^2^k (with k >= 0) has exactly two elements, let b be the least such base and u and v the corresponding two nonzero digits; the base b representation of a(n) is obtained by replacing the u's by v's and vice versa in the base b representation of n; otherwise a(n) = n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 9, 13, 8, 6, 10, 14, 12, 7, 11, 15, 16, 17, 33, 49, 65, 81, 41, 61, 36, 38, 37, 177, 52, 55, 225, 53, 32, 18, 34, 50, 24, 26, 25, 114, 130, 22, 162, 62, 56, 210, 59, 58, 48, 19, 35, 51, 28, 31, 99, 29, 44, 147, 47, 46, 195, 23, 43, 243, 64

Offset: 0

Rémy Sigrist, Jun 24 2020

This sequence is a self-inverse permutation of the nonnegative integers. See A332520 for the corresponding fixed points.

For any m > 1, we can devise a similar sequence by considering bases of the form m^2^k (with k >= 0).

			For n = 73:
- the base 2^2^0 representation of 73 is "1001001" which has only one kind of nonzero digits,
- the base 2^2^1 representation of 73 is "1021" which has exactly two kinds of nonzero digits, "1" and "2",
- so the base 2^2^1 representation of a(73) is "2012",
- and a(73) = 134.

Rémy Sigrist, Table of n, a(n) for n = 0..65536
Rémy Sigrist, Scatterplot of the first 2^2^4 terms
Rémy Sigrist, Colored scatterplot of the first 2^2^4 terms (where the color denotes the base b if any)
Index entries for sequences that are permutations of the natural numbers

Cf. A001146, A332520 (fixed points).

a(n) = { for (x=0, oo, my (b=2^2^x, d=if (n, digits(n, b), [0])); if (#d==1, return (n), my (uv=select(sign, Set(d))); if (#uv==2, return (
fromdigits(apply (t -> if (t==0, 0, t==uv[1], uv[2], uv[1]), d), b))))) }

a(n) < 2^2^k iff n < 2^2^k for any n, k >= 0.
a(2^k) = 2^k for any k >= 0.
a(2^2^k-1) = 2^2^k-1 for any k >= 0.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula