A131849 Cardinality of largest subset of {1,...,n} such that the difference between any two elements of the subset is never one less than a prime.

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

Offset

0,5

Comments

From the abstract of Ruzsa & Sanders: Suppose that A is a subset of {1,...,N} is such that the difference between any two elements of A is never one less than a prime. We show that |A| = O(N exp(-c(log N)^(1/4))) for some absolute c>0.

Links

Table of n, a(n) for n=0..33.

Imre Z. Ruzsa, Tom Sanders, Difference sets and the primes, arXiv:0710.0644 [math.CA], 2007-2010.

Example

a(4) = 2 because {1,4} is the unique subset of {1,2,3,4} with the desired property that 4-1 = 3 is not 1 less than a prime.
a(9) = 3 because {1,4,9} is the unique subset of {1,2,3,4,5,6,7,8,9} with the desired property that 4-1 = 3 is not 1 less than a prime and 9-1 = 8 is not 1 less than a prime and 9-4 = 5 is not 1 less than a prime.
For n=9, 10 and 11, the cardinality is limited to 3 (the subset {1,4,9}). For 12 <= n <= 17, the cardinality is limited to 4 (the subset {1,4,9,12}).

Mathematica

okQ[sub_] := AllTrue[Subsets[sub, {2}], CompositeQ[1+Abs[#[[1]]-#[[2]]]]&];
a[n_] := For[k = n, k >= 0, k--, If[AnyTrue[Subsets[Range[n], {k}], okQ], Return[k]]];
Table[an = a[n]; Print[n, " ", an]; an, {n, 0, 20}] (* Jean-François Alcover, Nov 28 2018 *)

Crossrefs

Cf. A000040, A174911.

Sequence in context: A204591 A279220 A114575 * A362344 A244479 A090735

Adjacent sequences: A131846 A131847 A131848 * A131850 A131851 A131852

Keyword

more,nonn

Author

Jonathan Vos Post, Oct 04 2007

Extensions

Edited and extended by R. J. Mathar, Jan 15 2008

Edited and extended by Alois P. Heinz, Feb 06 2017

Status

approved