A103294 -id:A103294 - cp's OEIS frontend

A308999 Irregular triangle T(n,k) read by rows: Lexicographically smallest marks on "perfect rulers" (as defined in A103294) of length n.

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

Offset: 0

Bob Selcoe, Jul 04 2019

Refer to A103294 for additional definitions, references and links.
All rulers (rows) start with mark 0 and end with mark n.
Row lengths are A103298(n) + 1.

			Triangle starts:
  0;
  0,  1;
  0,  1,  2;
  0,  1,  3;
  0,  1,  2,  4;
  0,  1,  2,  5;
  0,  1,  4,  6;
  0,  1,  2,  3,  7;
  0,  1,  2,  5,  8;
  0,  1,  2,  6,  9;
  0,  1,  2,  3,  6, 10;
  0,  1,  2,  3,  7, 11;
  0,  1,  2,  3,  8, 12;
  0,  1,  2,  6, 10, 13;
  0,  1,  2,  3,  4,  9, 14;
  0,  1,  2,  3,  4, 10, 15;
  0,  1,  2,  3,  8, 12, 16;

Peter Luschny, The perfect ruler pyramid
Peter Luschny, Perfect rulers

Cf. A103294, A103298.

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 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 CompleteRuler(L, S) :
    return list(filter(isComplete, Ruler(L, S)))
def PerfectRulers(L) :
    for i in (0..L) :
        R = CompleteRuler(L, i)
        if R: return R
    return []
def A308999list(L):
    for n in (0..L):
        print(PerfectRulers(n)[-1])
A308999list(16) # Peter Luschny, Aug 21 2019

A103295 Number of complete rulers with length n.

Original entry on oeis.org

1, 1, 1, 3, 4, 9, 17, 33, 63, 128, 248, 495, 988, 1969, 3911, 7857, 15635, 31304, 62732, 125501, 250793, 503203, 1006339, 2014992, 4035985, 8080448, 16169267, 32397761, 64826967, 129774838, 259822143, 520063531, 1040616486, 2083345793, 4168640894, 8342197304, 16694070805, 33404706520, 66832674546, 133736345590

Offset: 0

Peter Luschny, Feb 28 2005

nonn

For definitions, references and links related to complete rulers see A103294.
Also the number of compositions of n whose consecutive subsequence-sums cover an initial interval of the positive integers. For example, (2,3,1) is such a composition because (1), (2), (3), (3,1), (2,3), and (2,3,1) are subsequences with sums covering {1..6}. - Gus Wiseman, May 17 2019
a(n) ~ c*2^n, where 0.2427 < c < 0.2459. - Fei Peng, Oct 17 2019

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

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..49
Scott Harvey-Arnold, Steven J. Miller, and Fei Peng, Distribution of missing differences in diffsets, arXiv:2001.08931 [math.CO], 2020.
Peter Luschny, Perfect rulers
Hugo Pfoertner, Count complete rulers of given length. FORTRAN program.
Index entries for sequences related to perfect rulers.
Gus Wiseman, Illustration of A103295.

Cf. A103300 (Perfect rulers with length n). Main diagonal of A349976.

Cf. A000079, A126796, A143823, A169942, A325676, A325677, A325683, A325684, A325685.

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

a(n) = Sum_{i=0..n} A103294(n, i) = Sum_{i=A103298(n)..n} A103294(n, i).

a(30)-a(36) from Hugo Pfoertner, Mar 17 2005
a(37)-a(38) from Hugo Pfoertner, Dec 10 2021
a(39) from Hugo Pfoertner, Dec 16 2021

A103300 Number of perfect rulers with length n.

Original entry on oeis.org

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.

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

Original entry on oeis.org

0, 1, 3, 6, 9, 13, 17, 23, 29, 36, 43, 50, 58, 68, 79, 90, 101, 112, 123, 138, 153, 168, 183, 198, 213, 232

Offset: 1

N. J. A. Sloane, Simon Plouffe

A graph with e edges is "graceful" if its nodes can be labeled with distinct integers in {0,1,...,e} 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 restricted 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. A "restricted" difference basis is one in which the smallest element is 0 and the largest is m.
a(n) is also the length of an optimal ruler with n marks. For definitions see A103294. For example, a(6)=13 is the length of the optimal rulers with 6 marks, {[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]}. Also n = 1 + A103298(a(n)). - Peter Luschny, Feb 28 2005
If the conjecture is true that an optimal ruler with more than 12 segments is a Wichmann ruler then the sequence continues 232, 251, 270, 289, 308, 327, ... - Peter Luschny, Oct 09 2011 [updated to take the verifications of Robison into account, Oct 01 2015]

			a(7)=17: Label the 7 nodes 0,1,8,11,13,15,17 and include all edges except those from 8 to 15, from 13 to 15, from 13 to 17 and from 15 to 17. {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. 17.
a(21)=153 because there exists a complete ruler (i.e., one that can measure every distance between 1 and 153) with marks [0,1,2,3,7,14,21,28,43,58,73,88,103,118,126,134,142,150,151,152,153] and no complete ruler of greater length with the same number of marks can be found. This ruler is of the type described by B. Wichmann and it is conjectured by _Peter Luschny_ that it is impossible to improve upon Wichmann's construction for finding optimal rulers of bigger lengths.

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, Modular difference sets and error correcting codes. in: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, chapter C10, (2004), 181-183.
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).

D. Beutner and H. Harborth, Graceful labelings of Nearly Complete Graphs, Results Math. 41 (2002) 34-39.
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
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.
L. Egidi and G. Manzini, Spaced seeds design using perfect rulers, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89-115.
P. Erdős and R. Freud, On sums of a Sidon-sequence, J. Number Theory 38 (1991), 196-205.
P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.
S. Lou and Q. Yao, A Chebyshev's type of prime number theorem in a short interval II, Hardy-Ramanujan J. 15 (1992), 1-33.
Peter Luschny, Perfect Rulers.
Peter Luschny, Wichmann Rulers.
Klaus Nagel, Evaluation of perfect rulers C program.
O. Pikhurko, Dense edge-magic graphs and thin additive bases, Discrete Math. 306 (2006), 2097-2107.
O. Pikhurko and T. Schoen, Integer Sets Having the Maximum Number of Distinct Differences, Integers: Electronic journal of combinatorial number theory 7 (2007).
I. Redéi and A. Rényi, On the representation of integers 1, 2, ..., n by differences, Mat. Sbornik 24 (1949), 385-389 (Russian).
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.
J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377-85.
David Singmaster, David Fielker, N. J. A. Sloane, Correspondence, August 1979.
M. Wald & N. J. A. Sloane, Correspondence and Attachment, 1987.
Eric Weisstein's World of Mathematics, Graceful Graph.
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.
Al Zimmermann's Programming Contests, Graceful Graphs, September - December 2013.

Cf. A046693, A103294, A103298, A103299, A103296, A102508, A212661.
A080060 is an erroneous version of the sequence, given in Bermond's paper. Cf. A005488.
A289761 provides the conjectured continuation.

See Klaus Nagel link.
(Parallel C++) See A. Robison link.

a(n) = n*(n-1)/2 - A212661(n). - Kellen Myers, Jun 06 2016

Miller's paper gives these lower bounds for the 8 terms from a(15) to a(22): 79, 90, 101, 112, 123, 138, 153, 168.
Edited by Dean Hickerson, Jan 26 2003
Terms 79,...,123 from Peter Luschny, Feb 28 2005, with verification by an independent program written by Klaus Nagel. Using this program Hugo Pfoertner found the next term, 138.
Using this program Hugo Pfoertner found further evidence for the conjectured term a(21)=153, Feb 23 2005
Terms a(21) .. a(24) proved by exhaustive search by Arch D. Robison, Hugo Pfoertner, Nov 01 2013
Term a(25) proved by exhaustive search by Arch D. Robison, Peter Luschny, Jan 14 2014
Term a(26) proved by exhaustive search by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 22 2021

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)

A103298 Number of segments of a perfect ruler with length n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 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, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14

Offset: 0

Peter Luschny, Feb 28 2005

nonn

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

			a(11)=5 means that a perfect ruler with length 11 has 5 segments.

F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Table of n, a(n) for n = 0..244
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. A046693, A103297.

a(n) = A046693(n) - 1.

Extended using A046693 terms by Vaclav Kotesovec, Oct 20 2019

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.

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

A308999 Irregular triangle T(n,k) read by rows: Lexicographically smallest marks on "perfect rulers" (as defined in A103294) of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

A103295 Number of complete rulers with length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A103300 Number of perfect rulers with length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A103298 Number of segments of a perfect ruler with length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

A103296 Number of complete rulers with n segments.

Views

Author

Keywords

Comments

Examples