Erdős Problem #945

Erdős Problem 945 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/945

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below with TeX syntax corrections for display.

TeX syntax corrected for display; mathematical content unchanged.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/945.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/945.tex.

Let $F(x)$ be the maximal $k$ such that there exist $n+1,\ldots,n+k\leq x$ with $\tau(n+1),\ldots,\tau(n+k)$ all distinct (where $\tau(m)$ counts the divisors of $m$). Estimate $F(x)$. In particular, is it true that\[F(x) \leq (\log x)^{O(1)}?\]In other words, is there a constant $C>0$ such that, for all large $x$, every interval $[x,x+(\log x)^C]$ contains two integers with the same number of divisors? A problem of Erdős and Mirsky [ErMi52], who proved that\[\frac{(\log x)^{1/2}}{\log\log x}\ll F(x) \ll \exp\left(O\left(\frac{(\log x)^{1/2}}{\log\log x}\right)\right).\]Erdős [Er85e] claimed that the lower bound could be improved via their method 'with some more work' to $(\log x)^{1-o(1)}$. Beker has improved the upper bound to\[F(x) \ll \exp\left(O\left((\log x)^{1/3+o(1)}\right)\right).\]Cambie has observed that Cramér's conjecture implies that $F(x) \ll (\log x)^2$, and furthermore if every interval in $[x,2x]$ of length $\gg \log x$ contains a squarefree number (see [208] ) then every interval of length $\gg (\log x)^2$ contains two numbers with the same number of divisors, whence\[F(x) \ll (\log x)^2.\]See [1004] for the analogous problem with the Euler totient function. This problem is discussed in problem B18 of Guy's collection [Gu04]. References [Er85e] Erdős, P., Some problems and results in number theory . Number theory and combinatorics. Japan 1984 (Tokyo, Okayama and Kyoto, 1984) $1985$, 65-87. [ErMi52] Erdős, P. and Mirsky, L., The distribution of values of the divisor function {$d(n)$} . Proc. London Math. Soc. $3$ $1952$, 257--271. [Gu04] Guy, Richard K., Unsolved problems in number theory . $2004$, xviii+437.

FORMAL RESTATEMENT

Let $\tau(m)$ denote the number of positive divisors of $m\in\mathbb{N}$. For $x\ge 1$, define $F(x)$ to be the maximum integer $k\ge 1$ for which there exists an integer $n$ such that \[ n+1, n+2,\dots,n+k \le x \] and the values $\tau(n+1),\dots,\tau(n+k)$ are pairwise distinct. The problem asks to estimate $F(x)$ as $x\to\infty$, and in particular asks whether $F(x)\le (\log x)^{O(1)}$.

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The text gives known bounds of Erdős--Mirsky and subsequent improvements (all treated here as context, not re-proved).

ATTACK PLAN

Proof-track ideas.

• Use upper bounds on the range of $\tau$ on $[1,x]$ to obtain (weak) upper bounds on $F(x)$.
• Try to control collisions $\tau(n+i)=\tau(n+j)$ within short intervals via multiplicative structure.
• For lower bounds, attempt CRT-based constructions to prescribe prime-power divisibility patterns of consecutive integers so as to force distinct divisor counts.

Disproof-track ideas.

• Search computationally for unusually long runs of distinct $\tau$ values to see if growth could exceed any polylog.

WORK

Fast reality check (explicit computation).

I computed $F(x)$ exactly for several $x$ by computing $\tau(n)$ for all $n\le x$ and using a sliding-window algorithm to find the longest block of pairwise distinct values. Exact outputs:

• $F(10)=3$, attained on $[4,6]$ (i.e. $\tau(4)=3,\tau(5)=2,\tau(6)=4$).
• $F(100)=6$, attained on $[76,81]$.
• $F(1000)=7$, first attained on $[270,276]$.
• $F(10000)=9$, first attained on $[3718,3726]$.
• $F(200000)=10$, first attained on $[95499,95508]$.
• $F(10^6)=11$, attained on $[590890,590900]$.

These are sanity checks; they do not indicate the true asymptotic.

Lemma 945.1 (divisor function formula).

If $n=\prod_{i=1}^t p_i^{e_i}$ is the prime factorization of $n\ge 1$ (distinct primes $p_i$ and integers $e_i\ge 1$), then \[ \tau(n)=\prod_{i=1}^t (e_i+1). \]

Proof. A positive divisor $d$ of $n$ has the form $d=\prod_{i=1}^t p_i^{f_i}$ where each exponent $f_i$ satisfies $0\le f_i\le e_i$; conversely every such choice gives a divisor. For each $i$ there are exactly $e_i+1$ choices of $f_i$, and choices across different primes are independent. Thus the total number of divisors is the product $\prod_{i=1}^t (e_i+1)$. $\Box$

Lemma 945.2 (trivial upper bound $\tau(n)\le 2\sqrt{n}$).

For every integer $n\ge 1$, \[ \tau(n)\le 2\lfloor \sqrt{n}\rfloor \le 2\sqrt{n}. \]

Proof. Every divisor $d\le \sqrt{n}$ pairs with a distinct divisor $n/d\ge \sqrt{n}$. There are at most $\lfloor\sqrt{n}\rfloor$ divisors $\le \sqrt{n}$, so counting their pairs gives at most $2\lfloor\sqrt{n}\rfloor$ total divisors. (If $n$ is a perfect square, the divisor $\sqrt{n}$ pairs with itself, so the inequality remains valid.) $\Box$

Lemma 945.3 (odd values of $\tau$).

For $n\ge 1$, $\tau(n)$ is odd if and only if $n$ is a perfect square.

Proof. Write $n=\prod p_i^{e_i}$. By Lemma 945.1, $\tau(n)=\prod (e_i+1)$ is odd if and only if every factor $(e_i+1)$ is odd, i.e. every $e_i$ is even. This is equivalent to $n$ being a perfect square. $\Box$

Corollary 945.4 (very weak global bound on $F(x)$).

For every $x\ge 1$, \[ F(x) \le 2\sqrt{x}. \]

Proof. If $n+1,\dots,n+k\le x$ and $\tau(n+1),\dots,\tau(n+k)$ are pairwise distinct, then these are $k$ distinct positive integers each bounded by $\max_{m\le x}\tau(m)$. By Lemma 945.2, $\max_{m\le x}\tau(m)\le 2\sqrt{x}$. Hence $k\le 2\sqrt{x}$. $\Box$

VERIFICATION

• Lemma 945.2: checked the square case explicitly: if $n=t^2$, then the pairing counts $t$ only once, so $\tau(n)\le 2t-1\le 2t$.
• Corollary 945.4: verified the logic only uses that $\tau(m)$ are positive integers in $[1,2\sqrt{x}]$.
• Computation sanity: for $x=10$, the longest block found is $4..6$ with divisor counts $3,2,4$ distinct; any block of length $4$ inside $\{1,\dots,10\}$ fails (checked by the program).

FINAL

UNRESOLVED (i) Strongest proved partial result: a very weak universal upper bound $F(x)\le 2\sqrt{x}$ (Corollary 945.4), coming from $\tau(n)\le 2\sqrt{n}$. (ii) First gap: prove any polylogarithmic upper bound $F(x)\le (\log x)^C$ (or produce evidence/counterexample showing $F(x)$ can be much larger). (iii) Top 3 next moves:

1. Try to implement (from scratch) a CRT-based lower-bound construction that forces $\tau(n+i)$ to take prescribed, pairwise distinct values while keeping $n+k\le x$.
2. Attempt to prove an upper bound by showing that in any interval of length $L$ there must exist $i\ne j$ with $\tau(n+i)=\tau(n+j)$; reduce to counting solutions of multiplicative equations and apply divisor/sieve bounds.
3. Extend exact computations to larger $x$ (e.g. $10^8$ or higher) and record the structure of the maximizing intervals to see whether they resemble known constructions (e.g. many values of $\tau$ close to each other or highly composite-like behavior).

(iv) Minimal counterexample structure (to a conjectured polylog upper bound): an exceptionally long interval $[n+1,n+k]$ in which each integer has a distinct divisor count, which likely forces unusually rigid and varied prime-exponent patterns across consecutive integers.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $F(x)$ be the maximal $k$ such that there exist $n+1,\ldots,n+k\leq x$ with $\tau(n+1),\ldots,\tau(n+k)$ all distinct (where $\tau(m)$ counts the divisors of $m$). Estimate $F(x)$. In particular, is it true that\[F(x) \leq (\log x)^{O(1)}?\]In other words, is there a constant $C>0$ such that, for all large $x$, every interval $[x,x+(\log x)^C]$ contains two integers with the same number of divisors? A problem of Erdős and Mirsky [ErMi52], who proved that\[\frac{(\log x)^{1/2}}{\log\log x}\ll F(x) \ll \exp\left(O\left(\frac{(\log x)^{1/2}}{\log\log x}\right)\right).\]Erdős [Er85e] claimed that the lower bound could be improved via their method 'with some more work' to $(\log x)^{1-o(1)}$. Beker has improved the upper bound to\[F(x) \ll \exp\left(O\left((\log x)^{1/3+o(1)}\right)\right).\]Cambie has observed that Cramér's conjecture implies that $F(x) \ll (\log x)^2$, and furthermore if every interval in $[x,2x]$ of length $\gg \log x$ contains a squarefree number (see [208] ) then every interval of length $\gg (\log x)^2$ contains two numbers with the same number of divisors, whence\[F(x) \ll (\log x)^2.\]See [1004] for the analogous problem with the Euler totient function. This problem is discussed in problem B18 of Guy's collection [Gu04]. References [Er85e] Erdős, P., Some problems and results in number theory . Number theory and combinatorics. Japan 1984 (Tokyo, Okayama and Kyoto, 1984) $1985$, 65-87. [ErMi52] Erdős, P. and Mirsky, L., The distribution of values of the divisor function {$d(n)$} . Proc. London Math. Soc. $3$ $1952$, 257--271. [Gu04] Guy, Richard K., Unsolved problems in number theory . $2004$, xviii+437.

FORMAL RESTATEMENT

Let $\tau(m)$ denote the number of positive divisors of $m\in\mathbb{N}$. For $x\ge 1$, define $F(x)$ to be the maximum integer $k\ge 1$ for which there exists an integer $n$ such that \[ n+1, n+2,\dots,n+k \le x \] and the values $\tau(n+1),\dots,\tau(n+k)$ are pairwise distinct. The problem asks to estimate $F(x)$ as $x\to\infty$, and in particular asks whether $F(x)\le (\log x)^{O(1)}$.

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The text gives known bounds of Erdős--Mirsky and subsequent improvements (all treated here as context, not re-proved).

ATTACK PLAN

Proof-track ideas.

• Use upper bounds on the range of $\tau$ on $[1,x]$ to obtain (weak) upper bounds on $F(x)$.
• Try to control collisions $\tau(n+i)=\tau(n+j)$ within short intervals via multiplicative structure.
• For lower bounds, attempt CRT-based constructions to prescribe prime-power divisibility patterns of consecutive integers so as to force distinct divisor counts.

Disproof-track ideas.

• Search computationally for unusually long runs of distinct $\tau$ values to see if growth could exceed any polylog.

WORK

Fast reality check (explicit computation).

I computed $F(x)$ exactly for several $x$ by computing $\tau(n)$ for all $n\le x$ and using a sliding-window algorithm to find the longest block of pairwise distinct values. Exact outputs:

• $F(10)=3$, attained on $[4,6]$ (i.e. $\tau(4)=3,\tau(5)=2,\tau(6)=4$).
• $F(100)=6$, attained on $[76,81]$.
• $F(1000)=7$, first attained on $[270,276]$.
• $F(10000)=9$, first attained on $[3718,3726]$.
• $F(200000)=10$, first attained on $[95499,95508]$.
• $F(10^6)=11$, attained on $[590890,590900]$.

These are sanity checks; they do not indicate the true asymptotic.

Lemma 945.1 (divisor function formula).

If $n=\prod_{i=1}^t p_i^{e_i}$ is the prime factorization of $n\ge 1$ (distinct primes $p_i$ and integers $e_i\ge 1$), then \[ \tau(n)=\prod_{i=1}^t (e_i+1). \]

Proof. A positive divisor $d$ of $n$ has the form $d=\prod_{i=1}^t p_i^{f_i}$ where each exponent $f_i$ satisfies $0\le f_i\le e_i$; conversely every such choice gives a divisor. For each $i$ there are exactly $e_i+1$ choices of $f_i$, and choices across different primes are independent. Thus the total number of divisors is the product $\prod_{i=1}^t (e_i+1)$. $\Box$

Lemma 945.2 (trivial upper bound $\tau(n)\le 2\sqrt{n}$).

For every integer $n\ge 1$, \[ \tau(n)\le 2\lfloor \sqrt{n}\rfloor \le 2\sqrt{n}. \]

Proof. Every divisor $d\le \sqrt{n}$ pairs with a distinct divisor $n/d\ge \sqrt{n}$. There are at most $\lfloor\sqrt{n}\rfloor$ divisors $\le \sqrt{n}$, so counting their pairs gives at most $2\lfloor\sqrt{n}\rfloor$ total divisors. (If $n$ is a perfect square, the divisor $\sqrt{n}$ pairs with itself, so the inequality remains valid.) $\Box$

Lemma 945.3 (odd values of $\tau$).

For $n\ge 1$, $\tau(n)$ is odd if and only if $n$ is a perfect square.

Proof. Write $n=\prod p_i^{e_i}$. By Lemma 945.1, $\tau(n)=\prod (e_i+1)$ is odd if and only if every factor $(e_i+1)$ is odd, i.e. every $e_i$ is even. This is equivalent to $n$ being a perfect square. $\Box$

Corollary 945.4 (very weak global bound on $F(x)$).

For every $x\ge 1$, \[ F(x) \le 2\sqrt{x}. \]

Proof. If $n+1,\dots,n+k\le x$ and $\tau(n+1),\dots,\tau(n+k)$ are pairwise distinct, then these are $k$ distinct positive integers each bounded by $\max_{m\le x}\tau(m)$. By Lemma 945.2, $\max_{m\le x}\tau(m)\le 2\sqrt{x}$. Hence $k\le 2\sqrt{x}$. $\Box$

VERIFICATION

• Lemma 945.2: checked the square case explicitly: if $n=t^2$, then the pairing counts $t$ only once, so $\tau(n)\le 2t-1\le 2t$.
• Corollary 945.4: verified the logic only uses that $\tau(m)$ are positive integers in $[1,2\sqrt{x}]$.
• Computation sanity: for $x=10$, the longest block found is $4..6$ with divisor counts $3,2,4$ distinct; any block of length $4$ inside $\{1,\dots,10\}$ fails (checked by the program).

FINAL

UNRESOLVED (i) Strongest proved partial result: a very weak universal upper bound $F(x)\le 2\sqrt{x}$ (Corollary 945.4), coming from $\tau(n)\le 2\sqrt{n}$. (ii) First gap: prove any polylogarithmic upper bound $F(x)\le (\log x)^C$ (or produce evidence/counterexample showing $F(x)$ can be much larger). (iii) Top 3 next moves:

1. Try to implement (from scratch) a CRT-based lower-bound construction that forces $\tau(n+i)$ to take prescribed, pairwise distinct values while keeping $n+k\le x$.
2. Attempt to prove an upper bound by showing that in any interval of length $L$ there must exist $i\ne j$ with $\tau(n+i)=\tau(n+j)$; reduce to counting solutions of multiplicative equations and apply divisor/sieve bounds.
3. Extend exact computations to larger $x$ (e.g. $10^8$ or higher) and record the structure of the maximizing intervals to see whether they resemble known constructions (e.g. many values of $\tau$ close to each other or highly composite-like behavior).

(iv) Minimal counterexample structure (to a conjectured polylog upper bound): an exceptionally long interval $[n+1,n+k]$ in which each integer has a distinct divisor count, which likely forces unusually rigid and varied prime-exponent patterns across consecutive integers.