OFFSET
1,2
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}. An Erdős clique in this graph is a subset of V that contains n and in which any two numbers share at least one prime factor. Such a clique is a 'maximum clique' if it is a largest clique by size (this does not imply uniqueness). The definitions are a graph-theoretic reformulation of Erdős Problem 534 (cf. links).
LINKS
Peter Luschny, Table for row n = 1..100.
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, Illustrating the maximum clique for n = 15.
Peter Luschny, The Shared Prime Factor Graph, an interactive demo.
Wikipedia, Clique problem.
FORMULA
The length of row n is A387543(n).
EXAMPLE
Triangle begins:
[1] {1}
[2] {2}
[3] {3}
[4] {2, 4}
[5] {5}
[6] {2, 4, 6}
[7] {7}
[8] {2, 4, 6, 8}
[9] {3, 6, 9}
[10] {2, 4, 6, 8, 10}
.
For n = 4301 two maximum cliques exist:
C1 = {m <= 4301 : 11 | m}, size = 4301/11 = 391.
C2 = {m <= 4301 : 22 | m or 34 | m or 46 | m} U {4301}, size = 391.
So row 4301 of the triangle is C1 = {11, 22, ..., 4301}.
MAPLE
(* Designed only for 1 <= n <= 4300. *)
maximumClique := proc(n) local p, q, s, r, t, i;
q := 1; s := {n}; r := {n}; t := {};
for p in NumberTheory:-PrimeFactors(n) do
q := q * p;
s := s union {seq(i, i = 2*p..n-1, 2*p)};
t := s union {seq(i, i = q..n-1, q)};
if nops(t) > nops(r) then r := t fi;
od; r end:
for n from 1 to 20 do maximumClique(n) od;
MATHEMATICA
(* Designed only for 1 <= n <= 4300. *)
maximumClique[n_Integer?Positive] := Module[
{q = 1, s = {n}, r = {n}, t, primes},
primes = FactorInteger[n][[All, 1]];
Do[ q *= p;
s = Union[s, Range[2*p, n - 1, 2*p]];
t = Union[s, Range[q, n - 1, q]];
If[Length[t] > Length[r], r = t],
{p, primes}]; r ];
Table[maximumClique[n], {n, 1, 21}] // Flatten
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Peter Luschny, Sep 10 2025
STATUS
approved