login
Number of inequivalent Golomb rulers with n marks and shortest length.
6

%I #22 Feb 23 2022 22:32:57

%S 1,1,1,2,4,5,1,1,1,2,1,1,1,1,1,1,1,1

%N Number of inequivalent Golomb rulers with n marks and shortest length.

%C From _Gus Wiseman_, May 31 2019: (Start)

%C 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. For example, the a(2) = 1 through a(8) = 1 Golomb rulers are:

%C 2: {0,1}

%C 3: {0,1,3}

%C 4: {0,1,4,6}

%C 5: {0,1,4,9,11}

%C 5: {0,2,7,8,11}

%C 6: {0,1,4,10,12,17}

%C 6: {0,1,4,10,15,17}

%C 6: {0,1,8,11,13,17}

%C 6: {0,1,8,12,14,17}

%C 7: {0,1,4,10,18,23,25}

%C 7: {0,1,7,11,20,23,25}

%C 7: {0,2,3,10,16,21,25}

%C 7: {0,2,7,13,21,22,25}

%C 7: {0,1,11,16,19,23,25}

%C 8: {0,1,4,9,15,22,32,34}

%C Also half the number of length-(n - 1) compositions of A003022(n) such that every consecutive subsequence has a different sum. For example, the a(2) = 1 through a(8) = 1 compositions are (A = 10):

%C 2: (1)

%C 3: (1,2)

%C 4: (1,3,2)

%C 5: (1,3,5,2)

%C 5: (2,5,1,3)

%C 6: (1,3,6,2,5)

%C 6: (1,3,6,5,2)

%C 6: (1,7,3,2,4)

%C 6: (1,7,4,2,3)

%C 7: (1,3,6,8,5,2)

%C 7: (1,6,4,9,3,2)

%C 7: (2,1,7,6,5,4)

%C 7: (2,5,6,8,1,3)

%C 7: (1,A,5,3,4,2)

%C 8: (1,3,5,6,7,A,2)

%C (End)

%H Anonymous, <a href="http://members.aol.com/golomb20">In Search Of The Optimal 20, 21 and 22 Mark Golomb Rulers</a>

%H Distributed.Net, <a href="http://www.distributed.net/ogr">Project OGR</a>

%H J. B. Shearer, <a href="http://www.research.ibm.com/people/s/shearer/gropt.html">Table of known optimal Golomb rulers</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GolombRuler.html">Golomb Ruler</a>

%H <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>

%Y Cf. A003022, A039953, A054578, A108917, A143823, A169942, A270813, A325677, A325683.

%K nonn,hard,nice,more

%O 2,4

%A _N. J. A. Sloane_