cp's OEIS Frontend

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.

%I A131849 #33 Feb 02 2025 01:57:59
%S A131849 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,
%T A131849 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,
%U A131849 10,10,10,10,10,10,10,10,10,10,10,10,10,10,10
%N 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.
%C A131849 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.
%H A131849 Michael S. Branicky, <a href="/A131849/b131849.txt">Table of n, a(n) for n = 0..137</a>
%H A131849 Michael S. Branicky, <a href="/A131849/a131849.txt">Table of n, lexicographically earliest subset with size a(n)</a>
%H A131849 Imre Z. Ruzsa and Tom Sanders, <a href="https://arxiv.org/abs/0710.0644">Difference sets and the primes</a>, arXiv:0710.0644 [math.CA], 2007-2010.
%e A131849 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.
%e A131849 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.
%e A131849 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}).
%t A131849 okQ[sub_] := AllTrue[Subsets[sub, {2}], CompositeQ[1+Abs[#[[1]]-#[[2]]]]&];
%t A131849 a[n_] := For[k = n, k >= 0, k--, If[AnyTrue[Subsets[Range[n], {k}], okQ], Return[k]]];
%t A131849 Table[an = a[n]; Print[n, " ", an]; an, {n, 0, 20}] (* _Jean-François Alcover_, Nov 28 2018 *)
%Y A131849 Cf. A000040, A174911.
%K A131849 nonn
%O A131849 0,5
%A A131849 _Jonathan Vos Post_, Oct 04 2007
%E A131849 Edited and extended by _R. J. Mathar_, Jan 15 2008
%E A131849 Edited and extended by _Alois P. Heinz_, Feb 06 2017
%E A131849 a(34) and beyond from _Michael S. Branicky_, Feb 01 2025