ERDŐS/DAILY ▸

← back to the ledger

ERDőS #945 · PARTIAL

Erdős problem #945 — live check, exact computation, and a power-free reduction

Access and computation date: 2026-07-28 UTC.

Claim labels

Every mathematical assertion below is labelled as requested:

Status facts and bibliographic facts are explicitly attributed to their sources rather than assigned a mathematical label. No category-(c) assertion is used in a conclusion.

0. Mandatory live-page check

I loaded the live problem page, its live LaTeX source, and the discussion thread through the Bright Data browser route. This was a rendered-page check, not a direct datacenter curl.

The live page reported:

Thus none of the mandatory stop conditions applied.

Live statement

The page begins with this short verbatim excerpt:

“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.”

Here \(\tau(m)\) counts the positive divisors of \(m\). The exact mathematical remainder of the live statement asks to estimate \(F(x)\), and in particular whether

\[ F(x)\leq(\log x)^{O(1)}. \]

Equivalently, it asks whether some constant \(C>0\) makes every interval \([x,x+(\log x)^C]\), for all sufficiently large \(x\), contain two integers having the same divisor count. This is a formula-preserving restatement of the live LaTeX source.

Live known-results block

The page attributes the following results:

\[ \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). \]

\[ F(x)\ll\exp\!\left(O((\log x)^{1/3+o(1)})\right). \]

The page references are:

All three live comments

  1. abeker, 10:09 on 03 Oct 2025. He announced a short note giving the upper bound \(\exp((\log x)^{1/3+o(1)})\) and said that pushing it further appeared to need new ideas.
  2. Woett, 15:36 on 04 Oct 2025. He noted one equality/inequality typo, observed that the valuation bound for a “frequent” prime can be reduced using \(p>|I|/6\), and suggested an Erdős–Kac-in-short-intervals refinement for the number of prime factors. He explicitly observed that these changes appear to affect only lower-order terms or constants.
  3. abeker, 19:39 on 08 Oct 2025. He accepted the typo correction, agreed that the first refinement does not change the shape of the bound, and identified control of the large prime factors as the continuing difficulty.

The page warns that comments are not verified. I use them only to identify the current line of attack and its stated obstruction.

1. Primary-source literature check

I searched exact phrases from the statement, the exact title “Consecutive integers with different numbers of divisors,” combinations of “divisor function / consecutive / all distinct,” and arXiv/DOI-targeted variants. The specific primary sources found were the following.

  1. The Erdős–Mirsky paper exists; its DOI is 10.1112/plms/s3-2.1.257. Section 11 proves its Theorem V about \(F(x)\), and the introduction gives the upper bound through the number \(D(x)\) of divisor-function values. This verifies that the cited 1952 paper really contains this problem and these bounds.
  2. The 1985 Erdős paper exists. On its printed page 66, Erdős writes that “with some more work” the method would give \(F(x)>c(\log x)^{1-\varepsilon}\), while the method could not reach \(c\log x/\log\log x\). This directly supports the live page's lower-bound attribution.
  3. Adrian Beker's linked three-page note, dated 3 October 2025, exists and was read in full. Its stated Theorem 1.1 is

\[ F(x)\leq \exp\!\bigl(O((\log x)^{1/3}\log\log x)\bigr). \] Its concluding refinement is \[ F(x)\leq \exp\!\bigl(O((\log x\log\log x)^{1/3})\bigr), \] which is consistent with the live page's shorter \(\exp(O((\log x)^{1/3+o(1)}))\) formulation.

  1. For the reduction in Section 2, I checked the author-hosted primary survey by Filaseta, Graham, and Trifonov, Starting with gaps between \(k\)-free numbers, DOI 10.1142/S1793042115400199. Its Theorem 3.2 records Trifonov's fixed-\(k\) worst-case gap bound \(O_k(x^{1/(2k+1)}\log x)\). I also checked Pandey's 2024 primary preprint Squarefree numbers in short intervals, which improves the squarefree exponent below \(1/5\) but remains a power of \(x\), not a polylogarithm.

The exact-title and exact-statement searches did not locate another paper specifically improving \(F(x)\) beyond Beker's note. This is a search report, not a proof that no unindexed literature exists. The live page itself gives the same warning.

The page links OEIS A048892, which lists starts of runs. I did not use those entries as proof or as input to the computation. The independently recomputed starts below agree through \(k=13\).

For download identity, the source files inspected had SHA-256 hashes:

ErMi52 PDF:  7ac131edebf35cac366f67e466b2268e98ab44fb21f2ba198eb3a3b3c53e63e5
Er85e PDF:   8343193ea03e84f94b095e08b136be3086a35524d2adb13d3c739c27681988c5
Beker PDF:   0ed8c51c8b5c35ba9f0071f9c2c812e26e55693f70884841e3cf361cb512a04c

2. An elementary reduction to worst-case gaps between power-free integers

This section gives a clean sufficient lemma for the desired polylogarithmic bound and pinpoints the missing uniform input.

Fix an integer \(r\geq2\).

\[ V_r(x)=\#\{m\leq x:\text{ every prime divisor of }m\text{ is at most }r\}. \] Thus \(V_r(x)\) counts the \(r\)-smooth positive integers up to \(x\), with \(1\) included.

Lemma

Claim (a). For every \(x\geq1\) and fixed \(r\geq2\),

\[ \boxed{F(x)\leq (V_r(x)+1)G_r(x)-1.} \]

Proof. Write \(n=\prod p^{a_p}\). If \(n\) is \(r\)-free, then every \(a_p+1\leq r\). Hence

\[ \tau(n)=\prod_p(a_p+1) \]

has no prime divisor exceeding \(r\). Also \(\tau(n)\leq n\leq x\), so \(\tau(n)\) is one of the \(V_r(x)\) possible \(r\)-smooth values.

Now take any block of \((V_r(x)+1)G_r(x)\) consecutive integers in \([1,x]\). Partition it into \(V_r(x)+1\) disjoint consecutive blocks of length \(G_r(x)\). Each sub-block contains an \(r\)-free integer. Their \(V_r(x)+1\) divisor counts lie in a set of size \(V_r(x)\), so two are equal. Therefore no divisor-count-injective block can be that long. ∎

Size of the finite value set

Claim (a). If \(\pi(r)\) is the number of primes at most \(r\), then

\[ V_r(x) \leq \prod_{\substack{q\leq r\\q\ {\rm prime}}} \left(1+\left\lfloor\frac{\log x}{\log q}\right\rfloor\right) =O_r((\log x)^{\pi(r)}). \]

Indeed, an \(r\)-smooth \(m\leq x\) has a unique exponent vector \((v_q(m))_{q\leq r}\), and each coordinate is at most \(\lfloor\log x/\log q\rfloor\).

Consequently:

Claim (a). If, for even one fixed \(r\), a uniform worst-case estimate

\[ G_r(x)\ll(\log x)^A \]

were proved, then

\[ F(x)\ll_r(\log x)^{A+\pi(r)}, \]

which would answer Erdős problem #945 affirmatively.

For \(r=2\), \(V_2(x)=1+\lfloor\log_2x\rfloor\). Thus a uniform squarefree-gap bound \(G_2(x)\ll\log x\) gives \(F(x)\ll(\log x)^2\), recovering Cambie's implication from the live page.

What known \(r\)-free gap machinery gives

Claim (b), modulo Trifonov's theorem. The fixed-\(r\) result

\[ G_r(x)\ll_r x^{1/(2r+1)}\log x \]

and the lemma imply

\[ F(x)\ll_r x^{1/(2r+1)}(\log x)^{\pi(r)+1}. \]

Choosing a sufficiently large but fixed \(r=r(\varepsilon)\) gives \(F(x)\ll_\varepsilon x^\varepsilon\) for every \(\varepsilon>0\). This is much weaker than Beker's quantitative subexponential bound and does not improve the live state of the art.

The exact missing input for this reduction is now explicit: a polylogarithmic, worst-case and uniform in the interval location, bound for \(G_r(x)\) for some fixed \(r\). Average short-interval density theorems do not supply it, because \(F(x)\) is defined by the single worst exceptional interval. The worst-case primary results located above still have power-scale length. This is a genuine uniformity gap, not a finiteness detail that can be discarded.

This reduction also makes Beker's obstruction concrete. His sieve removes high powers of small primes, after which high valuations attached to primes larger than the interval length remain. The multiplication-table count for the products of those valuations is exactly where the cube-root exponent is spent. An Erdős–Kac statement for typical integers does not control every integer in a worst-case interval and does not by itself bound those large-prime valuations.

3. Exact computation through \(20{,}000{,}000\)

Define

\[ a(k)=\min\{a\geq1:\tau(a),\tau(a+1),\ldots,\tau(a+k-1) \text{ are pairwise distinct}\}. \]

Claim (a). Whenever \(a(k)\) has been determined,

\[ F(x)\geq k\quad\Longleftrightarrow\quad a(k)+k-1\leq x. \]

This is immediate from the definitions.

Result

Claim (d). Exhaustive dual computation gives the following exact table for \(1\leq k\leq13\).

| \(k\) | \(a(k)\) | first endpoint \(a(k)+k-1\) | independently recomputed \(\tau\)-vector | |---:|---:|---:|:---| | 1 | 1 | 1 | \(1\) | | 2 | 1 | 2 | \(1,2\) | | 3 | 4 | 6 | \(3,2,4\) | | 4 | 9 | 12 | \(3,4,2,6\) | | 5 | 45 | 49 | \(6,4,2,10,3\) | | 6 | 76 | 81 | \(6,4,8,2,10,5\) | | 7 | 270 | 276 | \(16,2,10,8,4,6,12\) | | 8 | 2204 | 2211 | \(12,18,4,2,24,3,16,8\) | | 9 | 3718 | 3726 | \(12,2,32,3,4,8,18,6,20\) | | 10 | 95499 | 95508 | \(14,24,6,16,4,20,8,12,2,36\) | | 11 | 590890 | 590900 | \(16,12,24,6,8,20,10,4,32,2,36\) | | 12 | 16023339 | 16023350 | \(20,24,8,32,6,10,16,12,4,72,2,48\) | | 13 | 16475964 | 16475976 | \(48,24,16,20,14,4,64,2,6,32,8,12,96\) |

Claim (d). Among all starts whose complete window ends by \(20{,}000{,}000\):

\(16023339,16475964,16475965\);

It follows computationally that, for every integer \(1\leq x\leq20{,}000{,}000\), \(F(x)\) is exactly:

| range of \(x\) | \(F(x)\) | |:---|---:| | \(1\) | 1 | | \(2\leq x\leq5\) | 2 | | \(6\leq x\leq11\) | 3 | | \(12\leq x\leq48\) | 4 | | \(49\leq x\leq80\) | 5 | | \(81\leq x\leq275\) | 6 | | \(276\leq x\leq2210\) | 7 | | \(2211\leq x\leq3725\) | 8 | | \(3726\leq x\leq95507\) | 9 | | \(95508\leq x\leq590899\) | 10 | | \(590900\leq x\leq16023349\) | 11 | | \(16023350\leq x\leq16475975\) | 12 | | \(16475976\leq x\leq20000000\) | 13 |

Reproducible verifier

The standalone standard-library script is:

runs/erdos945_wavew023_reverify.py
SHA-256: 074794793d20b0f687fc5adaeea51b2cd0a0e394b09c9cd826dcc9159f16c809

Run it from the repository root:

python3 runs/erdos945_wavew023_reverify.py

The verifier does not import SymPy, OEIS data, or a precomputed prime/divisor table.

  1. Pass A factors one-million-integer blocks by a from-scratch Eratosthenes prime list. After all primes \(p\) with \(p^2<\text{block upper bound}\) have been divided out, every residual is \(1\) or prime.
  2. Pass B independently builds the full smallest-prime-factor array and uses

\[ \tau(p^em)=(e+1)\tau(m),\qquad (p,m)=1. \]

  1. All \(20{,}000{,}000\) values from the two passes are compared directly, entry by entry. Their common little-endian-uint32 SHA-256 is

   597f383c24a83065fe6128dc39c91af4c448c244c6c114df5303f555e831b93b

  1. A streaming last-occurrence algorithm keeps the longest suffix with distinct \(\tau\)-values. If the current value last appeared at \(j\) inside the suffix, its left endpoint moves to \(j+1\). Thus every possible endpoint is checked and the first record of each length is exact.
  2. Every displayed witness vector is recomputed a third way by enumerating divisor pairs \(d,n/d\), without either prime-factor algorithm.
  3. The script additionally performs 43,205 finite spot checks of the elementary “\(r\)-free implies \(r\)-smooth divisor count” lemma.

The final measured run took 16.770 seconds for the SPF pass and 30.657 seconds for the segmented pass on this VM, with no parallelism. These timings are evidence about reproducibility only, not a mathematical claim.

4. Honest boundary of the result

The computation proves a concrete finite regime only. It does not imply a uniform asymptotic bound and does not close the problem.

The next value listed by OEIS is \(a(14)=1{,}745{,}175{,}039\), but I have not promoted that database entry to a theorem or to a verified claim. Certifying its minimality with the present dual Python method would require scanning through endpoint \(1{,}745{,}175{,}052\), about 87.3 times the present range. Ideal linear scaling is roughly 1.1 core-hours, while interpreter/cache effects and the approximately 14 GB full SPF-plus-\(\tau\) arrays make 2–4 core-hours a more realistic dual-check budget. That exceeds the permitted few CPU-minutes, so it was not run. A segmented C/C++ implementation could reduce memory and likely time, but would still be a materially heavier computation.

At the asymptotic level, the clean sufficient missing lemma is:

For some fixed \(r\geq2\), prove \(G_r(x)\leq(\log x)^{O(1)}\) uniformly for every interval location.

For \(r=2\) this is the squarefree short-interval issue already highlighted by the live page. Alternatively, improving Beker's method requires a new uniform restriction on high exponents belonging to primes larger than the interval length. The primary sources and comments checked here supply neither input.

PARTIAL: Dual exhaustive computation proves the exact first starts through \(k=13\), the full step function \(F(x)\) for integer \(x\leq20{,}000{,}000\), and no length-14 run there; an elementary reduction isolates a uniform polylogarithmic \(r\)-free-gap lemma as sufficient, but the asymptotic problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger