A267610 -id:A267610 - cp's OEIS frontend

A325095 Number of subsets of {1...n} with no binary carries.

1, 2, 4, 5, 10, 12, 14, 15, 30, 35, 40, 42, 47, 49, 51, 52, 104, 119, 134, 139, 154, 159, 164, 166, 181, 186, 191, 193, 198, 200, 202, 203, 406, 458, 510, 525, 577, 592, 607, 612, 664, 679, 694, 699, 714, 719, 724, 726, 778, 793, 808, 813, 828, 833, 838, 840

Offset: 0

Gus Wiseman, Mar 27 2019

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the binary representations of {2,5,8} are:
  2 =   10,
  5 =  101,
  8 = 1000,
and since there are no columns with more than one 1, {2,5,8} is counted under a(8).

			The a(1) = 1 through a(7) = 15 subsets:
  {}   {}     {}     {}       {}       {}       {}
  {1}  {1}    {1}    {1}      {1}      {1}      {1}
       {2}    {2}    {2}      {2}      {2}      {2}
       {1,2}  {3}    {3}      {3}      {3}      {3}
              {1,2}  {4}      {4}      {4}      {4}
                     {1,2}    {5}      {5}      {5}
                     {1,4}    {1,2}    {6}      {6}
                     {2,4}    {1,4}    {1,2}    {7}
                     {3,4}    {2,4}    {1,4}    {1,2}
                     {1,2,4}  {2,5}    {1,6}    {1,4}
                              {3,4}    {2,4}    {1,6}
                              {1,2,4}  {2,5}    {2,4}
                                       {3,4}    {2,5}
                                       {1,2,4}  {3,4}
                                                {1,2,4}

Alois P. Heinz, Table of n, a(n) for n = 0..16383

Cf. A000110, A019565, A050315, A080572, A247935, A267610, A267700.

Cf. A325094, A325096, A325097, A325100, A325103, A325104, A325105.

b:= proc(n, t) option remember; `if`(n=0, 1, b(n-1, t)+
     `if`(Bits[And](n, t)=0, b(n-1, Bits[Or](n, t)), 0))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..63);  # Alois P. Heinz, Mar 28 2019

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Range[n]],stableQ[#,Intersection[binpos[#1],binpos[#2]]!={}&]&]],{n,0,10}]

a(2^n - 1) = A000110(n + 1).

a(16)-a(55) from Alois P. Heinz, Mar 28 2019

A325109 Number of integer partitions of n whose distinct parts have no binary containments.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 8, 10, 12, 15, 18, 23, 28, 32, 41, 52, 57, 66, 76, 90, 99, 117, 131, 157, 172, 194, 216, 255, 276, 313, 358, 410, 447, 511, 546, 630, 677, 750, 818, 945, 990, 1108, 1200, 1338, 1429, 1606, 1713, 1928, 2062, 2263, 2412, 2725, 2847, 3142, 3389

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.

			The a(1) = 1 through a(8) = 12 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (41)     (33)      (43)       (44)
             (111)  (211)   (221)    (42)      (52)       (53)
                    (1111)  (2111)   (222)     (61)       (422)
                            (11111)  (411)     (421)      (611)
                                     (2211)    (2221)     (2222)
                                     (21111)   (4111)     (4211)
                                     (111111)  (22111)    (22211)
                                               (211111)   (41111)
                                               (1111111)  (221111)
                                                          (2111111)
                                                          (11111111)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..400, (terms up to a(200) from Alois P. Heinz)

Cf. A019565, A247935, A267610, A267700.

Cf. A325098, A325101, A325106, A325107, A325108, A325110.

c:= proc() option remember; local i, x, y;
      x, y:= map(n-> Bits[Split](n), [args])[];
      for i to nops(x) do
        if x[i]=1 and y[i]=0 then return false fi
      od; true
    end:
b:= proc(n, i, s) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1, s)+`if`(ormap(j-> c(i, j), s), 0, add(
      b(n-i*j, i-1, s union {i}), j=1..n/i))))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..55);  # Alois P. Heinz, Mar 29 2019

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[IntegerPartitions[n],stableQ[#,SubsetQ[binpos[#1],binpos[#2]]&]&]],{n,0,15}]
(* Second program: *)
c[args_List] := c[args] = Module[{i, x, y}, {x, y} = Reverse@IntegerDigits[#, 2]& /@ args; For[i = 1, i <= Length[x], i++, If[x[[i]] == 1 && y[[i]] == 0, Return[False]]]; True];
b[n_, i_, s_List] := b[n, i, s] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, s] + If[AnyTrue[s, c[{i, #}]&], 0, Sum[b[n - i*j, i-1, s ~Union~ {i}], {j, 1, n/i}]]]];
a[n_] := b[n, n, {}];
a /@ Range[0, 55] (* Jean-François Alcover, Jun 03 2021, after Alois P. Heinz *)

a(31)-a(54) from Alois P. Heinz, Mar 29 2019

A325101 Number of divisible binary-containment pairs of positive integers up to n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 11, 12, 14, 16, 18, 20, 22, 24, 28, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 53, 55, 57, 61, 63, 64, 66, 68, 70, 72, 74, 76, 79, 81, 83, 85, 87, 89, 93, 95, 97, 99, 101, 103, 107, 109, 111, 115, 118, 120, 122, 124, 126, 130, 132, 134

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A pair of positive integers is divisible if the first divides the second, and is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of those in the second.

			The a(1) = 1 through a(8) = 12 pairs:
  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)
         (2,2)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)
                (2,2)  (2,2)  (1,5)  (1,5)  (1,5)  (1,5)
                (3,3)  (3,3)  (2,2)  (2,2)  (1,7)  (1,7)
                       (4,4)  (3,3)  (2,6)  (2,2)  (2,2)
                              (4,4)  (3,3)  (2,6)  (2,6)
                              (5,5)  (4,4)  (3,3)  (3,3)
                                     (5,5)  (4,4)  (4,4)
                                     (6,6)  (5,5)  (5,5)
                                            (6,6)  (6,6)
                                            (7,7)  (7,7)
                                                   (8,8)

Cf. A000005, A006218, A080572, A267610, A267700.

Cf. A325094, A325102, A325106, A325107, A325108, A325109, A325110.

Table[Length[Select[Tuples[Range[n],2],Divisible[#[[2]],#[[1]]]&&SubsetQ[Position[Reverse[IntegerDigits[#[[2]],2]],1],Position[Reverse[IntegerDigits[#1[[1]],2]],1]]&]],{n,0,30}]

a(n) = A325106(n) + n.

A325107 Number of subsets of {1...n} with no binary containments.

Original entry on oeis.org

1, 2, 4, 5, 10, 13, 18, 19, 38, 52, 77, 83, 133, 147, 166, 167, 334, 482, 764, 848, 1465, 1680, 1987, 2007, 3699, 4413, 5488, 5572, 7264, 7412, 7579, 7580, 15160, 22573, 37251, 42824, 77387, 92863, 116453, 118461, 227502, 286775, 382573, 392246, 555661, 574113

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.

			The a(0) = 1 through a(6) = 18 subsets:
  {}  {}   {}     {}     {}       {}       {}
      {1}  {1}    {1}    {1}      {1}      {1}
           {2}    {2}    {2}      {2}      {2}
           {1,2}  {3}    {3}      {3}      {3}
                  {1,2}  {4}      {4}      {4}
                         {1,2}    {5}      {5}
                         {1,4}    {1,2}    {6}
                         {2,4}    {1,4}    {1,2}
                         {3,4}    {2,4}    {1,4}
                         {1,2,4}  {2,5}    {1,6}
                                  {3,4}    {2,4}
                                  {3,5}    {2,5}
                                  {1,2,4}  {3,4}
                                           {3,5}
                                           {3,6}
                                           {5,6}
                                           {1,2,4}
                                           {3,5,6}

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..129, (terms up to a(71) from Alois P. Heinz)

Cf. A006126, A014466, A019565, A267610.

Cf. A325095, A325096, A325101, A325105, A325106, A325108, A325109, A325110.

c:= proc() option remember; local i, x, y;
      x, y:= map(n-> Bits[Split](n), [args])[];
      for i to nops(x) do
        if x[i]=1 and y[i]=0 then return false fi
      od; true
    end:
b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+
     `if`(ormap(i-> c(n, i), s), 0, b(n-1, s union {n})))
    end:
a:= n-> b(n, {}):
seq(a(n), n=0..34);  # Alois P. Heinz, Mar 28 2019

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Range[n]],stableQ[#,SubsetQ[binpos[#1],binpos[#2]]&]&]],{n,0,13}]

a(2^n - 1) = A014466(n).

a(16)-a(45) from Alois P. Heinz, Mar 28 2019

A325108 Number of maximal subsets of {1...n} with no binary containments.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 6, 6, 11, 13, 16, 17, 22, 27, 28

Offset: 0

Gus Wiseman, Mar 28 2019

A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.

			The a(0) = 1 through a(7) = 6 maximal subsets:
  {}  {1}  {1,2}  {3}    {3,4}    {2,5}    {1,6}    {7}
                  {1,2}  {1,2,4}  {3,4}    {2,5}    {1,6}
                                  {3,5}    {3,4}    {2,5}
                                  {1,2,4}  {1,2,4}  {3,4}
                                           {3,5,6}  {1,2,4}
                                                    {3,5,6}

Cf. A006126, A014466, A019565, A267610.

Cf. A325095, A325096, A325101, A325106, A325107, A325109, A325110.

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],stableQ[#,SubsetQ[binpos[#1],binpos[#2]]&]&]]],{n,0,10}]

A325102 Number of ordered pairs of positive integers up to n with no binary carries.

Original entry on oeis.org

0, 0, 2, 2, 8, 10, 12, 12, 26, 32, 38, 40, 46, 48, 50, 50, 80, 94, 108, 114, 128, 134, 140, 142, 156, 162, 168, 170, 176, 178, 180, 180, 242, 272, 302, 316, 346, 360, 374, 380, 410, 424, 438, 444, 458, 464, 470, 472, 502, 516, 530, 536, 550, 556, 562, 564, 578

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion.

			The a(2) = 2 through a(6) = 12 pairs:
  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)  (1,2)
  (2,1)  (2,1)  (1,4)  (1,4)  (1,4)  (1,4)
                (2,1)  (2,1)  (1,6)  (1,6)
                (2,4)  (2,4)  (2,1)  (2,1)
                (3,4)  (2,5)  (2,4)  (2,4)
                (4,1)  (3,4)  (2,5)  (2,5)
                (4,2)  (4,1)  (3,4)  (3,4)
                (4,3)  (4,2)  (4,1)  (4,1)
                       (4,3)  (4,2)  (4,2)
                       (5,2)  (4,3)  (4,3)
                              (5,2)  (5,2)
                              (6,1)  (6,1)

Cf. A006218, A050315, A080572, A247935, A267610, A267700.

Cf. A325094, A325096, A325098, A325103, A325104, A325106, A325108, A325123.

Table[Length[Select[Tuples[Range[n],2],Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]=={}&]],{n,0,30}]

a(n) = 2 * A325103(n).

A325123 Number of divisible pairs of positive integers up to n with no binary carries.

Original entry on oeis.org

0, 0, 1, 1, 3, 3, 4, 4, 7, 7, 9, 9, 12, 12, 13, 13, 17, 17, 19, 19, 22, 22, 23, 23, 28, 28, 29, 29, 31, 31, 32, 32, 37, 37, 39, 39, 44, 44, 45, 45, 50, 50, 52, 52, 54, 54, 55, 55, 62, 62, 64, 64, 66, 66, 68, 68, 72, 72, 73, 73, 76, 76, 77, 77, 83, 83, 85, 85

Offset: 0

Gus Wiseman, Mar 29 2019

nonn

Two positive integers are divisible if the first divides the second, and they have a binary carry if the positions of 1's in their reversed binary expansion overlap.

a(2k+1) = a(2k), since an odd number and any divisor will overlap in the last digit. Additionally, a(2k+2) > a(2k+1) because the pair {1,2k+2} is always valid. Therefore, every term appears exactly twice. - Charlie Neder, Apr 02 2019

			The a(2) = 1 through a(11) = 9 pairs:
  {1,2}  {1,2}  {1,2}  {1,2}  {1,2}  {1,2}  {1,2}  {1,2}  {1,2}   {1,2}
                {1,4}  {1,4}  {1,4}  {1,4}  {1,4}  {1,4}  {1,4}   {1,4}
                {2,4}  {2,4}  {1,6}  {1,6}  {1,6}  {1,6}  {1,6}   {1,6}
                              {2,4}  {2,4}  {1,8}  {1,8}  {1,8}   {1,8}
                                            {2,4}  {2,4}  {2,4}   {2,4}
                                            {2,8}  {2,8}  {2,8}   {2,8}
                                            {4,8}  {4,8}  {4,8}   {4,8}
                                                          {1,10}  {1,10}
                                                          {5,10}  {5,10}

Cf. A006218, A019565, A050315, A070939, A080572, A247935, A267610.

Cf. A325095, A325096, A325101, A325103, A325104, A325105, A325106, A325124.

Table[Length[Select[Tuples[Range[n],2],Divisible@@Reverse[#]&&Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]=={}&]],{n,0,20}]

A325099 Number of binary carry-connected strict integer partitions of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 1, 4, 5, 8, 6, 11, 11, 15, 13, 18, 20, 30, 29, 43, 49, 68, 66, 84, 94, 125, 131, 165, 184, 237, 251, 291, 315, 383, 408, 486, 536, 663, 714, 832, 912, 1104, 1195, 1405, 1554, 1877, 2046, 2348, 2559, 2998, 3256, 3730, 4084, 4793, 5230, 5938

Offset: 0

Gus Wiseman, Mar 28 2019

nonn

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. An integer partition is binary carry-connected if the graph whose vertices are the parts and whose edges are binary carries is connected.

			The a(1) = 1 through a(11) = 6 strict partitions (A = 10, B = 11):
  (1)  (2)  (3)  (4)   (5)   (6)    (7)  (8)   (9)    (A)    (B)
                 (31)  (32)  (51)        (53)  (54)   (64)   (65)
                             (321)       (62)  (63)   (73)   (74)
                                         (71)  (72)   (91)   (632)
                                               (531)  (532)  (731)
                                                      (541)  (5321)
                                                      (631)
                                                      (721)

Cf. A050315, A080572, A247935, A267610, A267700.

Cf. A325095, A325096, A325098, A325104, A325106, A325110, A325119.

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Length[csm[binpos/@#]]<=1&]],{n,0,30}]

A325100 Heinz numbers of strict integer partitions with no binary carries.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 11, 13, 14, 17, 19, 21, 23, 26, 29, 31, 33, 35, 37, 38, 41, 42, 43, 47, 53, 57, 58, 59, 61, 67, 69, 71, 73, 74, 79, 83, 86, 89, 95, 97, 101, 103, 106, 107, 109, 111, 113, 114, 122, 123, 127, 131, 133, 137, 139, 142, 149, 151, 157, 158, 159

Offset: 1

Gus Wiseman, Mar 28 2019

nonn

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1) * ... * prime(y_k), so these are squarefree numbers whose prime indices have no carries. A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
  11: {5}
  13: {6}
  14: {1,4}
  17: {7}
  19: {8}
  21: {2,4}
  23: {9}
  26: {1,6}
  29: {10}
  31: {11}
  33: {2,5}
  35: {3,4}
  37: {12}
  38: {1,8}
  41: {13}
  42: {1,2,4}

Cf. A050315, A056239, A080572, A112798, A247935, A267610.

Cf. A325095, A325096, A325097, A325100, A325101, A325103, A325110, A325119.

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[100],SquareFreeQ[#]&&stableQ[PrimePi/@First/@FactorInteger[#],Intersection[binpos[#1],binpos[#2]]!={}&]&]

A325124 Number of divisible pairs of positive integers up to n with at least one binary carry.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 10, 12, 13, 16, 18, 20, 23, 25, 28, 32, 33, 35, 39, 41, 44, 48, 51, 53, 56, 59, 62, 66, 70, 72, 79, 81, 82, 86, 88, 92, 96, 98, 101, 105, 108, 110, 116, 118, 122, 128, 131, 133, 136, 139, 143, 147, 151, 153, 159, 163, 167, 171, 174, 176, 185

Offset: 0

Gus Wiseman, Mar 29 2019

nonn

Two positive integers are divisible if the first divides the second, and they have a binary carry if the positions of 1's in their reversed binary expansion overlap.

			The a(1) = 1 through a(8) = 13 pairs:
  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)
         (2,2)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)  (1,3)
                (2,2)  (2,2)  (1,5)  (1,5)  (1,5)  (1,5)
                (3,3)  (3,3)  (2,2)  (2,2)  (1,7)  (1,7)
                       (4,4)  (3,3)  (2,6)  (2,2)  (2,2)
                              (4,4)  (3,3)  (2,6)  (2,6)
                              (5,5)  (3,6)  (3,3)  (3,3)
                                     (4,4)  (3,6)  (3,6)
                                     (5,5)  (4,4)  (4,4)
                                     (6,6)  (5,5)  (5,5)
                                            (6,6)  (6,6)
                                            (7,7)  (7,7)
                                                   (8,8)

Cf. A006218, A019565, A050315, A070939, A080572, A247935, A267610, A307230.

Cf. A325095, A325096, A325101, A325103, A325104, A325105, A325106, A325123.

Table[Length[Select[Tuples[Range[n],2],Divisible@@Reverse[#]&&Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]!={}&]],{n,0,20}]

a(n) = A307230(n) + n.

cp's OEIS Frontend

A325095 Number of subsets of {1...n} with no binary carries.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A325109 Number of integer partitions of n whose distinct parts have no binary containments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A325101 Number of divisible binary-containment pairs of positive integers up to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A325107 Number of subsets of {1...n} with no binary containments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A325108 Number of maximal subsets of {1...n} with no binary containments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325102 Number of ordered pairs of positive integers up to n with no binary carries.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A325123 Number of divisible pairs of positive integers up to n with no binary carries.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325099 Number of binary carry-connected strict integer partitions of n.

Views

Author