OFFSET
1,1
COMMENTS
We define the set V = {1, 2, 3, ..., n} as a graph, where the numbers represent the vertices, and edges connect numbers that share a common prime factor. We refer to this graph as the gcd-graph of {1, ..., n}. A clique in this graph is a subset of V in which any two numbers share at least one prime factor. We are particularly interested in 'maximum cliques', which are the largest cliques by size that contain n. The sizes of these maximum cliques are documented in A387543. The gcd-graph of n may have multiple maximum cliques of equal size containing n, but no larger one. Numbers that have more than one such maximum clique are the subject of the present sequence.
LINKS
Peter Luschny, Table of n, a(n) for n = 1..3000
Rudolf Ahlswede and Levon H. Khachatrian, Sets of integers with pairwise common divisor and a factor from a specified set of primes, Acta Arith. (1996), 259-276.
Thomas Bloom, Problem 534, Erdős Problems.
Peter Luschny, Python implementation.
Wikipedia, Clique problem.
EXAMPLE
Proof that 4301 is a term in this sequence: Starting point is the prime factorization of 4301 = 11 * 17 * 23. The following construction outlines the basic structure of a (now proved) conjecture by Erdős (see links).
Set S0 = {m <= 4301 : 11 | m}, size = 4301/11 = 391.
Set S1 = {m <= 4301 : 22 | m}, size = 195.
Set S2 = {m <= 4301 : 34 | m}, size = 126.
Set S3 = {m <= 4301 : 46 | m}, size = 93.
Set T0 = S1 U S2 U S3 U {4301}, size = 391.
S0 != T0 because 11 is in S0 but not in T0, both S0 and T0 have size 391 and are a clique (every two elements share a prime factor), and no larger clique that contains 4301 exists.
MATHEMATICA
maximumClique[n_Integer?Positive] := Module[
{primes, q = 1, l, counts, us, cp, kSet, j, sub, term},
primes = FactorInteger[n][[All, 1]];
If[primes === {}, Return[0]];
counts = Table[
q *= primes[[i]];
cp = Take[primes, i];
kSet = Union[2*cp, {q}];
us = Sum[
Sum[Floor[(n - 1)/LCM @@ s],
{s, Subsets[kSet, {j}]}] * (-1)^(j - 1),
{j, 1, Length[kSet]}];
1 + us, {i, Length[primes]}];
With[{maxL = Max[counts]},
If[Count[counts, maxL] > 1, n, 0]]]
A387699List[start_, len_] := Select[
ParallelTable[maximumClique[n],
{n, start, start + len - 1}], # =!= 0 & ]
A387699List[1, 10000000]
PROG
(Python) # See links.
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Luschny, Sep 08 2025
STATUS
approved