Svoboda | Graniru | BBC Russia | Golosameriki | Facebook
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a325679 -id:a325679
Displaying 1-7 of 7 results found. page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A143823 Number of subsets {x(1),x(2),...,x(k)} of {1,2,...,n} such that all differences |x(i)-x(j)| are distinct. +10
70
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
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
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)
Wikipedia, Sidon sequence.
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
EXAMPLE
{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)
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 *)
PROG
(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
CROSSREFS
First differences are A308251.
Second differences are A169942.
The subset case is A143823 (this sequence).
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. A143824, A054578, A169947.
Cf. A000079, A108917, A143824, A169942, A308251, A325676, A325677, A325679, A325683, A325860, A325864, A241688, A241689, A241690.
KEYWORD
nonn
AUTHOR
John W. Layman, Sep 02 2008
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
STATUS
approved
A169942 Number of Golomb rulers of length n. +10
49
1, 1, 3, 3, 5, 7, 13, 15, 27, 25, 45, 59, 89, 103, 163, 187, 281, 313, 469, 533, 835, 873, 1319, 1551, 2093, 2347, 3477, 3881, 5363, 5871, 8267, 9443, 12887, 14069, 19229, 22113, 29359, 32229, 44127, 48659, 64789, 71167, 94625, 105699, 139119, 151145, 199657 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
Wanted: a recurrence. Are any of A169940-A169954 related to any other entries in the OEIS?
Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012
Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 1..99
T. Pham, Enumeration of Golomb Rulers (Master's thesis), San Francisco State U., 2011.
Eric Weisstein's World of Mathematics, Golomb Ruler.
Index entries for sequences related to carryless arithmetic
Index entries for sequences related to Golomb rulers
FORMULA
a(n) = A169952(n) - A169952(n-1) for n>1. - Andrew Howroyd, Jul 09 2017
EXAMPLE
For n=2, there is one Golomb Ruler: {0,2}. For n=3, there are three: {0,3}, {0,1,3}, {0,2,3}. - Tomas Boothby, May 15 2012
From Gus Wiseman, May 16 2019: (Start)
The a(1) = 1 through a(8) = 15 compositions such that every restriction to a subinterval has a different sum:
(1) (2) (3) (4) (5) (6) (7) (8)
(12) (13) (14) (15) (16) (17)
(21) (31) (23) (24) (25) (26)
(32) (42) (34) (35)
(41) (51) (43) (53)
(132) (52) (62)
(231) (61) (71)
(124) (125)
(142) (143)
(214) (152)
(241) (215)
(412) (251)
(421) (341)
(512)
(521)
(End)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}] (* Gus Wiseman, May 16 2019 *)
PROG
(Sage)
def A169942(n):
R = QQ['x']
return sum(1 for c in cartesian_product([[0, 1]]*n) if max(R([1] + list(c) + [1])^2) == 2)
[A169942(n) for n in range(1, 8)]
# Tomas Boothby, May 15 2012
CROSSREFS
Related to thickness: A169940-A169954, A061909.
Related to Golomb rulers: A036501, A054578, A143823.
Row sums of A325677.
Cf. A000079, A103295, A103300, A108917, A143824, A325466, A325545, A325676, A325678, A325679, A325683, A325686.
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Aug 01 2010
EXTENSIONS
a(15)-a(30) from Nathaniel Johnston, Nov 12 2011
a(31)-a(50) from Tomas Boothby, May 15 2012
STATUS
approved
A325683 Number of maximal Golomb rulers of length n. +10
24
1, 1, 1, 2, 2, 4, 2, 6, 8, 18, 16, 24, 20, 28, 42, 76, 100, 138, 168, 204, 194, 272, 276, 450, 588, 808, 992, 1578, 1612, 1998, 2166, 2680, 2732, 3834, 3910, 5716, 6818, 9450, 10524, 15504, 16640, 22268, 23754, 30430, 31498, 40644, 40294, 52442, 56344, 72972, 77184 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
A Golomb ruler of length n is a subset of {0..n} containing 0 and n and such that every pair of distinct terms has a different difference up to sign.
Also the number of minimal (most refined) compositions of n such that every restriction to a subinterval has a different sum.
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Golomb Ruler.
EXAMPLE
The a(1) = 1 through a(8) = 8 maximal Golomb rulers:
{0,1} {0,2} {0,1,3} {0,1,4} {0,1,5} {0,1,4,6} {0,1,3,7} {0,1,3,8}
{0,2,3} {0,3,4} {0,2,5} {0,2,5,6} {0,1,5,7} {0,1,5,8}
{0,3,5} {0,2,3,7} {0,1,6,8}
{0,4,5} {0,2,6,7} {0,2,3,8}
{0,4,5,7} {0,2,7,8}
{0,4,6,7} {0,3,7,8}
{0,5,6,8}
{0,5,7,8}
The a(1) = 1 through a(10) = 16 minimal compositions:
(1) (2) (12) (13) (14) (132) (124) (125) (126) (127)
(21) (31) (23) (231) (142) (143) (135) (136)
(32) (214) (152) (153) (154)
(41) (241) (215) (162) (163)
(412) (251) (216) (172)
(421) (341) (234) (217)
(512) (243) (253)
(521) (261) (271)
(315) (316)
(324) (352)
(342) (361)
(351) (451)
(423) (613)
(432) (631)
(513) (712)
(531) (721)
(612)
(621)
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Accumulate/@Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]]], {n, 0, 15}]
CROSSREFS
Rightmost column of A325677.
Cf. A000079, A103295, A108917, A143823, A169942, A276024.
Cf. A325676, A325678, A325679, A325681, A325687.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 13 2019
EXTENSIONS
a(21)-a(50) from Fausto A. C. Cariboni, Feb 22 2022
STATUS
approved
A325677 Irregular triangle read by rows where T(n,k) is the number of Golomb rulers of length n with k + 1 marks, k > 0. +10
21
1, 1, 1, 2, 1, 2, 1, 4, 1, 4, 2, 1, 6, 6, 1, 6, 8, 1, 8, 18, 1, 8, 16, 1, 10, 30, 4, 1, 10, 34, 14, 1, 12, 48, 28, 1, 12, 48, 42, 1, 14, 72, 76, 1, 14, 72, 100, 1, 16, 96, 160, 8, 1, 16, 98, 190, 8, 1, 18, 126, 284, 40, 1, 18, 128, 316, 70 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
Also the number of length-k compositions of n such that every restriction to a subinterval has a different sum. A composition of n is a finite sequence of positive integers summing to n.
LINKS
Table of n, a(n) for n=1..67.
Eric Weisstein's World of Mathematics, Golomb Ruler.
EXAMPLE
Triangle begins:
1
1
1 2
1 2
1 4
1 4 2
1 6 6
1 6 8
1 8 18
1 8 16
1 10 30 4
1 10 34 14
1 12 48 28
1 12 48 42
1 14 72 76
1 14 72 100
1 16 96 160 8
1 16 98 190 8
1 18 126 284 40
1 18 128 316 70
Row n = 8 counts the following rulers:
{0,8} {0,1,8} {0,1,3,8}
{0,2,8} {0,1,5,8}
{0,3,8} {0,1,6,8}
{0,5,8} {0,2,3,8}
{0,6,8} {0,2,7,8}
{0,7,8} {0,3,7,8}
{0,5,6,8}
{0,5,7,8}
and the following compositions:
(8) (17) (125)
(26) (143)
(35) (152)
(53) (215)
(62) (251)
(71) (341)
(512)
(521)
MATHEMATICA
DeleteCases[Table[Length[Select[Join@@Permutations/@IntegerPartitions[n, {k}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}, {k, n}], 0, {2}]
CROSSREFS
Row sums are A169942.
Row lengths are A325678(n) = A143824(n + 1) - 1.
Column k = 2 is A052928.
Column k = 3 is A325686.
Rightmost column is A325683.
Cf. A000079, A007318, A103295, A108917, A143823, A325676, A325679, A325687.
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, May 13 2019
STATUS
approved
A325678 Maximum length of a composition of n such that every restriction to a subinterval has a different sum. +10
8
0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
Also the maximum number of nonzero marks on a Golomb ruler of length n.
LINKS
Table of n, a(n) for n=0..83.
FORMULA
a(n) + 1 = A143824(n + 1).
MATHEMATICA
Table[Max[Length/@Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 0, 15}]
CROSSREFS
Run-lengths are A270813.
Cf. A000079, A007318, A103295, A108917, A143823, A169942.
Cf. A325466, A325676, A325677, A325679, A325681, A325683, A325687.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 13 2019
STATUS
approved
A325789 Number of perfect necklace compositions of n. +10
6
1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence.
LINKS
Table of n, a(n) for n=1..40.
FORMULA
For n > 1, a(n) = A325787(n) + 1.
EXAMPLE
The a(1) = 1 , a(2) = 1, a(3) = 2, a(7) = 3, a(13) = 5, and a(31) = 11 perfect necklace compositions (A = 10, B = 11, C = 12, D = 13, E = 14):
1 11 12 124 1264 12546D
111 142 1327 1274C5
1111111 1462 13278A
1723 13625E
1111111111111 15C472
17324E
1A8723
1D6452
1E4237
1E5263
1111111111111111111111111111111
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
subalt[q_]:=Union[ReplaceList[q, {___, s__, ___}:>{s}], DeleteCases[ReplaceList[q, {t___, __, u___}:>{u, t}], {}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]], {n, 10}]
CROSSREFS
Cf. A002033, A008965, A103300, A108917, A126796, A325676, A325679, A325685, A325780, A325782, A325786, A325787, A325789.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, May 22 2019
STATUS
approved
A325681 Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum. +10
3
1, 1, 2, 2, 3, 3, 6, 6, 11, 9, 16, 16, 27, 23, 46, 42, 73, 63, 112, 102 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.
LINKS
Table of n, a(n) for n=1..20.
EXAMPLE
The a(1) = 1 through a(10) = 9 necklace compositions (A = 10):
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A)
(12) (13) (14) (15) (16) (17) (18) (19)
(23) (24) (25) (26) (27) (28)
(34) (35) (36) (37)
(124) (125) (45) (46)
(142) (152) (126) (127)
(135) (136)
(153) (163)
(162) (172)
(234)
(243)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
suball[q_]:=Join[Take[q, #]&/@Select[Tuples[Range[Length[q]], 2], OrderedQ], Drop[q, #]&/@Select[Tuples[Range[2, Length[q]-1], 2], OrderedQ]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&UnsameQ@@Total/@suball[#]&]], {n, 15}]
CROSSREFS
Cf. A000079, A000740, A008965, A108917, A143823, A169942, A276024.
Cf. A325676, A325677, A325678, A325679, A325682, A325683, A325687.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, May 13 2019
STATUS
approved
page 1

Search completed in 0.009 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 11 17:54 EDT 2024. Contains 375839 sequences. (Running on oeis4.)