A004137 -id:A004137 - cp's OEIS frontend

A080060 Erroneous version of A004137 given in the reference.

3, 6, 9, 13, 17, 23, 29, 36, 43, 50, 59, 60, 79, 90, 101, 112, 123, 138

Offset: 3

dead

J.-C. Bermond, Graceful graphs, radio antennae and French windmills, pp. 18-37 of R. J. Wilson, editor, Graph Theory and Combinatorics. Pitman, London, 1978.

A103300 Number of perfect rulers with length n.

1, 1, 1, 2, 3, 4, 2, 12, 8, 4, 38, 30, 14, 6, 130, 80, 32, 12, 500, 326, 150, 66, 18, 4, 944, 460, 166, 56, 12, 6, 2036, 890, 304, 120, 20, 10, 2, 2678, 974, 362, 100, 36, 4, 2, 4892, 2114, 684, 238, 68, 22, 4, 16318, 6350, 2286, 836, 330, 108, 24, 12, 31980, 12252

Offset: 0

Peter Luschny, Feb 28 2005

For definitions, references and links related to complete rulers see A103294.
The values for n = 208-213 are 22,0,0,0,4,4 according to Arch D. Robison. The values for 199-207 are not yet known. - Peter Luschny, Feb 20 2014, Jun 28 2019
Zero values at 135, 136, 149, 150, 151, 164, 165, 166, 179, 180, 181, 195, 196, 209, 210, 211. - Ed Pegg Jr, Jun 23 2019 [These values were found by Arch D. Robison, see links. Peter Luschny, Jun 28 2019]
From Yannic Schröder, Feb 22 2021: (Start)
Zero values at 135, 136, 149, 150, 151, 164, 165, 166, 179, 180, 181, 195, 196 have been replaced with correct values using an additional mark.
A lower bound for 209 is 62, for 210 is 16, and for 211 is 204.
The verified value for 212 and for 213 is 4. (End)

			a(5)=4 counts the perfect rulers with length 5, {[0,1,3,5],[0,2,4,5],[0,1,2,5],[0,3,4,5]}.

Peter Luschny (0..123), Arch D. Robison (124..198) and Fabian Schwartau and Yannic Schröder (199..208), Table of n, a(n) for n = 0..208
Peter Luschny, Perfect and Optimal Rulers.
Ed Pegg, Sparse ruler data, Oct 20 2022.
Arch D. Robison, Parallel Computation of Sparse Rulers, Jan 14 2014.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
Index entries for sequences related to perfect rulers.

Cf. A004137 (Maximal number of edges in a graceful graph on n nodes).

Cf. A103301, A103297, A103298.

a(n) = T(n, A103298(n)) where the triangle T is described by A103294.

A103294 Triangle T, read by rows: T(n,k) = number of complete rulers with length n and k segments (n >= 0, k >= 0).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 1, 0, 0, 0, 4, 4, 1, 0, 0, 0, 2, 9, 5, 1, 0, 0, 0, 0, 12, 14, 6, 1, 0, 0, 0, 0, 8, 27, 20, 7, 1, 0, 0, 0, 0, 4, 40, 48, 27, 8, 1, 0, 0, 0, 0, 0, 38, 90, 75, 35, 9, 1, 0, 0, 0, 0, 0, 30, 134, 166, 110, 44, 10, 1, 0, 0, 0, 0, 0, 14, 166, 311, 277, 154, 54, 11, 1

Offset: 0

Peter Luschny, Feb 28 2005

If n=k then T(n,k)=1.
A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0 called marks.
A segment of a ruler is the space between two adjacent marks. The number of segments is the number of marks - 1.
A ruler is complete if the set of all distances it can measure is {1,2,3,...,k} for some integer k>=1.
A ruler is perfect if it is complete and no complete ruler with the same length possesses less marks.
A ruler is optimal if it is perfect and no perfect ruler with the same number of segments has a greater length.
The 'empty ruler' with length n=0 is considered perfect and optimal.

			Rows begin:
[1],
[0,1],
[0,0,1],
[0,0,2,1],
[0,0,0,3,1],
[0,0,0,4,4,1],
[0,0,0,2,9,5,1],
[0,0,0,0,12,14,6,1],
[0,0,0,0,8,27,20,7,1],
...
a(19)=T(5,4)=4 counts the complete rulers with length 5 and 4 segments: {[0,2,3,4,5],[0,1,3,4,5],[0,1,2,4,5],[0,1,2,3,5]}

G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications. Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
R. K. Guy, Modular difference sets and error correcting codes. in: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, chapter C10, pp. 181-183, 2004.
J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.

Fausto A. C. Cariboni, Rows n = 0..49, flattened (rows n = 0..39 from Hugo Pfoertner)
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
Peter Luschny, Perfect and Optimal Rulers
Peter Luschny, Table of Counts
Peter Luschny, Perfect rulers
Eric Weisstein's World of Mathematics, Perfect Rulers
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.
Index entries for sequences related to perfect rulers

Row sums give A103295.
Column sums give A103296.
The first nonzero entries in the rows give A103300.
The last nonzero entries in the columns give A103299.
The row numbers of the last nonzero entries in the columns give A004137.
Cf. A103295 through A103301, A004137, A212661.

marks[n_, k_] := Module[{i}, i[0] = 0; iter = Sequence @@ Table[{i[j], i[j - 1] + 1, n - k + j - 1}, {j, 1, k}]; Table[Join[{0}, Array[i, k], {n}],
     iter // Evaluate] // Flatten[#, k - 1]&];
completeQ[ruler_List] := Range[ruler[[-1]]] == Sort[ Union[ Flatten[ Table[ ruler[[i]] - ruler[[j]], {i, 1, Length[ruler]}, {j, 1, i - 1}]]]];
rulers[n_, k_] := Select[marks[n, k - 1], completeQ];
T[n_, n_] = 1; T[, 0] = 0; T[n, k_] := Length[rulers[n, k]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Quiet (* Jean-François Alcover, Jul 05 2019 *)

def isComplete(R) :
    S = Set([])
    L = len(R)-1
    for i in range(L,0,-1) :
        for j in (1..i) :
            S = S.union(Set([R[i]-R[i-j]]))
    return len(S) == R[L]
def Partsum(T) :
    return [add([T[j] for j in range(i)]) for i in (0..len(T))]
def Ruler(L, S) :
    return map(Partsum, Compositions(L, length=S))
def CompleteRuler(L, S) :
    return tuple(filter(isComplete, Ruler(L, S)))
for n in (0..8):
    print([len(CompleteRuler(n,k)) for k in (0..n)]) # Peter Luschny, Jul 05 2019

Typo in data corrected by Jean-François Alcover, Jul 05 2019

A046693 Size of smallest subset S of N={0,1,2,...,n} such that S-S=N, where S-S={abs(i-j) | i,j in S}.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset: 0

John W. Layman

It is easy to show that a(n+1) must be no larger than a(n)+1. Problem: Can a(n+1) ever be smaller than a(n)?
Problem above solved in A103300. a(137) smaller than a(136).
Except for initial term, round(sqrt(3*n + 9/4)) up to n=51. See A308766 for divergences up to n=213. See A326499 for a list of best known solutions.
From Ed Pegg Jr, Jun 23 2019: (Start)
Minimal marks for a sparse ruler of length n.
Minimal vertices in a graceful graph with n edges. (End)

			a(10)=6 since all integers in {0,1,2...10} are differences of elements of {0,1,2,3,6,10}, but not of any 5-element set.
a(17)=7 since all integers in {0,1,2...17} are differences of elements of {0,1,8,11,13,15,17}, but not of any 6-element set.
In other words, {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. A004137(7)=17.

Ed Pegg Jr, Table of n, a(n) for n = 0..213
Andrew Granville and Friedrich Roesler, The set of differences of a given set.
Andrew Granville and Friedrich Roesler, The set of differences of a given set, Amer. Math. Monthly, 106 (1999), 338-344.
J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.
Ed Pegg Jr, Best known values A046693(n)-round(sqrt(3*n+9/4)) up to 1750.
Aleksi Saarela and Aleksi Vanhatalo, A Connection Between Unbordered Partial Words and Sparse Rulers, arXiv:2408.16335 [math.CO], 2024. See p. 17.

Cf. A004137, A103300, A308766, A309407, A326499. - Ed Pegg Jr, Sep 14 2019

Prepend[Table[Round[Sqrt[3*n+9/4]]+If[MemberQ[A308766,n],1,0],{n,1,213}],1]

A289761 Maximum length of a perfect Wichmann ruler with n segments.

Original entry on oeis.org

3, 6, 9, 12, 15, 22, 29, 36, 43, 50, 57, 68, 79, 90, 101, 112, 123, 138, 153, 168, 183, 198, 213, 232, 251, 270, 289, 308, 327, 350, 373, 396, 419, 442, 465, 492, 519, 546, 573, 600, 627, 658, 689, 720, 751, 782, 813, 848, 883, 918, 953, 988, 1023, 1062, 1101, 1140, 1179, 1218, 1257, 1300, 1343, 1386, 1429

Offset: 2

Hugo Pfoertner, Jul 12 2017

For definitions see A103294.

Hugo Pfoertner, Table of n, a(n) for n = 2..10001
Peter Luschny, Are optimal rulers of Wichmann type?
Eric Weisstein's World of Mathematics, Dark Satanic Mills on a Cloudy Day.
Eric Weisstein's World of Mathematics, Sparse Ruler.
Eric Weisstein's World of Mathematics, Wichmann Ruler.
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.

Cf. A004137, A103294, A193802, A193803, A289873.

Table[(n^2 - (Mod[n, 6] - 3)^2)/3 + n, {n, 2, 66}] (* Michael De Vlieger, Jul 14 2017 *)

a(n) = n + (n^2 - (n%6 - 3)^2)/3; \\ Michel Marcus, Jul 14 2017

def A289761(n): return (n+(m:=n%6))*(n-(k:=m-3))//3+k # Chai Wah Wu, Jun 20 2024

a(n) = ( n^2 - (mod(n,6)-3)^2 ) / 3 + n.
Conjectures from Colin Barker, Jul 14 2017: (Start)
G.f.: x^2*(3 + 4*x^5 - 3*x^6) / ((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)).
a(n) = 2*a(n-1) - a(n-2) + a(n-6) - 2*a(n-7) + a(n-8) for n>9.
(End)

A308766 Numbers k such that the minimal mark in a length k sparse ruler is round(sqrt(9 + 12*k)/2) + 1.

Original entry on oeis.org

51, 59, 69, 113, 124, 125, 135, 136, 139, 149, 150, 151, 164, 165, 166, 179, 180, 181, 195, 196, 199, 209, 210, 211

Offset: 1

Ed Pegg Jr, Jun 23 2019

Other sparse rulers in the range length 1 to 213 have round(sqrt(9 + 12*k)/2) minimal marks.
Minimal vertices in k-edge graceful graph = minimal marks in length k sparse ruler.
Minimal marks can be derived from A004137 and using zero-count values in A103300.
Conjecture: Minimal marks k - round(sqrt(9 + 12*k)/2) is always 0 or 1.

P. Luschny, The Perfect Ruler Pyramid (1-101)
P. Luschny, Perfect and Optimal Rulers

Cf. A046693, A004137, A103300, A103294.

A005488 Maximal number of edges in a b^{hat} graceful graph with n nodes.

Original entry on oeis.org

0, 1, 3, 6, 9, 13, 18, 24, 29

Offset: 1

N. J. A. Sloane, Simon Plouffe

A graph with e edges is 'b^{hat} graceful' if its nodes can be labeled with distinct nonnegative integers so that, if each edge is labeled with the absolute difference between the labels of its endpoints, then the e edges have the distinct labels 1, 2, ..., e.
Equivalently, maximum m for which there's a difference basis with respect to m with n elements. A 'difference basis w.r.t. m' is a set of integers such that every integer from 1 to m is a difference between two elements of the set.
Miller's paper gives these lower bounds for the 11 terms from a(9) to a(19): 29,37,45,51,61,70,79,93,101,113,127. (Bermond's paper gives these as exact values, but quotes Miller as their source.)

			a(7)=18: Label the 7 nodes 0,6,9,10,17,22,24 and include all edges except those from 0 to 22, from 0 to 24 and from 17 to 24. {0,6,9,10,17,22,24} is a difference basis w.r.t. 18.

J.-C. Bermond, Graceful graphs, radio antennae and French windmills, pp. 18-37 of R. J. Wilson, editor, Graph Theory and Combinatorics. Pitman, London, 1978.
R. K. Guy, Unsolved Problems in Number Theory, Sect. C10.
J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.

Cf. A004137, A007187, A239308.

Edited by Dean Hickerson, Jan 26 2003

a(9) from J. Stauduhar, May 04 2022

A103296 Number of complete rulers with n segments.

Original entry on oeis.org

1, 1, 3, 10, 38, 175, 885, 5101, 32080, 219569, 1616882, 12747354, 106948772, 950494868

Offset: 0

Peter Luschny, Feb 28 2005

For definitions, references and links related to complete rulers see A103294.

a(10) > 1616740 (contributions from rows of A103294 up to 39). - Hugo Pfoertner, Dec 16 2021

			a(2)=3 counts the complete rulers with 2 segments, {[0,1,2],[0,1,3],[0,2,3]}.

Index entries for sequences related to perfect rulers.

Cf. A103301 (perfect rulers with n segments), A103299 (optimal rulers with n segments).

Cf. A103294, A103295 (complete rulers of length n).

! Link to FORTRAN program given in A103295.

a(n) = Sum_{i=n..A004137(n+1)} T(i, n) where T is the A103294 triangle.

a(9) from Hugo Pfoertner, Mar 17 2005
a(10)-a(11) from Fausto A. C. Cariboni, Mar 03 2022
a(12)-a(13) from Fausto A. C. Cariboni, Mar 08 2022

A103299 Number of optimal rulers with n segments (n>=0).

Original entry on oeis.org

1, 1, 2, 2, 4, 6, 12, 4, 6, 2, 2, 4, 12, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4

Offset: 0

Peter Luschny, Feb 28 2005

For definitions, references and links related to complete rulers see A103294.

			a(5)=6 counts the optimal rulers with 5 segments, {[0,1,6,9,11,13], [0,2,4,7,12,13], [0,1,4,5,11,13], [0,2,8,9,12,13], [0,1,2,6,10,13], [0,3,7,11,12,13]}.

F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
Index entries for sequences related to perfect rulers.

Cf. A103296 (Complete rulers with n segments), A103301 (Perfect rulers with n segments).

a(n) = A103300(A004137(n+1)).

Terms a(20)-a(24) proved by exhaustive search by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 22 2021

A103301 Number of perfect rulers with n segments (n>=0).

Original entry on oeis.org

1, 1, 3, 9, 24, 88, 254, 1064, 1644, 3382, 4156, 8022, 26264, 52012, 25434, 8506, 5632, 6224, 12330, 34224, 108854, 103156, 75992, 86560, 69084

Offset: 0

Peter Luschny, Feb 28 2005

For definitions, references and links related to complete rulers see A103294.

			a(3)=9 counts the perfect rulers with 3 segments, {[0,1,2,4],[0,2,3,4], [0,1,3,4],[0,1,3,5],[0,2,4,5],[0,1,2,5],[0,3,4,5],[0,1,4,6],[0,2,5,6]}.

F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
Index entries for sequences related to perfect rulers.

Cf. A103300, A103297, A103296 (Complete rulers with n segments), A103299 (Optimal rulers with n segments).

a(n) = Sum_{i=A004137(n)+1..A004137(n+1)} A103300(i), n>=1.

Terms a(19)-a(24) found by exhaustive search by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 23 2021

cp's OEIS Frontend

A080060 Erroneous version of A004137 given in the reference.

Views

Author

Keywords

References

A103300 Number of perfect rulers with length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A103294 Triangle T, read by rows: T(n,k) = number of complete rulers with length n and k segments (n >= 0, k >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Sage

Extensions

A046693 Size of smallest subset S of N={0,1,2,...,n} such that S-S=N, where S-S={abs(i-j) | i,j in S}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A289761 Maximum length of a perfect Wichmann ruler with n segments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A308766 Numbers k such that the minimal mark in a length k sparse ruler is round(sqrt(9 + 12*k)/2) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

A005488 Maximal number of edges in a b^{hat} graceful graph with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A103296 Number of complete rulers with n segments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

Formula

Extensions

A103299 Number of optimal rulers with n segments (n>=0).