OFFSET
1,4
COMMENTS
If n = q_1^k_1 * ... * q_r^k_r (where q_1 < ... < q_r are distinct primes) then the maximum is achieved by, for some 1 <= j <= r, the set of all integers in [1, n] that are a multiple of at least one of {2*q_1, ..., 2*q_j, q_1*...*q_j}. This result was conjectured by Erdős (1992), and proved by Ahlswede and Khachatrian (1996).
A graph-theoretic framing of the construction is as follows: Start with the vertex set {1, 2, ..., n}. Draw an edge between two vertices a and b if and only if they share at least one prime factor. In this setup, the problem can be phrased as: "Find a maximum clique containing n in the gcd-graph" and a(n) is the size of that clique. The maximum clique is not uniquely determined, for example 4301 has two maximum cliques of length 391 (cf. A387699). - Peter Luschny, Sep 08 2025
LINKS
David Radcliffe, Table of n, a(n) for n = 1..10000
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.
Erdős problems database contributors, Erdős problem database, see no. 534.
EXAMPLE
For n = 15 the graph-theoretic construction is: Vertices: 1, 2, 3,..., 15. Edges: connect numbers that share a factor > 1. For instance, 9 and 15 are connected (gcd=3), but 8 and 15 are not (gcd=1). The maximum clique containing 15 is {3, 6, 9, 12, 15}. This clique has size 5, so a(15) = 5. (See the illustration in the links.) - Peter Luschny, Sep 07 2025
MATHEMATICA
(* From Peter Luschny, Sep 08 2025: (Start) *)
A387543[n_Integer?Positive] := Module[
{primes, q = 1, ret = 1, cp, kSet, us, i, j, sub, term},
If[n == 1, Return[1]];
primes = FactorInteger[n][[All, 1]];
Do[ q *= primes[[i]];
cp = Take[primes, i];
kSet = Union[2 * cp, {q}];
us = 0;
Do[ sub = Subsets[kSet, {j}];
term = Sum[Floor[(n - 1) / Apply[LCM, s]], {s, sub}];
us += (-1)^(j - 1) * term;
, {j, 1, Length[kSet]}
];
ret = Max[ret, 1 + us];
, {i, 1, Length[primes]}
]; ret ]
Table[A387543[n], {n, 1, 75}] (* (End) *)
PROG
(Python)
from sympy import primefactors
def a(n):
if n == 1:
return 1
if n % 2 == 0:
return n // 2
m = (n - 1) // 2
pf = primefactors(n)
p = q = pf[0]
s = m // p
best = n // p
for p in pf[1:]:
s += (m - s) // p
q *= p
best = max(best, s - m // q + n // q)
return best # David Radcliffe, Sep 07 2025
CROSSREFS
KEYWORD
nonn
AUTHOR
David Radcliffe, Sep 01 2025
STATUS
approved