Skip to content
Home
Problems
Updates
Vela Mathematics Program
/
Problems
/
539
Search or jump
⌘K
Overview
Problem ledger
Claims
Proposed changes
Commits
Reproduce
Problem
erdos:539
For
∣
A
∣
=
n
|A| = n
, how small can the cofactor set
Q
(
A
)
=
{
a
/
gcd
(
a
,
b
)
:
a
,
b
∈
A
}
Q(A) = \{a / \gcd(a,b) : a, b \in A\}
be? The answer is
h
(
n
)
=
n
1
/
2
+
o
(
1
)
h(n) = n^{1/2 + o(1)}
: a new upper bound
h
(
n
)
≤
n
1
/
2
exp
(
O
(
log
n
)
)
h(n) \le n^{1/2} \exp(O(\sqrt{\log n}))
matches the classical lower bound.
Open Current State
Declared status
open
Formalization
formalized
Subjects
number theory
OEIS
possible
Sources
source:erdos-ai-contributions-wiki
·
source:erdos-problems
·
source:formal-conjectures
·
source:gpt-erdos
·
source:vibemathed
Statement
www.erdosproblems.com
Matching claims
0
No direct claims
This problem has no directly related claim record.
Browse this Repository’s Claims