A325879 Number of maximal subsets of {1..n} such that every ordered pair of distinct elements has a different difference.

1, 1, 1, 3, 3, 6, 14, 20, 24, 36, 64, 110, 176, 238, 294, 370, 504, 736, 1086, 1592, 2240, 2982, 3788, 4700, 5814, 7322, 9396, 12336, 16552, 22192, 29310, 38046, 48368, 60078, 73722, 89416, 108208, 131310, 160624, 198002, 247408, 310410, 390924, 490818, 613344, 758518

Offset

0,4

Comments

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

Links

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

Wikipedia, Sidon sequence.

Index entries for sequences related to Golomb rulers.

Example

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

Mathematica

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

Prog

(PARI)
a(n)={
  my(ismaxl(b, w)=for(k=1, n, if(!bittest(b, k) && !bitand(w, bitor(b, 1<<k)<<k), return(0))); 1);
  my(recurse(k, b, w)=
      if(k > n, ismaxl(b, w),
         my(s=self()(k+1, b, w));
         b+=1<<k; if(!bitand(w, b<<k), s+=self()(k+1, b, w + (b<<k)));
         s);
  );
  recurse(1, 0, 0);
} \\ Andrew Howroyd, Mar 27 2025

Crossrefs

The subset case is A143823.

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, A143824, A196723, A382397.

Cf. A325859, A325861, A325865, A325867, A325869, A325878, A325992.

Sequence in context: A123289 A096572 A318540 * A325865 A110523 A145597

Adjacent sequences: A325876 A325877 A325878 * A325880 A325881 A325882

Keyword

nonn

Author

Gus Wiseman, Jun 02 2019

Extensions

a(21)-a(45) from Fausto A. C. Cariboni, Feb 08 2022

Status

approved