A325466 -id:A325466 - cp's OEIS frontend

A325676 Number of compositions of n such that every distinct consecutive subsequence has a different sum.

1, 1, 2, 4, 5, 10, 12, 24, 26, 47, 50, 96, 104, 172, 188, 322, 335, 552, 590, 938, 1002, 1612, 1648, 2586, 2862, 4131, 4418, 6718, 7122, 10332, 11166, 15930, 17446, 24834, 26166, 37146, 41087, 55732, 59592, 84068, 89740, 122106, 133070, 177876, 194024, 262840, 278626

Offset: 0

Gus Wiseman, May 13 2019

nonn

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

Compare to the definition of knapsack partitions (A108917).

			The distinct consecutive subsequences of (1,4,4,3) together with their sums are:
   1: {1}
   3: {3}
   4: {4}
   5: {1,4}
   7: {4,3}
   8: {4,4}
   9: {1,4,4}
  11: {4,4,3}
  12: {1,4,4,3}
Because the sums are all different, (1,4,4,3) is counted under a(12).
The a(1) = 1 through a(6) = 12 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (1111)  (41)     (42)
                            (113)    (51)
                            (122)    (114)
                            (221)    (132)
                            (311)    (222)
                            (11111)  (231)
                                     (411)
                                     (111111)

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

Cf. A000079, A103295, A108917, A169942, A235998, A321143.

Cf. A325466, A325545, A325680, A325682, A325685, A325687, A325688.

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

a(21)-a(22) from Jinyuan Wang, Jun 20 2020
a(23)-a(25) from Robert Price, Jun 19 2021
a(26)-a(46) from Fausto A. C. Cariboni, Feb 10 2022

A003022 Length of shortest (or optimal) Golomb ruler with n marks.

Original entry on oeis.org

1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425, 480, 492, 553, 585

Offset: 2

N. J. A. Sloane

a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
From David W. Wilson, Aug 17 2007: (Start)
An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.
An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.
A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)
Positions where A143824 increases (see also A227590). - N. J. A. Sloane, Apr 08 2016
From Gus Wiseman, May 17 2019: (Start)
Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:
   0: ()
   1: (1)
   3: (2,1)
   6: (2,3,1)
  11: (3,1,5,2)
  17: (4,2,3,7,1)
Representatives of corresponding Golomb rulers are:
  {0}
  {0,1}
  {0,2,3}
  {0,2,5,6}
  {0,3,4,9,11}
  {0,4,6,9,16,17}
(End)

			a(5)=11 because 0-1-4-9-11 (0-2-7-10-11) resp. 0-3-4-9-11 (0-2-7-8-11) are shortest: there is no b0-b1-b2-b3-b4 with different distances |bi-bj| and max. |bi-bj| < 11.

CRC Handbook of Combinatorial Designs, 1996, p. 315.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
Miller, J. C. P., Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.
Ana Salagean, David Gardner and Raphael Phan, Index Tables of Finite Fields and Modular Golomb Rulers, in Sequences and Their Applications - SETA 2012, Lecture Notes in Computer Science. Volume 7280, 2012, pp. 136-147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Anonymous, In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Thomas Bloom, Problem 30, Problem 43, Problem 155, and Problem 861, Erdős Problems.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
Distributed.Net, Project OGR
Kent Freeman, Unpublished notes. [Scanned copy]
Michael Geißer, Theresa Körner, Sascha Kurz, and Anne Zahn, Squares with three digits, arXiv:2112.00444 [math.NT], 2021.
S. W. Golomb, Letter to N. J. A. Sloane, 1972.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13. [Annotated scanned copy]
Joseph Malkevitch, Weird Rulers.
Greg Martin and Kevin O'Bryant, Constructions of generalized Sidon sets, arXiv:math/0408081 [math.NT], 2004-2005.
Lloyd Miller, Golomb Rulers
Kevin O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
Ed Pegg, Jr., Math Games: Rulers, Arrays, and Gracefulness
Bill Rankin, Golomb Ruler Calculations
Walter Schneider, Golomb Rulers
James B. Shearer, Golomb ruler table
James B. Shearer, Table of Known Optimal Golomb Rulers
James B. Shearer, Difference Triangle Sets: Known optimal solutions.
James B. Shearer, Difference Triangle Sets: Discoverers
David Singmaster, David Fielker, and N. J. A. Sloane, Correspondence, August 1979
N. J. A. Sloane, First few optimal Golomb rulers
Terence Tao, Erdős problem database, see nos. 30, 43, 155, 861.
D. Vanderschel et al., In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers
Eric Weisstein's World of Mathematics, Golomb Ruler.
Wikipedia, Golomb ruler
Index entries for sequences related to Golomb rulers

See A106683 for triangle of marks.
Cf. A008404, A036501, A039953, A078106, A030873.
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11
A row or column of array in A234943.
Adding 1 to these terms gives A227590. Cf. A143824.
For first differences see A270813.
Cf. A103295, A108917, A143823, A169942.
Cf. A325466, A325545, A325676, A325677, A325678, A325683.

Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions[i],{i,0,15}],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&],Length] (* Gus Wiseman, May 17 2019 *)

from itertools import combinations, combinations_with_replacement, count
def a(n):
    for k in count(n-1):
        for c in combinations(range(k), n-1):
            c = c + (k, )
            ss = set()
            for s in combinations_with_replacement(c, 2):
                if sum(s) in ss: break
                else: ss.add(sum(s))
            if len(ss) == n*(n+1)//2: return k # Jianing Song, Feb 14 2025, adapted from the python program of A345731

a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007

425 sent by Ed Pegg Jr, Nov 15 2004
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev, Sep 29 2010
a(27) proved by OGR-27, added by David Consiglio, Jr., Jun 09 2014
a(28) proved by OGR-28, added by David Consiglio, Jr., Jan 19 2023

A169942 Number of Golomb rulers of length n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Aug 01 2010

nonn

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

			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)

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

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.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,15}] (* Gus Wiseman, May 16 2019 *)

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

a(n) = A169952(n) - A169952(n-1) for n>1. - Andrew Howroyd, Jul 09 2017

a(15)-a(30) from Nathaniel Johnston, Nov 12 2011

a(31)-a(50) from Tomas Boothby, May 15 2012

A325406 Triangle read by rows where T(n,k) is the number of reversed integer partitions of n with k distinct differences of any degree.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, May 03 2019

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2).
The zeroth differences of a sequence are the sequence itself, while the k-th differences for k > 0 are the differences of the (k-1)-th differences. The distinct differences of any degree are the union of the k-th differences for all k >= 0. For example, the k-th differences of (1,1,2,4) for k = 0...3 are:
  (1,1,2,4)
  (0,1,2)
  (1,1)
  (0)
so there are a total of 4 distinct differences of any degree, namely {0,1,2,4}.

			Triangle begins:
  1
  0  1
  0  1  1
  0  1  2  0
  0  1  2  2  0
  0  1  1  3  2  0
  0  1  4  2  3  1  0
  0  1  1  5  5  2  1  0
  0  1  3  5  6  3  3  1  0
  0  1  3  4  8  7  1  4  2  0
  0  1  3  6 11  7  5  2  4  2  1
  0  1  1  6 13  8  9  9  0  4  3  1
  0  1  6  7 11 12  9 10  8  4  3  2  2
  0  1  1  7 18  9 14 19  5 10  3  5  4  1
  0  1  3  9 17  9 22 20 15  9  7  6  5  4  1
  0  1  4  8 22 11 16 24 22 19 10 11  2  8  7  2
  0  1  4 10 23 15 24 23 27 27 12 14 11  8  8  5  5
Row n = 8 counts the following partitions:
  (8)  (44)        (17)       (116)     (134)   (1133)   (111122)
       (2222)      (26)       (125)     (233)   (11123)
       (11111111)  (35)       (1115)    (1223)  (11222)
                   (224)      (1124)
                   (1111112)  (11114)
                              (111113)

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

Row sums are A000041.

Cf. A049597, A049988, A279945, A320348, A325324, A325325, A325349, A325404, A325466.

Table[Length[Select[Reverse/@IntegerPartitions[n],Length[Union@@Table[Differences[#,i],{i,0,Length[#]}]]==k&]],{n,0,16},{k,0,n}]

cp's OEIS Frontend

A325676 Number of compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A003022 Length of shortest (or optimal) Golomb ruler with n marks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A169942 Number of Golomb rulers of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A325406 Triangle read by rows where T(n,k) is the number of reversed integer partitions of n with k distinct differences of any degree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325678 Maximum length of a composition of n such that every restriction to a subinterval has a different sum.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula