cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 57, 91, 140, 216, 317, 463, 668, 962, 1359, 1919, 2666, 3694, 5035, 6845, 9188, 12366, 16417, 21787, 28708, 37722, 49083, 63921, 82640, 106722, 136675, 174895, 222558, 283108, 357727, 451575, 567536, 712856, 890405, 1112081, 1382416, 1717540
Offset: 0

Views

Author

John W. Layman, Sep 02 2008

Keywords

Comments

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 this sequence is basically the number of Sidon subsets of {1,2,...,n}. - Sayan Dutta, Feb 15 2024
See A143824 for sizes of the largest subsets of {1,2,...,n} with the desired property.
Also the number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum. - Gus Wiseman, Jun 07 2019

Examples

			{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, so {1,2,4} is counted as one of the 13 subsets of {1,2,3,4} with the desired property.  Only 2^4-13=3 subsets of {1,2,3,4} do not have this property: {1,2,3}, {2,3,4}, {1,2,3,4}.
From _Gus Wiseman_, May 17 2019: (Start)
The a(0) = 1 through a(5) = 22 subsets:
  {}  {}   {}     {}     {}       {}
      {1}  {1}    {1}    {1}      {1}
           {2}    {2}    {2}      {2}
           {1,2}  {3}    {3}      {3}
                  {1,2}  {4}      {4}
                  {1,3}  {1,2}    {5}
                  {2,3}  {1,3}    {1,2}
                         {1,4}    {1,3}
                         {2,3}    {1,4}
                         {2,4}    {1,5}
                         {3,4}    {2,3}
                         {1,2,4}  {2,4}
                         {1,3,4}  {2,5}
                                  {3,4}
                                  {3,5}
                                  {4,5}
                                  {1,2,4}
                                  {1,2,5}
                                  {1,3,4}
                                  {1,4,5}
                                  {2,3,5}
                                  {2,4,5}
(End)
		

Crossrefs

First differences are A308251.
Second differences are A169942.
Row sums of A381476.
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.

Programs

  • Maple
    b:= proc(n, s) local sn, m;
          if n<1 then 1
        else sn:= [s[], n];
             m:= nops(sn);
             `if`(m*(m-1)/2 = nops(({seq(seq(sn[i]-sn[j],
               j=i+1..m), i=1..m-1)})), b(n-1, sn), 0) +b(n-1, s)
          fi
        end:
    a:= proc(n) option remember;
           b(n-1, [n]) +`if`(n=0, 0, a(n-1))
        end:
    seq(a(n), n=0..30);  # Alois P. Heinz, Sep 14 2011
  • Mathematica
    b[n_, s_] := Module[{ sn, m}, If[n<1, 1, sn = Append[s, n]; m = Length[sn]; If[m*(m-1)/2 == Length[Table[sn[[i]] - sn[[j]], {i, 1, m-1}, {j, i+1, m}] // Flatten // Union], b[n-1, sn], 0] + b[n-1, s]]]; a[n_] := a[n] = b[n - 1, {n}] + If[n == 0, 0, a[n-1]]; Table [a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 08 2015, after Alois P. Heinz *)
    Table[Length[Select[Subsets[Range[n]],UnsameQ@@Abs[Subtract@@@Subsets[#,{2}]]&]],{n,0,15}] (* Gus Wiseman, May 17 2019 *)
  • Python
    from itertools import combinations
    def is_sidon_set(s):
        allsums = []
        for i in range(len(s)):
            for j in range(i, len(s)):
                allsums.append(s[i] + s[j])
        if len(allsums)==len(set(allsums)):
            return True
        return False
    def a(n):
        sidon_count = 0
        for r in range(n + 1):
            subsets = combinations(range(1, n + 1), r)
            for subset in subsets:
                if is_sidon_set(subset):
                    sidon_count += 1
        return sidon_count
    print([a(n) for n in range(20)]) # Sayan Dutta, Feb 15 2024
    
  • Python
    from functools import cache
    def b(n, s):
        if n < 1: return 1
        sn = s + [n]
        m = len(sn)
        return (b(n-1, sn) if m*(m-1)//2 == len(set(sn[i]-sn[j] for i in range(m-1) for j in range(i+1, m))) else 0) + b(n-1, s)
    @cache
    def a(n): return b(n-1, [n]) + (0 if n==0 else a(n-1))
    print([a(n) for n in range(31)]) # Michael S. Branicky, Feb 15 2024 after Alois P. Heinz

Formula

a(n) = A169947(n-1) + n + 1 for n>=2. - Nathaniel Johnston, Nov 12 2010
a(n) = A054578(n) + 1 for n>0. - Alois P. Heinz, Jan 17 2013

Extensions

a(21)-a(29) from Nathaniel Johnston, Nov 12 2010
Corrected a(21)-a(29) and more terms from Alois P. Heinz, Sep 14 2011

A241688 Number of Sidon subsets of {1,...,n} of size 4.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 2, 10, 26, 60, 110, 190, 304, 466, 676, 958, 1312, 1762, 2310, 2984, 3786, 4750, 5874, 7196, 8720, 10484, 12488, 14780, 17360, 20276, 23530, 27174, 31210, 35696, 40630, 46074, 52032, 58566, 65676, 73434, 81840, 90966, 100814, 111460, 122906
Offset: 1

Views

Author

Carl Najafi, Apr 27 2014

Keywords

Comments

A Sidon set is a set of natural numbers A={a_1,a_2,...}, finite or infinite, such that all pairwise sums a_i+a_j (i <= j) are different.

Examples

			a(7)=2 since the only subsets of {1,...,7} satisfying the required conditions are {1,2,5,7} and {1,3,6,7}.
		

Crossrefs

Column k=4 of A381476.
Cf. A054578.

Programs

  • Mathematica
    SidonQ[l__] := If[Length[Join[Plus @@@ Subsets[l, {2}], 2 l]] == Length[Union[Join[Plus @@@ Subsets[l, {2}], 2 l]]], True, False]
    Table[Length@Select[Subsets[Range[n], {4}], SidonQ[#] &], {n, 1, 30}]

Formula

It appears to be the case that G.f.: 2*x^7*(1+3*x+3*x^2+5*x^3)/((1-x)^5*(1+x)^2*(1+x^2)*(1+x+x^2)), corrected by Vaclav Kotesovec, May 03 2014
a(n) ~ 1/24*n^4 (deduced from g.f.). - Ralf Stephan, Apr 29 2014
a(n) = a(n-11)+a(n-8)-a(n-3)+2*(a(n-6)+a(n-1)-a(n-10)-a(n-5)). - Fung Lam, May 02 2014
Explicit formula (derived from g.f.): a(n) = n^4/24 - 7*n^3/12 + 29*n^2/12 - 15*n/8 - floor(n/4) - 4/3*floor(n/3) + (n/2-9/4)*floor(n/2) - floor((n+1)/4) - 2/3*floor((n+1)/3). - Vaclav Kotesovec, May 03 2014

A241689 Number of Sidon subsets of {1,...,n} of size 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 22, 68, 156, 320, 584, 1008, 1622, 2520, 3734, 5428, 7612, 10488, 14126, 18744, 24390, 31436, 39914, 50212, 62390, 76932, 93918, 113960, 137058, 163896, 194632, 229988, 270018, 315712, 367106, 425220, 490164, 563080, 644096
Offset: 1

Views

Author

Carl Najafi, Apr 27 2014

Keywords

Comments

A Sidon set is a set of natural numbers A={a_1,a_2,...}, finite or infinite, such that all pairwise sums a_i+a_j (i <= j) are different.

Examples

			a(12)=4 since the only subsets of {1,...,12} satisfying the required conditions are {1,2,5,10,12}, {1,3,8,9,12}, {1,3,8,11,12}, and {1,4,5,10,12}.
		

Crossrefs

Column k=5 of A381476.
Cf. A054578.

Programs

  • Mathematica
    SidonQ[l__] := If[Length[Join[Plus @@@ Subsets[l, {2}], 2 l]] == Length[Union[Join[Plus @@@ Subsets[l, {2}], 2 l]]], True, False]
    Table[Length@Select[Subsets[Range[n], {5}], SidonQ[#] &], {n, 1, 30}]

A241690 Number of Sidon subsets of {1,...,n} of size 6.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 24, 80, 206, 504, 1004, 1910, 3380, 5688, 9036, 14106, 21190, 31158, 44370, 62206, 85308, 115662, 153746, 202146, 262156, 336960, 427488, 538690, 671604, 831926, 1021238, 1246604, 1510056, 1820580, 2179480
Offset: 1

Views

Author

Carl Najafi, Apr 27 2014

Keywords

Comments

A Sidon set is a set of natural numbers A={a_1,a_2,...}, finite or infinite, such that all pairwise sums a_i+a_j (i <= j) are different.

Examples

			a(18)=8 since there are 8 subsets of {1,...,18} satisfying the required conditions, for example {1,2,5,11,13,18}.
		

Crossrefs

Column k=6 of A381476.
Cf. A054578.

Programs

  • Mathematica
    SidonQ[l__] := If[Length[Join[Plus @@@ Subsets[l, {2}], 2 l]] == Length[Union[Join[Plus @@@ Subsets[l, {2}], 2 l]]], True, False]
    Table[Length@Select[Subsets[Range[n], {6}], SidonQ[#] &], {n, 1, 30}]
Showing 1-4 of 4 results.