/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtilpublicimportFormalConjectures.ErdosProblems.«711»
[ErPo80] Erdős, P. and Pomerance, C., Matching the natural numbers up to $n$ with distinct
multiples in another interval. Nederl. Akad. Wetensch. Indag. Math. 42 (1980), 147-161.
PDF
$f(n)$: the least $L$ such that the open interval $(n,n+L)$ contains distinct integers
$a_1,\ldots,a_n$ with $k \mid a_k$ for all $1 \leq k \leq n$. This is
Erdos711.HasDivisibleDistinctTuple n n L.
The set of such $L$ is nonempty for every $n$ (take $a_k = k(n+1)$ and $L = n^2+1$), so sInf
is the true minimum. For $n = 0$ there is nothing to choose and $f(0) = 0$.
The example $11, 22, 21, 16, 15, 12, 14, 24, 18, 20$ of [ErPo80, p. 147] shows $f(10) \leq 15$.
[ErPo80] use the interval $(n, f(n)]$, where this reads $f(10) = 24$.
Let $f(n)$ be minimal such that in $(n,n+f(n))$ there exist distinct integers $a_1,\ldots,a_n$
such that $k\mid a_k$ for all $1\leq k\leq n$. Obtain an asymptotic formula for $f(n)$.