Integers not overtaken by m + τ(m)

Find n > 24 such that m + τ(m) ≤ n + 2 for every m < n, where τ counts divisors, or prove that none exists.

shoal State the problem, from Erdős Problems da699cb · 2周前历史

43 行 · 3.4 KB 原始文件永久链接历史

1	# Integers not overtaken by m + τ(m)
2
3	Add to each integer $m$ its number of divisors $\tau(m)$. Erdős and Selfridge asked whether some $n>24$ is barely reached by these values, in the sense that no $m<n$ gets more than two past $n$. The case $n=24$ works, and exhaustive searches have found nothing else; a single example would settle the problem, which makes it a natural target for computation.
4
5	## Problem
6
7	Let $\tau(m)$ denote the number of positive divisors of $m$. Is there an integer $n>24$ such that
8
9	$$
10	\max_{m<n}\,\bigl(m+\tau(m)\bigr)\le n+2\,?
11	$$
12
13	The bound $n+2$ cannot be lowered, since $\max\bigl(\tau(n-1)+n-1,\ \tau(n-2)+n-2\bigr)\ge n+2$ for every $n\ge 7$.
14
15	Erdős offered £25 for an example with $n>24$ (the source lists this as \$44, converting at 1992 exchange rates).
16
17	## Background
18
19	The question is due to Erdős and Selfridge and appears in Erdős's 1979 article "Some unconventional problems in number theory". Erdős considered it "extremely doubtful" that there are infinitely many such $n$, and suggested that in fact $\max_{m<n}(m+\tau(m))-n\to\infty$. On the other hand he thought it "certain" that for each fixed $k$ there are infinitely many $n$ with $\max_{n-k<m<n}(m+\tau(m))\le n+2$, a statement that follows from Schinzel's Hypothesis H but seems out of reach. When he offered the prize he wrote that he was being "rather stingy".
20
21	## What is known
22
23	- Searches. The OEIS entry A087280, which lists the solutions $1,2,3,4,5,6,8,10,12,24$, records that there are no further terms up to $10^{22}$ (exhaustive search by Veljjanoski, 2026, with code on GitHub).
24	- Kernel-checked certificates. Mian and Siddique (2026) gave a Lean 4 proof, checked end to end by the proof kernel, that no solution exists with $24<n\le 10^9$; the problem's forum reports kernel-checked extensions to $10^{13}$.
25	- Structure of candidates. Contributors on the forum have shown that any further solution must be a multiple of $2520$ lying in a small number of residue classes, which is what makes searches at this scale feasible.
26	- Claims. A claimed proof that no solution exists, posted in January 2026, treated the case of large $n$ as an axiom in its Lean formalisation and is not accepted.
27
28	## What would count as progress
29
30	- An integer $n>24$ with the required property, which anyone can confirm by computing $\tau(m)$ for $m<n$ (or checking a certificate of the maximum).
31	- A proof that no such $n$ exists, or a proof that there are only finitely many.
32	- Kernel-checked certificates covering larger ranges, reusing the published approach.
33	- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/647.lean).
34
35	## References
36
37	1. P. Erdős, Some unconventional problems in number theory, Math. Mag. 52 (1979), 67–70. [doi:10.1080/0025570X.1979.11976756](https://doi.org/10.1080/0025570X.1979.11976756)
38	2. I. Mian and S. Siddique, A kernel-checked exclusion certificate for Erdős problem 647 (2026). [arXiv:2608.17880](https://arxiv.org/abs/2608.17880)
39	3. OEIS Foundation, Solutions $k$ of $\max(m+d(m))=k+2$ for $m<k$, sequence A087280. [oeis.org/A087280](https://oeis.org/A087280)
40
41	## Source
42
43	Imported from [Erdős Problems 647](https://www.erdosproblems.com/647), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.