Erdoes #420 - working report - Erdős Problem a Day

Erdős problem 420, wave 9g

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

0. Mandatory live-page gate

I fetched the live problem page, its LaTeX view, and its discussion thread through the Bright Data browser. I did not use datacenter curl for this gate.

The stop condition did not fire:

status: OPEN;
claimed proofs: 0 claimed proofs for this problem;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
all other reaction/worker fields shown on the page are also None;
the page says “Formalised statement? No” and was last edited

03 December 2025.

Verbatim live statement

The following is copied verbatim from the page's LaTeX endpoint:

If $\tau(n)$ counts the number of divisors of $n$ then let\[F(f,n)=\frac{\tau((n+\lfloor f(n)\rfloor)!)}{\tau(n!)}.\]Is it true that\[\lim_{n\to \infty}F((\log n)^C,n)=\infty\]for large $C$?

Is it true that $F(\log n,n)$ is everywhere dense in $(1,\infty)$?

More generally, if $f(n)\leq \log n$ is a monotonic function such that $f(n)\to \infty$ as $n\to \infty$, then is $F(f,n)$ everywhere dense?

Here and in the computation below, log means the natural logarithm.

Everything else mathematical on the live page

These are page/source reports, not new claims of this run.

(b) Erdős and Graham are reported to have shown

\(\lim F(n^{1/2},n)=\infty\), with \(n^{1/2}\) replaceable by \(n^{1/2-c}\) for some small \(c>0\).

(b) Erdős, Graham, Ivić, and Pomerance [EGIP96] are reported to have

proved \[ \liminf F(c\log n,n)=1,\qquad \lim F(n^{4/9},n)=\infty, \] for fixed \(c>0\), with the exponent \(4/9\) slightly improvable. The page also states that \(F(f,n)\sim1\) for almost all \(n\) when \(f(n)=o((\log n)^2)\).

(b) The page attributes to Wouter van Doorn the observations that

bounded prime gaps imply \(\limsup F(g(n),n)=\infty\) for every \(g(n)\to\infty\), and that Cramér's conjecture implies \(\lim F(g(n)(\log n)^2,n)=\infty\).

There is one comment, by Woett, timestamped 10:09 on

18 October 2025. The site explicitly warns that comments are unverified. The comment:

explains that the displayed statements in [EGIP96] are weaker than what

its proofs yield;

describes the one-step ratio in terms of the sum \(S(n)\) of prime

factors and identifies large prime factors in short intervals as the essential obstacle;

notes \(F(1,n)\leq2\), with equality exactly when \(n+1\) is prime;
gives the Cramér and bounded-gap consequences above.

The page says it was updated to address this comment. One detail needs care: the primary paper's actual asymptotic main term is the largest prime factor \(P(n)\), not \(S(n)\); \(S(n)\) supplies its two-sided elementary bounds. This distinction is used below.

1. Primary-source and current-literature check

Sources actually inspected

(b) P. Erdős and R. L. Graham, *Old and New Problems and Results in

Combinatorial Number Theory* (1980), printed p.83: primary scan. The scan has the original \(d\)-notation statement, including the \(n^{1/2-\varepsilon}\) remark, the \((\log n)^\alpha\) question, and the more general monotone sequence \(t_n\). Local PDF SHA-256: 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3.

(b) P. Erdős, S. W. Graham, A. Ivić, and C. Pomerance,

On the number of divisors of \(n!\), in Analytic Number Theory, 337–355 (1996): author-hosted PDF, DOI. Local PDF SHA-256: 0f89fea986741c12cdcb81efee7c76b251112b593e8f011152088281e954c4ae. Its Lemma 1 gives the \(S(n)\) bounds; Theorem 2 gives the uniform \(1+P(n)/n+O(n^{-1/2})\) formula; Theorems 3–4 and Corollary 3 treat the lower and upper behavior of the least window reaching ratio 2.

(b) J.-M. De Koninck and W. Verreault,

Arithmetic functions at factorial arguments, arXiv:2308.09761v2 (2024). Section 7 restates the EGIP one-step formula but does not advance the growing-window or density questions. Local PDF SHA-256: 21671aa5296d7f8dd17945161a0f23f5b2c08bf6055d4abaac6c6ebd0bb2b7ba.

(b) For the exact analytic obstruction, I also checked current primary

work on large prime factors in short intervals. Merikoski's arXiv:1805.05123 works at length \(x^{1/2}\log^{1.39}x\), and Li's 2026 arXiv:2601.00910 works at length \(x^{1/2+\varepsilon}\). Each guarantees a number with one very large prime factor; neither supplies the polylogarithmic, diverging weighted mass isolated below.

Targeted searches for the exact title/DOI, the expressions d((n+k)!)/d(n!), d((n+K)!)/d(n!), tau((n+k)!)/tau(n!), and later citations found no primary paper settling any of the three live questions. Semantic Scholar's DOI citation list did reveal the 2024 paper above; the other indexed citations were about global factorial values or unrelated applications. This is a documented search miss, not a proof that no unindexed paper exists.

A source inconsistency that must not be silently repaired

(a), as a textual/logical check. On p.5, [EGIP96] prints, in adjacent sentences,

k=o(\log^2n)\Longrightarrow F_k(n)\sim1\quad\hbox{for almost all }n,

and

k\sim c\log n\Longrightarrow F_k(n)\hbox{ has normal order }g(c)>1.

The second regime is contained in the first, so both assertions cannot be correct as printed. The live page repeats only the first. I preserve the live page's statement as requested, but do not use either conflicting aside in any proof below. The paper's proved one-step Theorem 2 and its displayed inequalities are unaffected.

2. Claim labels

(a) elementary-rigorous: proved here from definitions.
(b) rigorous-modulo-named-primary-source: the named source was checked,

but its full proof was not reproduced.

(c) plausible/structural-unverified: heuristic only.
(d) computational-only: exact finite computation reproduced by the

standalone checker; no uniform conclusion is inferred.

3. Exact one-step formula and a uniform window model

Put

D(N)=\tau(N!),\qquad R(m)=\frac{D(m)}{D(m-1)},\qquad w_p(t)=v_p(t!).

Let \(P(m)\) be the largest prime factor of \(m\), let \(S(m)\) be the sum of its prime factors counted with multiplicity, and set

\rho(m)=\frac{m}{P(m)}.

Lemma 1: exact update and \(S\)-bounds — (a)

If \(m=\prod p^{a_p}\), then

R(m) =\prod_{p^{a_p}\parallel m} \frac{w_p(m-1)+a_p+1}{w_p(m-1)+1} =\prod_{p^{a_p}\parallel m} \left(1+\frac{a_p}{w_p(m-1)+1}\right). \tag{1}

Moreover,

1+\frac{S(m)}{2m}\leq R(m)\leq \exp\!\left(\frac{S(m)}m\right)\leq1+\frac{2S(m)}m. \tag{2}

For \(p\mid m\),

w_p(m-1)+1\geq \left\lfloor\frac{m-1}{p}\right\rfloor+1 =\frac mp,

which gives the exponential upper bound in (2). In the other direction,

w_p(m-1)+1 <1+(m-1)\sum_{j\geq1}p^{-j}\leq\frac{2m}{p}.

Expanding the positive product in (1) and retaining its linear terms gives the lower bound. Finally \(S(m)\leq m\), and \(e^x\leq1+2x\) on \(0\leq x\leq1\).

Concavity of \(x\mapsto\log(1+x/2)\) consequently gives the useful exact comparison

\log(3/2)\frac{S(m)}m\leq\log R(m)\leq\frac{S(m)}m. \tag{3}

Thus for every integer window \(k\geq1\),

\log(3/2)\sum_{i=1}^k\frac{S(n+i)}{n+i} \leq\log\frac{D(n+k)}{D(n)} \leq\sum_{i=1}^k\frac{S(n+i)}{n+i}. \tag{4}

This makes the comment's “more or less sufficient” statement an exact two-sided equivalence for divergence.

Lemma 2: the largest-prime-factor main term — (a)

Uniformly for \(m\geq2\),

R(m)=1+\frac{P(m)}m+O(m^{-1/2}) =1+\frac1{\rho(m)}+O(m^{-1/2}). \tag{5}

Here is a self-contained proof. If \(P(m)\leq\sqrt m\), order the prime factors with multiplicity as \(p\geq q\geq\cdots\). If \(q\leq m^{1/3}\), then

S(m)\leq\sqrt m+m^{1/3}\frac{\log m}{\log 2}=O(\sqrt m).

If \(q>m^{1/3}\), then

S(m)\leq p+q+\frac{m}{pq}\leq3\sqrt m.

Equation (2) now gives \(R(m)=1+O(m^{-1/2})\), and \(P(m)/m\leq m^{-1/2}\).

If \(p=P(m)>\sqrt m\), write \(m=rp\), so \(r<\sqrt m\). The \(p\)-factor in (1) is exactly

\frac{r+1}{r}=1+\frac{p}{m}.

The product of all remaining factors lies between 1 and \(\exp(S(r)/m)\leq\exp(r/m)=1+O(m^{-1/2})\). This proves (5).

The uniform window formula — (a)

Because both sides of (5) are at least 1, the logarithm is Lipschitz on the relevant range. Summing (5) yields, uniformly in \(k\),

\boxed{\quad \log\frac{D(n+k)}{D(n)} =\sum_{i=1}^k\log\left(1+\frac1{\rho(n+i)}\right) +O\left(\frac{k}{\sqrt n}\right). \quad} \tag{6}

In particular, whenever \(k=o(\sqrt n)\),

\frac{D(n+k)}{D(n)} =(1+o(1))\prod_{i=1}^k\left(1+\frac1{\rho(n+i)}\right). \tag{7}

This applies simultaneously to every fixed polylogarithmic window in the first question and every \(k\leq\log n\) in the density questions.

4. Two exact reductions: what remains

4.1 The first question is a uniform weighted-prime theorem — (a)

Let

h=h_C(n)=\left\lfloor(\log n)^C\right\rfloor.

Since \((\log 2)x\leq\log(1+x)\leq x\) for \(0\leq x\leq1\), (6) gives

(\log 2)\sum_{i=1}^h\frac1{\rho(n+i)}+o(1) \leq\log F((\log n)^C,n) \leq\sum_{i=1}^h\frac1{\rho(n+i)}+o(1). \tag{8}

Consequently, for each fixed \(C\), the following are equivalent:

\begin{aligned} &F((\log n)^C,n)\longrightarrow\infty,\\ &\sum_{i=1}^{h}\frac1{\rho(n+i)}\longrightarrow\infty,\\ &\frac1n\sum_{i=1}^{h}P(n+i)\longrightarrow\infty. \end{aligned} \tag{9}

The last equivalence uses \(h=o(n)\).

Terms with \(\rho(n+i)>h\) contribute at most 1 in total. For \(\rho(n+i)=r\leq h\), write \(n+i=rp\). Since

p\geq n/h\gg h\geq r\geq P(r),

for all large \(n\), \(p\) is automatically the largest prime factor exactly when it is prime. Define

N_r(n,h)=\#\left\{1\leq i\leq h: r\mid n+i,\ \frac{n+i}{r}\ {\rm is\ prime}\right\}. \tag{10}

The first question is therefore equivalent to the following precise missing lemma:

\boxed{\quad \text{Does some fixed \(C\) satisfy }\quad \sum_{r\leq h_C(n)}\frac{N_r(n,h_C(n))}{r} \longrightarrow\infty \quad\text{for every sufficiently large \(n\)?} \quad} \tag{11}

The \(r=1\) summand counts primes in the original interval. Formula (11) shows exactly how prime multiples with small cofactors could replace primes; one isolated large prime factor is not enough for divergence.

4.2 The density questions reduce to moving prime-pattern counts — (a)

Let \(k=\lfloor f(n)\rfloor\), where \(k\to\infty\) and \(k\leq\log n\). The contribution in (6) from \(\rho(n+i)>k^2\) is at most

k\log(1+k^{-2})\leq\frac1k=o(1).

For \(r\leq k^2\), the same size argument as above shows that \(\rho(n+i)=r\) is equivalent, for all large \(n\), to \((n+i)/r\) being prime. Hence

\boxed{\quad \log F(f,n) =\sum_{r\leq k^2}N_r(n,k)\log\left(1+\frac1r\right)+o(1), \quad} \tag{12}

uniformly over every admissible \(f\).

Two real sequences differing by \(o(1)\) have the same tail-density behavior. Thus:

\(F(\log n,n)\) is dense in \((1,\infty)\) exactly when the right side of

(12), with \(k=\lfloor\log n\rfloor\), is dense in \((0,\infty)\);

the general question is exactly the same assertion for every admissible

moving \(k=\lfloor f(n)\rfloor\).

This is more specific than “large prime factors in short intervals.” What is missing is joint control of the weighted events

r\mid n+i,\qquad (n+i)/r\ {\rm prime}, \qquad r\leq k^2,\quad1\leq i\leq k, \tag{13}

including the complementary offsets, so that their weighted sum can be steered into every prescribed real interval.

5. Exact finite computation for \(F(\log n,n)\)

All statements in this section are (d).

The standalone checker erdos420_wave9g_reverify.py uses only the Python standard library.

Its first computation is an exhaustive exact rational scan of all \(999{,}998\) integers \(3\leq n\leq10^6\). It:

certifies the band starts

\[ \lceil e^k\rceil= 3,8,21,55,149,404,1097,2981,8104,22027,59875, 162755,442414,1202605 \] using rational Taylor lower/upper bounds, so no floating-point logarithm chooses a window;

computes (1) with Fraction and updates the \(k\)-term window exactly;
checks both inequalities in (2) for every one-step ratio used;
recomputes every retained certificate independently, prime by prime, from

Legendre's formula for \(v_p(n!)\), using a second sieve;

checks tiny cases directly by forming factorials and counting their

divisors from the definition.

Run:

python3 runs/erdos420_wave9g_reverify.py

Result on this VM: ALL ASSERTIONS PASSED, 62.125 seconds, peak RSS 27,472 KiB. There were 57 independently recomputed certificates; their canonical payload has SHA-256 c167bfac54f55e8c43cadaac6958fd094fa8c453083d303ca033e0688b20b5c3.

The positions and counts below are exact; displayed values are decimal renderings of exact fractions. “Model error” means \(\left|F/\prod_{i=1}^k(1+1/\rho(n+i))-1\right|\).

| \(k\) | exact \(n\)-range | \(F\geq2\) / count | minimum \(F\) at \(n\) | maximum \(F\) at \(n\) | closest-to-\(3/2\) error at \(n\) | largest model error | |---:|---:|---:|---:|---:|---:|---:| | 1 | 3–7 | 3 / 5 | 1.600000 @ 7 | 2.000000 @ 3 | \(1.00\cdot10^{-1}\) @ 7 | \(3.33\cdot10^{-1}\) | | 2 | 8–20 | 13 / 13 | 2.069717 @ 19 | 3.375000 @ 9 | \(5.70\cdot10^{-1}\) @ 19 | \(4.06\cdot10^{-1}\) | | 3 | 21–54 | 32 / 34 | 1.744615 @ 53 | 5.086342 @ 28 | \(2.45\cdot10^{-1}\) @ 53 | \(3.94\cdot10^{-1}\) | | 4 | 55–148 | 94 / 94 | 2.031359 @ 62 | 7.028061 @ 57 | \(5.31\cdot10^{-1}\) @ 62 | \(2.66\cdot10^{-1}\) | | 5 | 149–403 | 237 / 255 | 1.456891 @ 373 | 8.613217 @ 176 | \(3.71\cdot10^{-2}\) @ 339 | \(1.74\cdot10^{-1}\) | | 6 | 404–1096 | 642 / 693 | 1.328372 @ 1021 | 9.718650 @ 497 | \(2.91\cdot10^{-3}\) @ 984 | \(1.19\cdot10^{-1}\) | | 7 | 1097–2980 | 1700 / 1884 | 1.213479 @ 2621 | 15.700982 @ 2796 | \(2.47\cdot10^{-3}\) @ 2824 | \(7.87\cdot10^{-2}\) | | 8 | 2981–8103 | 4437 / 5123 | 1.132322 @ 4894 | 19.970572 @ 4785 | \(6.44\cdot10^{-4}\) @ 5132 | \(5.11\cdot10^{-2}\) | | 9 | 8104–22026 | 11915 / 13923 | 1.122535 @ 16163 | 30.827053 @ 15640 | \(4.66\cdot10^{-5}\) @ 8973 | \(3.25\cdot10^{-2}\) | | 10 | 22027–59874 | 31948 / 37848 | 1.051233 @ 48502 | 35.096357 @ 25300 | \(3.30\cdot10^{-5}\) @ 23567 | \(1.93\cdot10^{-2}\) | | 11 | 59875–162754 | 86076 / 102880 | 1.050924 @ 135990 | 36.415714 @ 146832 | \(2.93\cdot10^{-5}\) @ 76971 | \(1.25\cdot10^{-2}\) | | 12 | 162755–442413 | 231929 / 279659 | 1.020086 @ 416319 | 45.017234 @ 247990 | \(9.34\cdot10^{-6}\) @ 355392 | \(7.58\cdot10^{-3}\) | | 13 | 442414–1000000 | 461666 / 557587 | 1.021236 @ 780356 | 61.255769 @ 470076 | \(3.31\cdot10^{-7}\) @ 970494 | \(4.98\cdot10^{-3}\) |

Over the whole scanned range, exactly 830,692 values satisfy \(F\geq2\). The exact global extrema are

\begin{aligned} F(\log 416319,416319) &=\frac{ 52903062375466195016233054422239124499396190796796122307075578832582980109587 }{ 51861394942743754703375789935268058147887822561033102383883981028802470871040 }\\ &=1.020085603826748\ldots, \end{aligned}

and

\begin{aligned} F(\log 470076,470076) &=\frac{ 21058082141162140622942126683578374484122918624000 }{ 343773046081102540616918767137986712917528398387 }\\ &=61.25576854037050\ldots. \end{aligned}

The best \(3/2\) hit in the terminal band is

F(\log 970494,970494) =\frac{197386887253498214815819646388643379839606368} {131591287196543464018722748876089955474813505},

whose exact distance from \(3/2\) is

\frac{87082633962424528953850983106745227779} {263182574393086928037445497752179910949627010} =3.308829779602306\ldots\times10^{-7}.

As a finite tail-coverage check, for the 557,587 values in the single band \(442414\leq n\leq10^6\), the exact nearest hits to the quarter-grid are:

| target | attaining \(n\) | exact absolute error (decimal rendering) | |---:|---:|---:| | \(5/4\) | 550878 | \(4.590928695995064\cdot10^{-6}\) | | \(3/2\) | 970494 | \(3.308829779602306\cdot10^{-7}\) | | \(7/4\) | 877140 | \(4.743342704043465\cdot10^{-6}\) | | \(2\) | 970156 | \(1.308122328213046\cdot10^{-6}\) | | \(9/4\) | 545308 | \(4.750754908756469\cdot10^{-7}\) | | \(5/2\) | 833941 | \(3.552163382241628\cdot10^{-7}\) | | \(11/4\) | 577777 | \(9.825216112713825\cdot10^{-6}\) | | \(3\) | 760466 | \(7.075240643791264\cdot10^{-6}\) | | \(13/4\) | 869073 | \(4.089303870762464\cdot10^{-6}\) | | \(7/2\) | 800796 | \(4.803101482503445\cdot10^{-6}\) | | \(15/4\) | 638291 | \(8.656737729342220\cdot10^{-6}\) | | \(4\) | 864121 | \(2.071468672685934\cdot10^{-6}\) |

The worst error on this finite grid is therefore the exact rational

\frac{5823874313261953133407495830528716671237411} {592747706152321924193437463064867493024803284644} =9.825216112713825\ldots\times10^{-6}.

This is evidence only. A finite mesh, even with exact arithmetic, proves neither density nor any asymptotic trend.

6. Precise wall

Why the first question remains open here

(a) Formula (11) is a necessary-and-sufficient target, not just a sufficient criterion. It asks for a lower bound valid in every polylogarithmic interval and tending to infinity:

\sum_{r\leq h}\frac{1}{r} \#\{i\leq h:r\mid n+i,\ (n+i)/r\ {\rm prime}\}\to\infty.

Existing “one integer with a large prime factor” results at roughly square-root interval length can add only \(O(1)\) to this sum and operate on a vastly longer scale. They do not imply (11). Cramér's conjecture supplies many \(r=1\) terms and explains the conditional result on the live page, but no unconditional uniform polylogarithmic substitute was found.

Why the density questions remain open here

(a) Formula (12) isolates the missing statement: for selected \(n\), one must control the joint counts \(N_r(n,k)\), for moving \(r\leq k^2\), accurately enough to place

\sum_{r\leq k^2}N_r(n,k)\log(1+1/r)

inside every target interval, while also controlling all unselected offsets. Average sieve estimates or a theorem producing one large prime factor do not provide this joint local pattern. This is the exact lemma a proof would need to add.

Computation scale

The exact \(10^6\) scan is linear-time in the endpoint apart from small integer-arithmetic growth. Straight extrapolation puts \(10^8\) at roughly 1.7–2.5 core-hours and at least 0.4 GB for the factor table; \(10^9\) would be on the order of 17–25 core-hours and 4 GB. Neither scale addresses the uniformity/finiteness step in (11) or the joint-pattern theorem in (12), so I did not run it.

No construction, counterexample, or closure claim is made.

PARTIAL: Proved an elementary uniform prime-cofactor product formula and exact necessary-and-sufficient reductions (11)–(12), and exhaustively verified all 999,998 values of F(log n,n) through 10^6; the missing uniform/joint short-interval prime-cofactor lemma remains open.

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