A008404 -id:A008404 - cp's OEIS frontend

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

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

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

A320448 a(n) is the maximum number of distinct distances between n non-attacking rooks on an n X n chessboard.

Original entry on oeis.org

0, 1, 2, 4, 8, 11, 15, 20, 25, 31, 37, 44, 51, 59, 68

Offset: 1

Peter Kagey, Oct 12 2018

A319476(n) <= a(n) <= n(n-1)/2.

			For n = 5 a placement of five rooks on a 5 X 5 board with a(5) = 8 distinct distances is:
  +---+---+---+---+---+
5 |   | * |   |   |   |
  +---+---+---+---+---+
4 | * |   |   |   |   |
  +---+---+---+---+---+
3 |   |   |   |   | * |
  +---+---+---+---+---+.
2 |   |   | * |   |   |
  +---+---+---+---+---+
1 |   |   |   | * |   |
  +---+---+---+---+---+
    A   B   C   D   E
The distances between pairs of pieces are:
1)   sqrt(2)  (A4 to B5 and C2 to D1)
2) 2*sqrt(2)  (A4 to C2)
3) 3*sqrt(2)  (A4 to D1)
4)   sqrt(17) (A4 to E3)
5)   sqrt(10) (B5 to C2)
6) 2*sqrt(5)  (B5 to D1)
7)   sqrt(13) (B5 to E3)
8)   sqrt(5)  (C2 to E3 and D1 to E3)

Giovanni Resta, Illustration of a(3)-a(14)

Cf. A008404, A319476, A320575, A320576, A320448, A320573, A320574.

a(11)-a(14) from Giovanni Resta, Oct 17 2018

a(15) from Bert Dobbelaere, Jan 01 2019

A319476 a(n) is the minimum number of distinct distances between n non-attacking rooks on an n X n chessboard.

Original entry on oeis.org

0, 1, 2, 2, 3, 5, 5, 6, 5, 7, 9, 7, 8, 11, 13, 9, 11, 14, 16, 17, 19, 21, 21, 14, 14

Offset: 1

Peter Kagey, Oct 12 2018

a(n) <= n - 1, which is the number of distinct distances the rooks are placed along a diagonal.

Conjecture: a(n^2) = A047800(n-1) - 1. - Peter Kagey, Nov 02 2018

			For n = 7 a board with a(7) = 5 distinct distances is
  +---+---+---+---+---+---+---+
7 |   |   | * |   |   |   |   |
  +---+---+---+---+---+---+---+
6 |   |   |   |   |   | * |   |
  +---+---+---+---+---+---+---+
5 | * |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+
4 |   |   |   | * |   |   |   |
  +---+---+---+---+---+---+---+.
3 |   |   |   |   |   |   | * |
  +---+---+---+---+---+---+---+
2 |   | * |   |   |   |   |   |
  +---+---+---+---+---+---+---+
1 |   |   |   |   | * |   |   |
  +---+---+---+---+---+---+---+
    A   B   C   D   E   F   G
The distances between pairs of points are:
1)   sqrt(10) (e.g., A5 to B2),
2) 2*sqrt(2)  (e.g., A5 to C7),
3) 4*sqrt(2)  (e.g., B2 to F6),
4) 2*sqrt(10) (e.g., A5 to G3), and
5)   sqrt(26) (e.g., A5 to F6).

Giovanni Resta, Illustration of a(3)-a(14)

Cf. A008404, A319476, A320575, A320576, A320448, A320573, A320574.

a(11)-a(14) from Giovanni Resta, Oct 17 2018

a(15)-a(25) from Bert Dobbelaere, Dec 30 2018

A213338 Costas arrays such that the corresponding permutation is cyclic.

Original entry on oeis.org

1, 1, 2, 2, 10, 26, 32, 74, 54, 198, 486, 726, 1112, 1438, 1570, 1576, 1220, 954, 888, 464, 194, 116, 48, 8, 0, 0, 0, 36, 0

Offset: 1

Joerg Arndt, Jun 09 2012

Scott Rickard, costasarrays.org (information and papers about Costas arrays).

Cf. A008404 (Costas arrays), A213270 (Costas arrays that are involutions), A213271 (Costas arrays that are derangements), A213339 (Costas arrays that are connected).

A001441 Number of inequivalent Costas arrays of order n under dihedral group.

Original entry on oeis.org

1, 1, 1, 2, 6, 17, 30, 60, 100, 277, 555, 990, 1616, 2168, 2467, 2648, 2294, 1892, 1283, 810, 446, 259, 114, 25, 12, 8, 29, 89, 23

Offset: 1

N. J. A. Sloane

Dihedral group of order 8 acts by rotations and reflections of the square.

James K Beard, Jon C Russo, Keith Erickson, Michael Moneleone and Mike Wright, Combinatoric collaboration on Costas arrays and radar applications, Proceedings of the IEEE 2004 Radar Conference, April 26-29 2004, ISBN 0-7803-8234-X, pp. 260-265 (entries for orders 24 and 25).
James K Beard, Jon C Russo, Keith Erickson, Michael Moneleone and Mike Wright,"Costas Array Generation and Search Methodology," to appear in IEEE Transactions on Aerospace and Electronic Engineering. (Order 26)
CRC Handbook of Combinatorial Designs, C. Colbourn and J. Dinitz, Editors, 1996, IV.7: Costas Arrays by Herbert Taylor (IV.7.6, page 259, Table 2.29).
CRC Standard Mathematical Tables and Formulae, 30th ed. 1996, p. 227 (contains errors).

K. Drakakis, Results of the enumeration of Costas arrays of order 27, Slides, 2008.

Cf. A008404, A001440, A001442, A008403.

a(24)-a(26) from James K Beard (jkbeard(AT)comcast.net), Dec 04 2005
a(27) (from the Drakakis link) sent by John Healy (johnjhealy(AT)gmail.com), Jul 17 2008
a(28) and a(29) (from http://www.costasarrays.org/), Joerg Arndt, Jun 08 2012.

A213270 Costas arrays such that the corresponding permutation is an involution.

Original entry on oeis.org

1, 2, 2, 2, 4, 10, 20, 18, 20, 28, 36, 34, 50, 46, 62, 40, 38, 20, 12, 8, 16, 10, 20, 0, 4, 4, 14, 0, 10

Offset: 1

Joerg Arndt, Jun 08 2012

Self-inverse permutations such that each row in the difference table consists of pairwise distinct elements (see example).

			The permutation (4, 7, 9, 1, 6, 5, 2, 8, 3) is an involution and corresponds to a Costas array:
   4  7  9  1  6  5  2  8  3  (Permutation: p(1), p(2), p(3), ..., p(n) )
   3  2 -8  5 -1 -3  6 -5     (step-1 differences: p(2)-p(1), p(3)-p(2), ... )
   5 -6 -3  4 -4  3  1        (step-2 differences: p(3)-p(1), p(4)-p(2), ... )
  -3 -1 -4  1  2 -2           (step-3 differences: p(4)-p(1), p(5)-p(2), ... )
   2 -2 -7  7 -3              ( etc. )
   1 -5 -1  2
  -2  1 -6
   4 -4
  -1

Scott Rickard, costasarrays.org (information and papers about Costas arrays).

Cf. A008404 (Costas arrays), A213271 (Costas arrays that are derangements), A213338 (Costas arrays that are cyclic), A213339 (Costas arrays that are connected).

A213271 Costas arrays such that the corresponding permutation is a derangement.

Original entry on oeis.org

0, 1, 2, 2, 18, 42, 66, 168, 300, 910, 1882, 3192, 5320, 7166, 8346, 9042, 7760, 6668, 4620, 2822, 1528, 942, 282, 92, 32, 22, 88, 256, 24

Offset: 1

Joerg Arndt, Jun 08 2012

Fixed-point free permutations such that each row in the difference table consists of pairwise distinct elements (see example).

			The permutation (9, 8, 1, 6, 3, 7, 2, 4, 5) is a derangement and corresponds to a Costas array:
   9  8  1  6  3  7  2  4  5  (Permutation: p(1), p(2), p(3), ..., p(n) )
  -1 -7  5 -3  4 -5  2  1     (step-1 differences: p(2)-p(1), p(3)-p(2), ... )
  -8 -2  2  1 -1 -3  3        (step-2 differences: p(3)-p(1), p(4)-p(2), ... )
  -3 -5  6 -4  1 -2           (step-3 differences: p(4)-p(1), p(5)-p(2), ... )
  -6 -1  1 -2  2              ( etc. )
  -2 -6  3 -1
  -7 -4  4
  -5 -3
  -4

Scott Rickard, costasarrays.org (information and papers about Costas arrays).

Cf. A008404 (Costas arrays), A213270 (Costas arrays that are involutions), A213338 (Costas arrays that are cyclic), A213339 (Costas arrays that are connected).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A320448 a(n) is the maximum number of distinct distances between n non-attacking rooks on an n X n chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A319476 a(n) is the minimum number of distinct distances between n non-attacking rooks on an n X n chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A213338 Costas arrays such that the corresponding permutation is cyclic.

Views

Author

Keywords

Links

Crossrefs

A001441 Number of inequivalent Costas arrays of order n under dihedral group.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A213270 Costas arrays such that the corresponding permutation is an involution.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A213271 Costas arrays such that the corresponding permutation is a derangement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A213339 Costas arrays such that the corresponding permutation is connected.

Views

Author

Keywords

Links

Crossrefs

A001440 Number of symmetric Costas arrays of order n that are inequivalent under dihedral group.

Views

Author

Keywords

References

Crossrefs

A001442 G-symmetric Costas arrays of order n that are inequivalent under dihedral group.

Views

Author

Keywords