[seqfan] Re: Largest subsets of {1, ..., n} such that no difference is ...

[hv at crypt.org]

Given that by definition these sequences can as well be fully described
by the minimum span of an n-element set with the required properties,
it feels to me like it would be more obvious and more efficient to
represent them that way.

Thus A100719 could be represented by [1, 3, 6, 8, 11, 13, 16, 18, ...],
ie A210570. Sadly there is currently no cross-reference between these,
and there is some divergence of other references.

Hugo

Zach DeStefano <zachdestefano at gmail.com> wrote:
:It appears that (a) already has a sequence: A100719.
:As for (b), (c), and (d), here are the first 40 values. They don't match
:any existing sequence.
:b: 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
:4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, ...
:c: 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6,
:7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, ...
:d: 1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
:4, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, ...
:I would be happy to provide b-files with more terms.
:(c) empirically seems to be following a similar mundane pattern to the sum
:case with maximal subsets generally just following the form: all 2k + 4 <=
:n.
:
:On Mon, May 15, 2023 at 5:52 PM Zach DeStefano <zachdestefano at gmail.com>
:wrote:
:
:> About two years ago, I had thought about a similar problem, namely that of
:> maximal subsets of {1,...n} where SUMs of pairs avoid squares, determined
:> lower and upper bounds on the size of the subset, and computed the maximum
:> sized subsets up to n = 100. My results are here:
:> http://www.mathmasterzach.com/Math/SquarelessSets.html. The results I got
:> were all very close to the lower bound and would appreciate it if anyone
:> could improve the upper bound.
:>
:> I had also thought about the primes, but the results there were less
:> interesting (bet that's the only time you will hear that about the primes).
:> In general, the optimal subsets with sums avoiding primes for the values of
:> n I tested just consisted of all even numbers <= n.
:>
:> I can easily adapt my code to handle differences and contribute terms here.
:>
:> Also, is there a link to a recording of this talk online?
:>
:> - Zach
:>
:> On Mon, May 15, 2023 at 4:17 PM Neil Sloane <njasloane at gmail.com> wrote:
:>
:>> Dear Seqfans, A recent talk by Ben Green studies the density of, for
:>> example, the largest subset of {1..n} such that no difference is:
:>> (a) a square, (b) a prime - 1, (c) a prime, or (d) a prime + 1.
:>>
:>> So let's look at the actual sizes, not the density.
:>>
:>> I started off with (c), so let a(n) = max subset of {1..n} such that no
:>> difference is a prime.  For n=1..11 I get
:>> 1,2,2,2,2,2,2,2,3,3,4
:>> which seems not to be in the OEIS.
:>> The examples where a(n) increases are {1}, {1,2}, {1,5,9}, {1,2,10,11}.
:>> Could someone check?
:>>
:>> And what about (a), (b), and (d)?
:>>
:>> Best regards
:>> Neil
:>>
:>> Neil J. A. Sloane, Chairman, OEIS Foundation.
:>> Also Visiting Scientist, Math. Dept., Rutgers University,
:>> Email: njasloane at gmail.com
:>>
:>> --
:>> Seqfan Mailing list - http://list.seqfan.eu/
:>>
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/