A001196 -id:A001196 - 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).

A355663 Square array A(n, k), n, k >= 0, read by antidiagonals; for any number n with runs in binary expansion (r_w, ..., r_0), let p(n) be the polynomial of a single indeterminate x where the coefficient of x^e is r_e for e = 0..w and otherwise 0, and let q be the inverse of p; A(n, k) = q(p(n) + p(k)).

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 4, 4, 3, 4, 7, 12, 7, 4, 5, 8, 8, 8, 8, 5, 6, 11, 24, 15, 24, 11, 6, 7, 12, 19, 16, 16, 19, 12, 7, 8, 15, 28, 23, 48, 23, 28, 15, 8, 9, 16, 16, 24, 39, 39, 24, 16, 16, 9, 10, 19, 48, 31, 56, 51, 56, 31, 48, 19, 10, 11, 20, 35, 32, 32, 35, 35, 32, 32, 35, 20, 11

Offset: 0

Rémy Sigrist, Jul 13 2022

In other words, A(n, k) encodes the sum of the polynomials encoded by n and k.

			Array A(n, k) begins:
  n\k|   0   1   2   3    4    5    6   7    8    9   10   11   12
  ---+------------------------------------------------------------
    0|   0   1   2   3    4    5    6   7    8    9   10   11   12
    1|   1   3   4   7    8   11   12  15   16   19   20   23   24
    2|   2   4  12   8   24   19   28  16   48   35   44   39   56
    3|   3   7   8  15   16   23   24  31   32   39   40   47   48
    4|   4   8  24  16   48   39   56  32   96   71   88   79  112
    5|   5  11  19  23   39   51   35  47   79   99   76  103   71
    6|   6  12  28  24   56   35   60  48  112   67   92   71  120
    7|   7  15  16  31   32   47   48  63   64   79   80   95   96
    8|   8  16  48  32   96   79  112  64  192  143  176  159  224
    9|   9  19  35  39   71   99   67  79  143  195  156  199  135
   10|  10  20  44  40   88   76   92  80  176  156  204  152  184
   11|  11  23  39  47   79  103   71  95  159  199  152  207  143
   12|  12  24  56  48  112   71  120  96  224  135  184  143  240

Index entries for sequences related to binary expansion of n

Cf. A001196, A014601, A101211, A355664.

toruns(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); r }
fromruns(r) = { my (v=0); for (k=1, #r, v=(v+k%2)*2^r[k]-k%2); v }
A(n,k) = { fromruns(Vec(Pol(toruns(n)) + Pol(toruns(k)))) }

A(n, k) = A(k, n).
A(n, 0) = n.
A(n, 1) = A014601(n) for any n > 0.
A(n, n) = A001196(n).

A355664 Square array A(n, k), n, k >= 0, read by antidiagonals; for any number n with runs in binary expansion (r_w, ..., r_0), let p(n) be the polynomial of a single indeterminate x where the coefficient of x^e is r_e for e = 0..w and otherwise 0, and let q be the inverse of p; A(n, k) = q(p(n) * p(k)).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 3, 0, 0, 4, 12, 12, 4, 0, 0, 5, 35, 15, 35, 5, 0, 0, 6, 38, 48, 48, 38, 6, 0, 0, 7, 49, 51, 271, 51, 49, 7, 0, 0, 8, 56, 60, 284, 284, 60, 56, 8, 0, 0, 9, 135, 63, 387, 313, 387, 63, 135, 9, 0, 0, 10, 142, 192, 448, 398, 398, 448, 192, 142, 10, 0

Offset: 0

Rémy Sigrist, Jul 13 2022

In other words, A(n, k) encodes the product of the polynomials encoded by n and k.

			Array A(n, k) begins:
  n\k|  0   1    2    3     4     5     6     7      8      9     10     11
  ---+---------------------------------------------------------------------
    0|  0   0    0    0     0     0     0     0      0      0      0      0
    1|  0   1    2    3     4     5     6     7      8      9     10     11
    2|  0   2    9   12    35    38    49    56    135    142    153    156
    3|  0   3   12   15    48    51    60    63    192    195    204    207
    4|  0   4   35   48   271   284   387   448   2111   2172   2275   2288
    5|  0   5   38   51   284   313   398   455   2168   2289   2502   2531
    6|  0   6   49   60   387   398   481   504   3079   3102   3185   3196
    7|  0   7   56   63   448   455   504   511   3584   3591   3640   3647
    8|  0   8  135  192  2111  2168  3079  3584  33279  33784  34695  34752
    9|  0   9  142  195  2172  2289  3102  3591  33784  34785  36622  36739
   10|  0  10  153  204  2275  2502  3185  3640  34695  36622  39993  40476
   11|  0  11  156  207  2288  2531  3196  3647  34752  36739  40476  40719
   12|  0  12  195  240  3087  3132  3843  4032  49215  49404  50115  50160

Index entries for sequences related to binary expansion of n

Cf. A001196, A097254, A101211, A355663.

toruns(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); r }
fromruns(r) = { my (v=0); for (k=1, #r, v=(v+k%2)*2^r[k]-k%2); v }
A(n,k) = { fromruns(Vec(Pol(toruns(n)) * Pol(toruns(k)))) }

A(n, k) = A(k, n).
A(n, 0) = 0.
A(n, 1) = n.
A(n, 3) = A001196(n).
A(n, 7) = A097254(n+1).
A(n, n) = A355654(n).

A356353 Numbers k such that A356352(k) <> 1.

Original entry on oeis.org

0, 3, 7, 12, 15, 31, 48, 51, 56, 60, 63, 127, 192, 195, 204, 207, 240, 243, 252, 255, 448, 455, 504, 511, 768, 771, 780, 783, 816, 819, 828, 831, 960, 963, 972, 975, 992, 1008, 1011, 1020, 1023, 2047, 3072, 3075, 3084, 3087, 3120, 3123, 3132, 3135, 3264, 3267

Offset: 1

Rémy Sigrist, Oct 15 2022

Also, numbers whose binary expansions are juxtapositions of constant blocks of size g > 1.
A001196 and A097254 are subsequences.
There are A178472(k) terms with binary length k.

			The first terms, alongside their binary expansions and A356352(a(n)), are:
  n   a(n)  bin(a(n))   A356352(a(n))
  --  ----  ----------  -------------
   1     0           0              0
   2     3          11              2
   3     7         111              3
   4    12        1100              2
   5    15        1111              4
   6    31       11111              5
   7    48      110000              2
   8    51      110011              2
   9    56      111000              3
  10    60      111100              2
  11    63      111111              6
  12   127     1111111              7
  13   192    11000000              2
  14   195    11000011              2
  15   204    11001100              2
  16   207    11001111              2

Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n

Cf. A001196, A097254, A178472, A356352.

is(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); gcd(r)!=1 }

PARI
```
See Links section.
```

from math import gcd
from itertools import groupby
def ok(n):
    if n == 0: return True # by convention of A356352
    return gcd(*(len(list(g)) for k, g in groupby(bin(n)[2:]))) != 1
print([k for k in range(3268) if ok(k)]) # Michael S. Branicky, Oct 15 2022

A374446 Positions of zeros in the expansion of Product_{k>=0} (1 - x^(2^k))^3; A373308(a(n)) = 0 for n >= 1.

Original entry on oeis.org

2, 11, 14, 47, 50, 59, 62, 191, 194, 203, 206, 239, 242, 251, 254, 767, 770, 779, 782, 815, 818, 827, 830, 959, 962, 971, 974, 1007, 1010, 1019, 1022, 3071, 3074, 3083, 3086, 3119, 3122, 3131, 3134, 3263, 3266, 3275, 3278, 3311, 3314, 3323, 3326, 3839, 3842, 3851, 3854, 3887, 3890, 3899

Offset: 1

Paul D. Hanna, Jul 08 2024

nonn

Conjecture: a(n) = A001196(n) - 1 for n >= 1, where A001196 lists numbers with only even length runs in their binary expansion.

			Product_{k>=0} (1 - x^(2^k))^3 = 1 - 3*x + 0*x^2 + 8*x^3 - 9*x^4 + 3*x^5 + 8*x^6 - 24*x^7 + 15*x^8 + 19*x^9 - 24*x^10 + 0*x^11 + 17*x^12 - 27*x^13 + 0*x^14 + 64*x^15 + ... + A373308(n)*x^n + ...
in which the coefficients of {x^2, x^11, x^14, x^47, ..., x^a(n), ...} are zero.
Compare to numbers with only even length runs in their binary expansion: A001196 = [3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255, 768, ...]; it appears that a(n) = A001196(n) - 1 for n >= 1.

Paul D. Hanna, Table of n, a(n) for n = 1..511

Cf. A001196, A000695, A373308.

A374664 Nonnegative numbers whose binary expansion has no ones in common with some of its cyclic shifts.

Original entry on oeis.org

0, 2, 4, 8, 9, 10, 12, 16, 17, 18, 20, 24, 32, 33, 34, 35, 36, 40, 42, 48, 49, 56, 64, 65, 66, 67, 68, 72, 73, 74, 76, 80, 82, 84, 96, 97, 100, 112, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 140, 144, 145, 146, 148, 150, 152, 153, 160, 161, 162

Offset: 1

Rémy Sigrist, Jul 15 2024

Leading zeros in binary expansions are ignored.
All positive terms belong to A072602.
A number k belongs to the sequence iff A001196(k) belongs to the sequence.

			The first terms, with their binary expansion and an appropriate cyclic shift, are:
  n   a(n)  bin(a(n))  cyc
  --  ----  ---------  ------
   1     0          0       0
   2     2         10      01
   3     4        100     001
   4     8       1000    0001
   5     9       1001    0110
   6    10       1010    0101
   7    12       1100    0011
   8    16      10000   00001
   9    17      10001   00110
  10    18      10010   00101
  11    20      10100   01001
  12    24      11000   00011
  13    32     100000  000001
  14    33     100001  000110
  15    34     100010  000101
  16    35     100011  011100

Index entries for sequences related to binary expansion of n

Cf. A001196, A006257, A038572, A072602, A140900, A374712.

is(n) = { my (x = max(exponent(n), 0), s = n); for (i = 0, x, s = (s >> 1) + if (s%2, 2^x, 0); if (bitand(s, n)==0, return (1););); return (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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A356353 Numbers k such that A356352(k) <> 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Python

A374446 Positions of zeros in the expansion of Product_{k>=0} (1 - x^(2^k))^3; A373308(a(n)) = 0 for n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A374664 Nonnegative numbers whose binary expansion has no ones in common with some of its cyclic shifts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI