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, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 0

Author

Jonathan Vos Post, Oct 04 2007

Keywords

• nonn

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.

Examples

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

Links

• Michael S. Branicky, Table of n, a(n) for n = 0..137
• Michael S. Branicky, Table of n, lexicographically earliest subset with size a(n)
• Imre Z. Ruzsa and Tom Sanders, Difference sets and the primes, arXiv:0710.0644 [math.CA], 2007-2010.

Crossrefs

Cf. A000040, A174911.

Programs

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 *)

Extensions

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

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

a(34) and beyond from Michael S. Branicky, Feb 01 2025