A143823 -id:A143823 - cp's OEIS frontend

A325858 Number of Golomb partitions of n.

1, 1, 2, 3, 5, 7, 10, 14, 20, 25, 36, 47, 59, 78, 99, 122, 155, 195, 232, 295, 355, 432, 522, 641, 749, 919, 1076, 1283, 1506, 1802, 2067, 2470, 2835, 3322, 3815, 4496, 5070, 5959, 6736, 7807, 8849, 10266, 11499, 13326, 14928, 17140, 19193, 22037, 24519, 28106

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

We define a Golomb partition of n to be an integer partition of n such that every pair of distinct parts has a different difference.
Also the number of integer partitions of n such that every orderless pair of (not necessarily distinct) parts has a different sum.
The strict case is A325876.

			The a(1) = 1 through a(7) = 14 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (31)    (41)     (42)      (52)
                    (211)   (221)    (51)      (61)
                    (1111)  (311)    (222)     (322)
                            (2111)   (411)     (331)
                            (11111)  (2211)    (421)
                                     (3111)    (511)
                                     (21111)   (2221)
                                     (111111)  (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)
The A000041(9) - a(9) = 5 non-Golomb partitions of 9 are: (531), (432), (3321), (32211), (321111).

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

The subset case is A143823.
The maximal case is A325879.
The integer partition case is A325858.
The strict integer partition case is A325876.
Heinz numbers of the counterexamples are given by A325992.
Cf. A002033, A108917, A325325, A325853, A325856, A325868.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@Subtract@@@Subsets[Union[#],{2}]&]],{n,0,30}]

A325860 Number of subsets of {1..n} such that every pair of distinct elements has a different quotient.

Original entry on oeis.org

1, 2, 4, 8, 14, 28, 52, 104, 188, 308, 548, 1096, 1784, 3568, 6168, 10404, 16200, 32400, 49968, 99936, 155584, 256944, 433736, 867472, 1297504, 2026288, 3387216, 5692056, 8682912, 17365824, 25243200, 50486400, 78433056, 125191968, 206649216, 328195632

Offset: 0

Gus Wiseman, May 31 2019

nonn

Also subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different product.

			The a(0) = 1 through a(4) = 14 subsets:
  {}  {}   {}    {}     {}
      {1}  {1}   {1}    {1}
           {2}   {2}    {2}
           {12}  {3}    {3}
                 {12}   {4}
                 {13}   {12}
                 {23}   {13}
                 {123}  {14}
                        {23}
                        {24}
                        {34}
                        {123}
                        {134}
                        {234}

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

The subset case is A325860.
The maximal case is A325861.
The integer partition case is A325853.
The strict integer partition case is A325854.
Heinz numbers of the counterexamples are given by A325994.
Cf. A002033, A108917, A143823, A196723, A196723, A196724, A325855, A325858, A325859, A325868, A325869.

Table[Length[Select[Subsets[Range[n]],UnsameQ@@Divide@@@Subsets[#,{2}]&]],{n,0,20}]

a(21)-a(25) from Alois P. Heinz, Jun 07 2019

a(26)-a(35) from Fausto A. C. Cariboni, Oct 04 2020

A325864 Number of subsets of {1..n} of which every subset has a different sum.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 56, 91, 135, 211, 307, 446, 625, 882, 1194, 1677, 2238, 3031, 4001, 5460, 6995, 9302, 11921, 15424, 19554, 25032, 31005, 39170, 48251, 59917, 73093, 90831, 109271, 134049, 160922, 196109, 234179, 284157, 335933, 408390, 482597, 575109

Offset: 0

Gus Wiseman, Jun 01 2019

nonn

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

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..150 (terms 0..60 from Giovanni Resta)

Cf. A002033, A108917, A143823, A196723, A275972.

Cf. A325860, A325865, A325866, A325867, A325877, A325878, A325879, A325880.

Table[Length[Select[Subsets[Range[n]],UnsameQ@@Plus@@@Subsets[#]&]],{n,0,10}]

a(18)-a(42) from Alois P. Heinz, Jun 03 2019

A347460 Number of distinct possible alternating products of factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 3, 4, 1, 5, 1, 5, 2, 2, 2, 7, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 8, 2, 4, 2, 4, 1, 5, 2, 6, 2, 2, 1, 10, 1, 2, 4, 6, 2, 5, 1, 4, 2, 5, 1, 10, 1, 2, 4, 4, 2, 5, 1, 8, 4, 2, 1, 10, 2, 2

Offset: 1

Gus Wiseman, Oct 06 2021

nonn

We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).

A factorization of n is a weakly increasing sequence of positive integers > 1 with product n.

			The a(n) alternating products for n = 1, 4, 8, 12, 24, 30, 36, 48, 60, 120:
  1  4  8    12   24   30    36   48    60    120
     1  2    3    6    10/3  9    12    15    30
        1/2  3/4  8/3  5/6   4    16/3  20/3  40/3
             1/3  2/3  3/10  1    3     15/4  15/2
                  3/8  2/15  4/9  3/4   12/5  24/5
                  1/6        1/4  1/3   3/5   10/3
                             1/9  3/16  5/12  5/6
                                  1/12  4/15  8/15
                                        3/20  3/10
                                        1/15  5/24
                                              2/15
                                              3/40
                                              1/30

Positions of 1's are 1 and A000040.
Positions of 2's appear to be A001358.
Positions of 3's appear to be A030078.
Dominates A038548, the version for reverse-alternating product.
Counting only integers gives A046951.
The even-length case is A072670.
The version for partitions (not factorizations) is A347461, reverse A347462.
The odd-length case is A347708.
The length-3 case is A347709.
A001055 counts factorizations (strict A045778, ordered A074206).
A056239 adds up prime indices, row sums of A112798.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A108917 counts knapsack partitions, ranked by A299702.
A276024 counts distinct positive subset-sums of partitions, strict A284640.
A292886 counts knapsack factorizations, by sum A293627.
A299701 counts distinct subset-sums of prime indices, positive A304793.
A301957 counts distinct subset-products of prime indices.
A304792 counts distinct subset-sums of partitions.
Cf. A002033, A119620, A143823, A325770, A339846, A339890, A347437, A347438, A347439, A347440, A347442, A347456.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Union[altprod/@facs[n]]],{n,100}]

A143824 Size of the largest subset {x(1),x(2),...,x(k)} of {1,2,...,n} with the property that all differences |x(i)-x(j)| are distinct.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12

Offset: 0

John W. Layman, Sep 02 2008

When the set {x(1),x(2),...,x(k)} satisfies the property that all differences |x(i)-x(j)| are distinct (or alternately, all the sums are distinct), then it is called a Sidon set. So a(n) is the maximum cardinality of a dense Sidon subset of {1,2,...,n}. - Sayan Dutta, Aug 29 2024
See A143823 for the number of subsets of {1, 2, ..., n} with the required property.
See A003022 (and A227590) for the values of n such that a(n+1) > a(n). - Boris Bukh, Jul 28 2013
Can be formulated as an integer linear program: maximize sum {i = 1 to n} z[i] subject to z[i] + z[j] - 1 <= y[i,j] for all i < j, sum {i = 1 to n - d} y[i,i+d] <= 1 for d = 1 to n - 1, z[i] in {0,1} for all i, y[i,j] in {0,1} for all i < j. - Rob Pratt, Feb 09 2010
If the zeroth term is removed, the run-lengths are A270813 with 1 prepended. - Gus Wiseman, Jun 07 2019

			For n = 4, {1, 2, 4} is a subset of {1, 2, 3, 4} with distinct differences 2 - 1 = 1, 4 - 1 = 3, 4 - 2 = 2 between pairs of elements and no larger set has the required property; so a(4) = 3.
From _Gus Wiseman_, Jun 07 2019: (Start)
Examples of subsets realizing each largest size are:
   0: {}
   1: {1}
   2: {1,2}
   3: {2,3}
   4: {1,3,4}
   5: {2,4,5}
   6: {3,5,6}
   7: {1,3,6,7}
   8: {2,4,7,8}
   9: {3,5,8,9}
  10: {4,6,9,10}
  11: {5,7,10,11}
  12: {1,4,5,10,12}
  13: {2,5,6,11,13}
  14: {3,6,7,12,14}
  15: {4,7,8,13,15}
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..500
Thomas Bloom, Problem 30, Problem 43, Problem 155, and Problem 861, Erdős Problems.
Kevin O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin., DS11, Dynamic Surveys (2004), 39 pp.
Terence Tao, Erdős problem database, see nos. 30, 43, 155, 861.
Wikipedia, Sidon sequence.
Wikipedia, Golomb ruler
Balogh, J., Füredi, Z., & Roy, S. (2023), An Upper Bound on the Size of Sidon Sets, The American Mathematical Monthly, 130(5), 437-445.

Cf. A143823, A003002, A003022, A227590.

Cf. A108917, A169942, A270813, A325676, A325677, A325678, A325683, A325687.

Table[Length[Last[Select[Subsets[Range[n]],UnsameQ@@Subtract@@@Subsets[#,{2}]&]]],{n,0,15}] (* Gus Wiseman, Jun 07 2019 *)

For n > 1, a(n) = A325678(n - 1) + 1. - Gus Wiseman, Jun 07 2019
From Sayan Dutta, Aug 29 2024: (Start)
a(n) < n^(1/2) + 0.998*n^(1/4) for sufficiently large n (see Balogh et. al. link).
It is conjectured by Erdos (for $500) that a(n) < n^(1/2) + o(n^e) for all e>0. (End)

More terms from Rob Pratt, Feb 09 2010
a(41)-a(60) from Alois P. Heinz, Sep 14 2011
More terms and b-file from N. J. A. Sloane, Apr 08 2016 using data from A003022.

A325768 Number of integer partitions of n for which every restriction to a subinterval has a different sum.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 12, 15, 15, 23, 22, 29, 32, 40, 42, 55, 56, 71, 75, 92, 100, 124, 128, 152, 167, 198, 212, 255, 269, 315, 343, 392, 428, 501, 529, 615, 665, 757, 812, 937, 1002, 1142, 1238, 1385, 1490, 1701, 1808, 2038, 2200, 2476

Offset: 0

Gus Wiseman, May 21 2019

nonn

Also the number of Golomb rulers of length n whose consecutive marks are separated by weakly decreasing distances.

The Heinz numbers of these partitions are given by A325779.

			The a(1) = 1 through a(9) = 8 partitions:
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)    (9)
            (21)  (31)  (32)  (42)  (43)   (53)   (54)
                        (41)  (51)  (52)   (62)   (63)
                                    (61)   (71)   (72)
                                    (421)  (521)  (81)
                                                  (432)
                                                  (531)
                                                  (621)

Cf. A000041, A002033, A103300, A143823, A169942, A325676, A325687, A325769, A325779.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,0,30}]

A325877 Number of strict integer partitions of n such that every orderless pair of distinct parts has a different sum.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9, 12, 14, 18, 19, 26, 28, 36, 37, 50, 52, 67, 68, 89, 94, 115, 121, 151, 160, 195, 200, 247, 265, 312, 329, 386, 418, 487, 519, 600, 640, 742, 792, 901, 978, 1088, 1185, 1331, 1453, 1605, 1729, 1925, 2101, 2311, 2524, 2741, 3000

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

The non-strict case is A325857.

			The a(1) = 1 through a(10) = 9 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)    (9)    (A)
            (21)  (31)  (32)  (42)   (43)   (53)   (54)   (64)
                        (41)  (51)   (52)   (62)   (63)   (73)
                              (321)  (61)   (71)   (72)   (82)
                                     (421)  (431)  (81)   (91)
                                            (521)  (432)  (532)
                                                   (531)  (541)
                                                   (621)  (631)
                                                          (721)

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

The subset case is A196723.
The maximal case is A325878.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A108917, A143823, A275972.
Cf. A325854, A325855, A325858, A325862, A325864, A325876, A325879.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&UnsameQ@@Plus@@@Subsets[Union[#],{2}]&]],{n,0,30}]

A325687 Triangle read by rows where T(n,k) is the number of length-k compositions of n such that every distinct consecutive subsequence has a different sum.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 0, 1, 1, 4, 4, 0, 1, 1, 5, 5, 0, 0, 1, 1, 6, 12, 4, 0, 0, 1, 1, 7, 12, 5, 0, 0, 0, 1, 1, 8, 25, 8, 4, 0, 0, 0, 1, 1, 9, 24, 12, 3, 0, 0, 0, 0, 1, 1, 10, 40, 32, 8, 4, 0, 0, 0, 0, 1, 1, 11, 41, 41, 6, 3, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, May 13 2019

A composition of n is a finite sequence of positive integers summing to n.

			The distinct consecutive subsequences of (1,1,3,3) are (1), (1,1), (3), (1,3), (1,1,3), (3,3), (1,3,3), (1,1,3,3), all of which have different sums, so (1,1,3,3) is counted under a(8).
Triangle begins:
  1
  1  1
  1  2  1
  1  3  0  1
  1  4  4  0  1
  1  5  5  0  0  1
  1  6 12  4  0  0  1
  1  7 12  5  0  0  0  1
  1  8 25  8  4  0  0  0  1
  1  9 24 12  3  0  0  0  0  1
  1 10 40 32  8  4  0  0  0  0  1
  1 11 41 41  6  3  0  0  0  0  0  1
  1 12 60 76 14  4  4  0  0  0  0  0  1
  1 13 60 88 16  6  3  0  0  0  0  0  0  1
Row n = 8 counts the following compositions:
  (8)  (17)  (116)  (1115)  (11111111)
       (26)  (125)  (1133)
       (35)  (143)  (2222)
       (44)  (152)  (3311)
       (53)  (215)  (5111)
       (62)  (233)
       (71)  (251)
             (332)
             (341)
             (512)
             (521)
             (611)

Row sums are A325676.
Column k = 2 is A000027.
Column k = 3 is A325688.
Cf. A000079, A007318, A048004, A108917, A143823, A169942, A266223, A325592, A325680, A325685.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],UnsameQ@@Total/@Union[ReplaceList[#,{_,s__,_}:>{s}]]&]],{n,15},{k,n}]

A124770 Number of distinct nonempty subsequences for compositions in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 3, 3, 1, 3, 2, 5, 3, 5, 5, 4, 1, 3, 3, 5, 3, 5, 5, 7, 3, 5, 5, 8, 5, 8, 7, 5, 1, 3, 3, 5, 2, 6, 6, 7, 3, 6, 3, 8, 6, 7, 8, 9, 3, 5, 6, 8, 6, 8, 7, 11, 5, 8, 8, 11, 7, 11, 9, 6, 1, 3, 3, 5, 3, 6, 6, 7, 3, 5, 5, 9, 5, 9, 9, 9, 3, 6, 5, 9, 5, 7, 8, 11, 6, 9, 8, 11, 9, 11, 11, 11, 3, 5, 6, 8, 5, 9

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. - Gus Wiseman, Apr 03 2020

			Composition number 11 is 2,1,1; the nonempty subsequences are 1; 2; 1,1; 2,1; 2,1,1; so a(11) = 5.
The table starts:
  0
  1
  1 2
  1 3 3 3
  1 3 2 5 3 5 5 4
  1 3 3 5 3 5 5 7 3 5 5 8 5 8 7 5
From _Gus Wiseman_, Apr 03 2020: (Start)
If the k-th composition in standard order is c, then we say that the STC-number of c is k. The STC-numbers of the distinct subsequences of the composition with STC-number k are given in column k below:
  1  2  1  4  1  1  1  8  1  2   1   1   1   1   1   16  1   2   1   2
        3     2  2  3     4  10  2   4   2   2   3       8   4   4   4
              5  6  7     9      3   12  6   3   7       17  18  3   20
                                 5       5   6   15              9
                                 11      13  14                  19
(End)

Alois P. Heinz, Rows n = 0..14, flattened

Row lengths are A011782.
Allowing empty subsequences gives A124771.
Dominates A333224, the version counting subsequence-sums instead of subsequences.
Compositions where every restriction to a subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.
Cf. A000120, A003022, A029931, A048793, A066099, A070939, A103295, A108917, A143823, A325680.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[ReplaceList[stc[n],{_,s__,_}:>{s}]]],{n,0,100}] (* Gus Wiseman, Apr 03 2020 *)

a(n) = A124771(n) - 1. - Gus Wiseman, Apr 03 2020

A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

Original entry on oeis.org

1, 1, 1, 1, 4, 5, 8, 22, 40, 56, 78, 124, 222, 390, 616, 892, 1220, 1620, 2182, 3042, 4392, 6364, 9054, 12608, 16980, 22244, 28482, 36208, 45864, 58692, 75804, 98440, 128694, 168250, 218558, 281210, 357594, 449402, 560034, 693332, 853546, 1050118, 1293458, 1596144, 1975394

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..60

The subset case is A196723.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A108917, A143823, A143824, A276024.
Cf. A325858, A325859, A325864, A325865, A325867, A325879, A325880, A382398.

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

a(n)={
   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,b< n, ismaxl(b,w),
         my(s=self()(k+1, r, b, w));
         if(!bitand(w,b<Andrew Howroyd, Mar 23 2025

a(21) onwards from Andrew Howroyd, Mar 23 2025

cp's OEIS Frontend

A325858 Number of Golomb partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325860 Number of subsets of {1..n} such that every pair of distinct elements has a different quotient.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A325864 Number of subsets of {1..n} of which every subset has a different sum.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A347460 Number of distinct possible alternating products of factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A143824 Size of the largest subset {x(1),x(2),...,x(k)} of {1,2,...,n} with the property that all differences |x(i)-x(j)| are distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A325768 Number of integer partitions of n for which every restriction to a subinterval has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325877 Number of strict integer partitions of n such that every orderless pair of distinct parts has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325687 Triangle read by rows where T(n,k) is the number of length-k compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs