|
|
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.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|