A054519 -id:A054519 - cp's OEIS frontend

A326078 Number of subsets of {2..n} containing all of their integer quotients > 1.

1, 1, 2, 4, 8, 16, 24, 48, 72, 144, 216, 432, 552, 1104, 1656, 2592, 3936, 7872, 10056, 20112, 26688, 42320, 63480, 126960, 154800, 309600, 464400, 737568, 992160, 1984320, 2450880, 4901760, 6292800, 10197312, 15295968, 26241696, 32947488, 65894976, 98842464, 161587872, 205842528

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

These sets are closed under taking the quotient of two distinct divisible terms.

			The a(6) = 24 subsets:
  {}  {2}  {2,3}  {2,3,4}  {2,3,4,5}  {2,3,4,5,6}
      {3}  {2,4}  {2,3,5}  {2,3,4,6}
      {4}  {2,5}  {2,3,6}  {2,3,5,6}
      {5}  {3,4}  {2,4,5}
      {6}  {3,5}  {3,4,5}
           {4,5}  {4,5,6}
           {4,6}
           {5,6}

Cf. A007865, A051026, A054519, A067992, A103580, A325860, A325994, A326023, A326076, A326079, A326081.

Table[Length[Select[Subsets[Range[2,n]],SubsetQ[#,Divide@@@Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]]&]],{n,0,10}]

a(n)={
    my(lim=vector(n, k, sqrtint(k)));
    my(accept(b, k)=for(i=2, lim[k], if(k%i ==0 && bittest(b,i) != bittest(b,k/i), return(0))); 1);
    my(recurse(k, b)=
      my(m=1);
      for(j=max(2*k,n\2+1), min(2*k+1,n), if(accept(b,j), m*=2));
      k++;
      m*if(k > n\2, 1, (self()(k, b) + if(accept(b, k), self()(k, b + (1<Andrew Howroyd, Aug 30 2019

For n > 0, a(n) = A326023(n) - 1.

For n > 0, a(n) = A326079(n)/2.

Terms a(21) and beyond from Andrew Howroyd, Aug 30 2019

A326491 Number of maximal subsets of {1..n} containing no differences or quotients of pairs of distinct elements.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 7, 9, 10, 16, 22, 27, 39, 52, 70, 90, 120, 150, 198, 262, 357, 448, 602, 782, 1004, 1294, 1715, 2229, 2932, 3698, 4844, 6259, 8188, 10274, 13446, 16895, 21954, 27470, 35843, 45411, 58949, 73940, 95200, 120594, 154511, 192996, 247967, 312643

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

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

Subsets without differences or quotients are A326490.
Subsets with differences and quotients are A326494.
Maximal subsets without differences are A121269
Maximal subsets without quotients are A326492.
Cf. A007865, A051026, A054519, A326023, A326117, A326489, A326496, A327591.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],Intersection[#,Union[Divide@@@Reverse/@Subsets[#,{2}],Subtract@@@Reverse/@Subsets[#,{2}]]]=={}&]]],{n,0,10}]

a(n) = A326497(n) + 1 for n > 1. - Andrew Howroyd, Aug 30 2019

a(16)-a(40) from Andrew Howroyd, Aug 30 2019

a(41)-a(48) from Jinyuan Wang, Mar 04 2025

A364671 Number of subsets of {1..n} containing all of their own first differences.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 23, 34, 58, 96, 171, 302, 565, 1041, 1969, 3719, 7105, 13544, 25999, 49852, 95949, 184658, 356129, 687068, 1327540, 2566295, 4966449, 9617306, 18640098, 36150918, 70166056, 136272548, 264844111, 515036040, 1002211421, 1951345157, 3801569113

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

			The subset {1,2,4,5,10,14} has differences (1,2,1,5,4) so is counted under a(14).
The a(0) = 1 through a(5) = 14 subsets:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {2}    {2}      {2}        {2}
           {1,2}  {3}      {3}        {3}
                  {1,2}    {4}        {4}
                  {1,2,3}  {1,2}      {5}
                           {2,4}      {1,2}
                           {1,2,3}    {2,4}
                           {1,2,4}    {1,2,3}
                           {1,2,3,4}  {1,2,4}
                                      {1,2,3,4}
                                      {1,2,3,5}
                                      {1,2,4,5}
                                      {1,2,3,4,5}

Rémy Sigrist, C++ program

For differences of all strict pairs we have A054519, for partitions A007862.
For "disjoint" instead of "subset" we have A364463, partitions A363260.
For "non-disjoint" we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364672, partitions A364673, A364674, A364675.
First differences of terms are A364752, complement A364753.
Cf. A151897, A196723, A237667, A237668, A325325, A326083, A363225, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]], SubsetQ[#,Differences[#]]&]], {n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A326490 Number of subsets of {1..n} containing no differences or quotients of pairs of distinct elements.

Original entry on oeis.org

1, 2, 3, 5, 7, 12, 18, 31, 46, 72, 102, 172, 259, 428, 607, 989, 1329, 2142, 3117, 4953, 6956, 11032, 15321, 23979, 33380, 48699, 66849, 104853, 144712, 220758, 304133, 461580, 636556, 973843, 1316513, 1958828, 2585433, 3882843, 5237093, 7884277, 10555739, 15729293

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

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

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..90

Subsets without difference are A007865.
Maximal subsets without differences or quotients are A326491.
Subsets without quotients are A327591.
Subsets with differences and quotients are A326494.
Cf. A051026, A054519, A325860, A326023, A326079, A326489.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Union[Divide@@@Reverse/@Subsets[#,{2}],Subtract@@@Reverse/@Subsets[#,{2}]]]=={}&]],{n,0,10}]

a(n)={
   my(recurse(k, b)=
    if(k > n, 1,
      my(t = self()(k + 1, b));
      for(i=1, k\2, if(bittest(b,i) && (bittest(b,k-i) || (!(k%i) && bittest(b,k/i))), return(t)));
      t += self()(k + 1, b + (1<Andrew Howroyd, Aug 25 2019

For n > 0, a(n) = A326495(n) + 1.

a(19)-a(41) from Andrew Howroyd, Aug 25 2019

A364672 Number of subsets of {1..n} not containing all of their own first differences.

Original entry on oeis.org

0, 0, 0, 2, 6, 18, 41, 94, 198, 416, 853, 1746, 3531, 7151, 14415, 29049, 58431, 117528, 236145, 474436, 952627, 1912494, 3838175, 7701540, 15449676, 30988137, 62142415, 124600422, 249795358, 500719994, 1003575768, 2011211100, 4030123185, 8074898552, 16177657763, 32408393211, 64917907623

Offset: 0

Gus Wiseman, Aug 05 2023

nonn

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

For disjunction instead of containment we have A364463, partitions A363260.
For overlap we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364671, partitions A364673, A364674, A364675.
First differences of terms are A364753, complement A364752.
Cf. A007862, A054519, A151897, A237667, A325325, A326083, A363225, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]],!SubsetQ[#,Differences[#]]&]],{n,0,10}]

a(n) = 2^n - A364671(n). - Andrew Howroyd, Jan 27 2024

a(21) onwards (using A364671) added by Andrew Howroyd, Jan 27 2024

A056535 Mapping from the ordering by sum to the ordering by product of the ordered pairs. Inverse permutation to A056534.

Original entry on oeis.org

1, 2, 3, 4, 7, 5, 6, 12, 13, 8, 9, 18, 22, 19, 10, 11, 25, 32, 33, 26, 14, 15, 31, 43, 48, 44, 34, 16, 17, 39, 55, 63, 64, 56, 40, 20, 21, 47, 68, 80, 86, 81, 69, 49, 23, 24, 54, 79, 98, 107, 108, 99, 82, 57, 27, 28, 62, 93, 116, 129, 136, 130, 117, 94, 65, 29, 30, 72, 106

Offset: 1

Antti Karttunen, Jun 20 2000

The last term of the each row r of the triangle is the first term of that row + (tau(r)-1).

As an array, T(n,k) is the index of the k-th term of A027750 whose value is n. - Michel Marcus, Oct 15 2015

			As a triangle, sequence begins:
1;
2, 3;
4, 7, 5;
6, 12, 13, 8;
9, 18, 22, 19, 10;
...
As an array, sequence begins:
1,   2,  4,  6,  9,  11,  15, ...
3,   7, 12, 18, 25,  31,  39, ...
5,  13, 22, 32, 43,  55,  68, ...
8,  19, 33, 48, 63,  80,  98, ...
10, 26, 44, 64, 86, 107, 129, ...
...

Index entries for sequences that are permutations of the natural numbers

A056535[A000217[i]] = A056535[A000217[i-1]+1]+A000005[i]-1, for all i >= 1.

Left edge: A054519, Right edge: A006218.

Maple procedure nthmember given in A054426.

a[n_] := If[p = Position[A056534, n]; p != {}, p[[1, 1]], 0]; (* Jean-François Alcover, Aug 20 2013 *)

[seq(nthmember(j, A056534), j=1..105)];

A160664 a(n) = a(n-1) + A000203(n), a(0)=1.

Original entry on oeis.org

1, 2, 5, 9, 16, 22, 34, 42, 57, 70, 88, 100, 128, 142, 166, 190, 221, 239, 278, 298, 340, 372, 408, 432, 492, 523, 565, 605, 661, 691, 763, 795, 858, 906, 960, 1008, 1099, 1137, 1197, 1253, 1343, 1385, 1481, 1525, 1609, 1687, 1759, 1807, 1931, 1988, 2081, 2153

Offset: 0

Ctibor O. Zizka, May 22 2009

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Cf. A054519, A092406, A024916. - Greg Dresden, Feb 23 2020

ListTools:-PartialSums(map(numtheory:-sigma,[1,$1..100])); # Robert Israel, Dec 19 2016

lst = {1}; a = 1; Do[a = a + DivisorSigma[1, n]; AppendTo[lst, a], {n, 80}]; lst (* Carl Najafi, Aug 21 2011 *)
Transpose[NestList[{First[#]+1,Last[#]+DivisorSigma[1,First[#]+1]}&,{0,1},50]][[2]] (* Harvey P. Dale, May 05 2012 *)

a(n)=1+sum(k=1,n,sigma(k)) \\ Charles R Greathouse IV, Aug 22 2011

from math import isqrt
def A160664(n): return (-(s:=isqrt(n))**2*(s+1) + sum((q:=n//k)*((k<<1)+q+1) for k in range(1,s+1))>>1)+1 # Chai Wah Wu, Oct 22 2023

a(n) = 1 + A024916(n). - R. J. Mathar, May 25 2009

a(n) = 9 + A092406(n) for n>3. - Greg Dresden, Feb 23 2020

More terms from Carl Najafi, Aug 21 2011

A350102 Number of self-measuring subsets of the initial segment of the natural numbers strictly below n. Number of subsets S of [n] with S = distset(S).

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 12, 16, 18, 22, 25, 29, 31, 37, 39, 43, 47, 52, 54, 60, 62, 68, 72, 76, 78, 86, 89, 93, 97, 103, 105, 113, 115, 121, 125, 129, 133, 142, 144, 148, 152, 160, 162, 170, 172, 178, 184, 188, 190, 200, 203, 209, 213, 219, 221, 229, 233, 241, 245

Offset: 0

Peter Luschny, Dec 14 2021

nonn

We use the notation [n] = {0, 1, ..., n-1}. If S is a subset of [n] then we define the distset of S (set of distances of S) as {|x - y|: x, y in S}. We call a subset S of the natural numbers self-measuring if and only if S = distset(S).

			a(0) = 1 = card({}).
a(4) = 7 = card({}, {0}, {0, 1}, {0, 2}, {0, 3}, {0, 1, 2}, {0, 1, 2, 3}).
a(6) = 12 = card({}, {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 1, 2}, {0, 2, 4}, {0, 1, 2, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5}).

Winston de Greef, Table of n, a(n) for n = 0..10000
Peter Luschny, Illustrating self-measuring subsets of {0, 1, 2, 3}.

Cf. A350103, A349976, A006218, A054519, A000005.

A350102 := n -> ifelse(n = 0, 1, 2 + add(iquo(n-1, k), k = 1 .. n-1)):
seq(A350102(n), n = 0 .. 58);

a[0] = 1; a[1] = 2; a[n_] := a[n] = a[n - 1] + DivisorSigma[0, n - 1];
Table[a[n], {n, 0, 58}]

a(n) = a(n - 1) + tau(n - 1) for n >= 2, tau = A000005.
a(n) = 2 + Sum_{k=1..n-1} floor((n - 1)/k) for n >= 1.
a(n) = 2 + A006218(n - 1) for n >= 1.
a(n) = 1 + A054519(n - 1) for n >= 1.
Row sums of A350103.
a(n) >= n + floor(n/2) + floor(n/3).

A364752 Number of subsets of {1..n} containing n and all first differences.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 9, 11, 24, 38, 75, 131, 263, 476, 928, 1750, 3386, 6439, 12455, 23853, 46097, 88709, 171471, 330939, 640472, 1238755, 2400154, 4650857, 9022792, 17510820, 34015138, 66106492, 128571563, 250191929, 487175381, 949133736, 1850223956, 3608650389

Offset: 0

Gus Wiseman, Aug 06 2023

nonn

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

Rémy Sigrist, C++ program

Partial sums are A364671, complement A364672.
The complement is counted by A364753.
A054519 counts subsets containing differences, A326083 containing sums.
A364463 counts subsets disjoint from differences, complement A364466.
A364673 counts partitions containing differences, A364674, A364675.
Cf. A151897, A196723, A237668, A325325, A363225, A364345, A364464, A364537.

Table[If[n==0,1,Length[Select[Subsets[Range[n]], MemberQ[#,n]&&SubsetQ[#,Differences[#]]&]]],{n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A364753 Number of subsets of {1..n} containing n but not containing all first differences.

Original entry on oeis.org

0, 0, 0, 2, 4, 12, 23, 53, 104, 218, 437, 893, 1785, 3620, 7264, 14634, 29382, 59097, 118617, 238291, 478191, 959867, 1925681, 3863365, 7748136, 15538461, 31154278, 62458007, 125194936, 250924636, 502855774, 1007635332, 2018912085, 4044775367, 8102759211, 16230735448, 32509514412, 65110826347

Offset: 0

Gus Wiseman, Aug 06 2023

nonn

In other words, subsets containing both n and some element that is not the difference of two consecutive elements.

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

Partial sums are A364672, complement A364671.
The complement is counted by A364752.
A054519 counts subsets containing differences, A326083 containing sums.
A364463 counts subsets disjoint from differences, complement A364466.
A364673, A364674, A364675 count partitions containing differences.
Cf. A151897, A196723, A237668, A325325, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&!SubsetQ[#,Differences[#]]&]],{n,0,10}]

More terms from Giorgos Kalogeropoulos, Aug 07 2023

cp's OEIS Frontend

A326078 Number of subsets of {2..n} containing all of their integer quotients > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326491 Number of maximal subsets of {1..n} containing no differences or quotients of pairs of distinct elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A364671 Number of subsets of {1..n} containing all of their own first differences.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A326490 Number of subsets of {1..n} containing no differences or quotients of pairs of distinct elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A364672 Number of subsets of {1..n} not containing all of their own first differences.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A056535 Mapping from the ordering by sum to the ordering by product of the ordered pairs. Inverse permutation to A056534.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A160664 a(n) = a(n-1) + A000203(n), a(0)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions