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

Chai Wah Wu, Table of n, a(n) for n = 0..387 (terms 0..137 from Michael S. Branicky)

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.

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

Prog

(Python)
from networkx import empty_graph, find_cliques
from itertools import combinations
from sympy import isprime
def A131849(n):
    if n == 0: return 0
    v = list(range(1, n+1))
    G = empty_graph(v)
    G.add_edges_from((a, b) for a, b in combinations(v, 2) if not isprime(abs(a-b)+1))
    return max(len(c) for c in find_cliques(G)) # Chai Wah Wu, Jan 09 2026

Crossrefs

Cf. A000040, A174911.

Sequence in context: A204591 A279220 A114575 * A362344 A244479 A090735

Adjacent sequences: A131846 A131847 A131848 * A131850 A131851 A131852

Keyword

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

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

Status

approved