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}.

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,2

Comments

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)

Links

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.

Example

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.

Mathematica

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

Crossrefs

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

Sequence in context: A239308 A216256 A309407 * A368910 A196376 A156077

Adjacent sequences: A046690 A046691 A046692 * A046694 A046695 A046696

Keyword

nonn,hard

Author

John W. Layman

Status

approved