A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct.
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
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)
Links
- Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100 (terms 0..60 from Alois P. Heinz, 61..81 from Vaclav Kotesovec)
- Thomas Bloom, Problem 861, Erdős Problems.
- Terence Tao, Erdős problem database, see no. 861.
- Wikipedia, Sidon sequence.
Crossrefs
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
Comments