Erdős Problem #933

Erdős Problem 933 --- collection record

PROVENANCE AND STATUS

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, without editing their text.

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/933.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Let $n\ge 1$ be an integer and factor \[ n(n+1)=2^k3^l m, \] where $k:=v_2(n(n+1))$, $l:=v_3(n(n+1))$, and $m$ is an integer coprime to $6$ (so $(m,6)=1$). (Here $v_p$ is the usual $p$-adic valuation.) Let $\log$ denote the natural logarithm. The question is whether \[ \limsup_{n\to\infty} \frac{2^k3^l}{n\log n}=\infty. \]

2) QUICK LITERATURE/CONTEXT CHECK

From the provided problem statement: Mahler proved a more general result implying $2^k3^l<n^{1+o(1)}$. Erdős claimed it is easy to see that $2^k3^l>n\log n$ for infinitely many $n$, and Steinerberger noted a simple proof via $n=2^{3^r}$.

3) ATTACK PLAN

• Lower bound constructions: choose special $n$ so that $v_2(n(n+1))$ and/or $v_3(n(n+1))$ are large and computable via LTE (lifting-the-exponent).
• Try to amplify the ratio: look for $n$ where one of $n$ and $n+1$ is close to a large power of $2$ and the other is close to a large power of $3$.
• Computation: scan $n$ up to a moderate bound to see how large the ratio actually gets and what $n$ achieves it.

4) WORK

Lemma 933.1 (an infinite family with ratio $>1$ via $n=2^{3^r}$). For every integer $r\ge 1$, let $n=2^{3^r}$. Then \[ v_2(n(n+1))=3^r,\qquad v_3(n(n+1))=r+1, \] and hence \[ \frac{2^k3^l}{n\log n}=\frac{3}{\log 2}>1. \] In particular, $2^k3^l>n\log n$ for infinitely many $n$.

Proof. Let $n=2^{3^r}$. Then $n$ is even and $n+1$ is odd, so \[ v_2(n(n+1))=v_2(n)=3^r. \] Next, $2\equiv -1\pmod 3$, so $2^{3^r}\equiv -1\pmod 3$, hence $3\mid (2^{3^r}+1)=n+1$. We compute the exact 3-adic valuation using the standard LTE identity for odd primes $p$: if $p\mid (a+b)$ and $p\nmid ab$ and $t$ is odd, then \[ v_p(a^t+b^t)=v_p(a+b)+v_p(t). \] Apply this with $p=3$, $a=2$, $b=1$, and $t=3^r$ (odd). Since $3\mid (2+1)$ and $3\nmid 2$, LTE gives \[ v_3(2^{3^r}+1)=v_3(2+1)+v_3(3^r)=1+r. \] Because $n$ itself is a power of $2$, $v_3(n)=0$, so \[ v_3(n(n+1))=v_3(n+1)=r+1. \] Therefore $2^k3^l=2^{3^r}3^{r+1}=n\cdot 3^{r+1}$. Also $\log n = \log(2^{3^r})=3^r\log 2$. Hence \[ \frac{2^k3^l}{n\log n}=\frac{n\cdot 3^{r+1}}{n\cdot 3^r\log 2}=\frac{3}{\log 2}. \] $\square$

Lemma 933.2 (another infinite family via $n=3^{2^r}-1$). For every integer $r\ge 1$, let $n=3^{2^r}-1$. Then \[ v_3(n(n+1))=2^r,\qquad v_2(n(n+1))=r+2, \] and \[ \lim_{r\to\infty}\frac{2^k3^l}{n\log n}=\frac{4}{\log 3}>1. \] In particular, for all sufficiently large $r$ we have $2^k3^l>n\log n$.

Proof. Let $n=3^{2^r}-1$. Then $n+1=3^{2^r}$, so $v_3(n+1)=2^r$ and $v_3(n)=0$ (since $n\equiv -1\pmod 3$). Hence \[ v_3(n(n+1))=v_3(n+1)=2^r. \] Next, $n$ is even and $n+1$ is odd, so $v_2(n(n+1))=v_2(n)=v_2(3^{2^r}-1)$. We use the $2$-adic LTE formula for odd $a$ and even exponent $t$: \[ v_2(a^t-1)=v_2(a-1)+v_2(a+1)+v_2(t)-1. \] Apply this with $a=3$ and $t=2^r$. We have $v_2(3-1)=v_2(2)=1$, $v_2(3+1)=v_2(4)=2$, and $v_2(2^r)=r$. Therefore \[ v_2(3^{2^r}-1)=1+2+r-1=r+2. \] So $2^k3^l=2^{r+2}\cdot 3^{2^r}$. Since $n=3^{2^r}-1\sim 3^{2^r}$ and $\log n\sim 2^r\log 3$ as $r\to\infty$, we obtain \[ \frac{2^k3^l}{n\log n} =\frac{2^{r+2}3^{2^r}}{(3^{2^r}-1)\log(3^{2^r}-1)} \longrightarrow \frac{2^{r+2}}{2^r\log 3}=\frac{4}{\log 3}. \] The limit is $>1$, so for all sufficiently large $r$ the ratio exceeds $1$, giving $2^k3^l>n\log n$ infinitely often. $\square$

FAST REALITY CHECK (local computation up to $2{,}000{,}000$). I scanned all $2\le n\le 2{,}000{,}000$ and computed $R(n):=2^{v_2(n(n+1))}3^{v_3(n(n+1))}/(n\log n)$. The maximum value observed in this range was \[ \max_{2\le n\le 2{,}000{,}000} R(n)\approx 4.328085\,=\frac{3}{\log 2}, \] achieved for example at $n=2$ and $n=8$. (This is evidence only; it does not bound the true limsup.)

5) VERIFICATION

• Lemma 933.1: checked the hypotheses of LTE for $v_3(2^{3^r}+1)$: $3\mid 2+1$ and $3\nmid 2\cdot 1$ and exponent $3^r$ is odd.
• Lemma 933.2: checked the $2$-adic LTE conditions: base $3$ is odd and exponent $2^r$ is even.
• Computation: the scan used exact $v_2$ via trailing-zero count and exact division for $v_3$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here. There are infinitely many $n$ with $2^k3^l>n\log n$ (Lemma 933.1 gives an exact constant ratio $3/\log 2$ along $n=2^{3^r}$; Lemma 933.2 gives another constant $4/\log 3$ along $n=3^{2^r}-1$). Hence \[ \limsup_{n\to\infty}\frac{2^k3^l}{n\log n}\ \ge\ \frac{3}{\log 2}. \]

(ii) First gap (crisp). Either prove that the ratio $\frac{2^k3^l}{n\log n}$ is unbounded (limsup $=\infty$) or produce an explicit upper bound $\frac{2^k3^l}{n\log n}\le C$ for all sufficiently large $n$.

(iii) Top 3 next moves.

1. Search for $n$ such that one of $n,n+1$ is divisible by an unusually large power of $2$ while the other is divisible by an unusually large power of $3$, in a way that makes $2^k3^l$ close to $n^2$; this reduces to studying near-collisions of the form $2^a u \pm 1=3^b v$ with small $u,v$.
2. Extend the brute-force scan to larger $n$ using log-scale comparisons to see whether any $R(n)$ exceed $3/\log 2$ and to guess growth.
3. Try to bound $v_2(n)$ and $v_3(n\pm 1)$ simultaneously using $p$-adic methods (e.g. lifting-exponent plus constraints from exponential Diophantine equations) to either force boundedness or construct sequences with growing $v_2$ and $v_3$.

(iv) What a minimal counterexample would look like. If the conjectured limsup $=\infty$ is false, there would exist a constant $C$ and $n_0$ such that for all $n\ge n_0$, the $\{2,3\}$-part of $n(n+1)$ satisfies $2^k3^l\le C\,n\log n$. Any extremal $n$ should then avoid having simultaneously large $2$-adic valuation on one of $n,n+1$ and large $3$-adic valuation on the other.

COMPLETION ESTIMATE

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

1) FORMAL RESTATEMENT

Let $n\ge 1$ be an integer and factor \[ n(n+1)=2^k3^l m, \] where $k:=v_2(n(n+1))$, $l:=v_3(n(n+1))$, and $m$ is an integer coprime to $6$ (so $(m,6)=1$). (Here $v_p$ is the usual $p$-adic valuation.) Let $\log$ denote the natural logarithm. The question is whether \[ \limsup_{n\to\infty} \frac{2^k3^l}{n\log n}=\infty. \]

2) QUICK LITERATURE/CONTEXT CHECK

From the provided problem statement: Mahler proved a more general result implying $2^k3^l<n^{1+o(1)}$. Erdős claimed it is easy to see that $2^k3^l>n\log n$ for infinitely many $n$, and Steinerberger noted a simple proof via $n=2^{3^r}$.

3) ATTACK PLAN

• Lower bound constructions: choose special $n$ so that $v_2(n(n+1))$ and/or $v_3(n(n+1))$ are large and computable via LTE (lifting-the-exponent).
• Try to amplify the ratio: look for $n$ where one of $n$ and $n+1$ is close to a large power of $2$ and the other is close to a large power of $3$.
• Computation: scan $n$ up to a moderate bound to see how large the ratio actually gets and what $n$ achieves it.

4) WORK

Lemma 933.1 (an infinite family with ratio $>1$ via $n=2^{3^r}$). For every integer $r\ge 1$, let $n=2^{3^r}$. Then \[ v_2(n(n+1))=3^r,\qquad v_3(n(n+1))=r+1, \] and hence \[ \frac{2^k3^l}{n\log n}=\frac{3}{\log 2}>1. \] In particular, $2^k3^l>n\log n$ for infinitely many $n$.

Proof. Let $n=2^{3^r}$. Then $n$ is even and $n+1$ is odd, so \[ v_2(n(n+1))=v_2(n)=3^r. \] Next, $2\equiv -1\pmod 3$, so $2^{3^r}\equiv -1\pmod 3$, hence $3\mid (2^{3^r}+1)=n+1$. We compute the exact 3-adic valuation using the standard LTE identity for odd primes $p$: if $p\mid (a+b)$ and $p\nmid ab$ and $t$ is odd, then \[ v_p(a^t+b^t)=v_p(a+b)+v_p(t). \] Apply this with $p=3$, $a=2$, $b=1$, and $t=3^r$ (odd). Since $3\mid (2+1)$ and $3\nmid 2$, LTE gives \[ v_3(2^{3^r}+1)=v_3(2+1)+v_3(3^r)=1+r. \] Because $n$ itself is a power of $2$, $v_3(n)=0$, so \[ v_3(n(n+1))=v_3(n+1)=r+1. \] Therefore $2^k3^l=2^{3^r}3^{r+1}=n\cdot 3^{r+1}$. Also $\log n = \log(2^{3^r})=3^r\log 2$. Hence \[ \frac{2^k3^l}{n\log n}=\frac{n\cdot 3^{r+1}}{n\cdot 3^r\log 2}=\frac{3}{\log 2}. \] $\square$

Lemma 933.2 (another infinite family via $n=3^{2^r}-1$). For every integer $r\ge 1$, let $n=3^{2^r}-1$. Then \[ v_3(n(n+1))=2^r,\qquad v_2(n(n+1))=r+2, \] and \[ \lim_{r\to\infty}\frac{2^k3^l}{n\log n}=\frac{4}{\log 3}>1. \] In particular, for all sufficiently large $r$ we have $2^k3^l>n\log n$.

Proof. Let $n=3^{2^r}-1$. Then $n+1=3^{2^r}$, so $v_3(n+1)=2^r$ and $v_3(n)=0$ (since $n\equiv -1\pmod 3$). Hence \[ v_3(n(n+1))=v_3(n+1)=2^r. \] Next, $n$ is even and $n+1$ is odd, so $v_2(n(n+1))=v_2(n)=v_2(3^{2^r}-1)$. We use the $2$-adic LTE formula for odd $a$ and even exponent $t$: \[ v_2(a^t-1)=v_2(a-1)+v_2(a+1)+v_2(t)-1. \] Apply this with $a=3$ and $t=2^r$. We have $v_2(3-1)=v_2(2)=1$, $v_2(3+1)=v_2(4)=2$, and $v_2(2^r)=r$. Therefore \[ v_2(3^{2^r}-1)=1+2+r-1=r+2. \] So $2^k3^l=2^{r+2}\cdot 3^{2^r}$. Since $n=3^{2^r}-1\sim 3^{2^r}$ and $\log n\sim 2^r\log 3$ as $r\to\infty$, we obtain \[ \frac{2^k3^l}{n\log n} =\frac{2^{r+2}3^{2^r}}{(3^{2^r}-1)\log(3^{2^r}-1)} \longrightarrow \frac{2^{r+2}}{2^r\log 3}=\frac{4}{\log 3}. \] The limit is $>1$, so for all sufficiently large $r$ the ratio exceeds $1$, giving $2^k3^l>n\log n$ infinitely often. $\square$

FAST REALITY CHECK (local computation up to $2{,}000{,}000$). I scanned all $2\le n\le 2{,}000{,}000$ and computed $R(n):=2^{v_2(n(n+1))}3^{v_3(n(n+1))}/(n\log n)$. The maximum value observed in this range was \[ \max_{2\le n\le 2{,}000{,}000} R(n)\approx 4.328085\,=\frac{3}{\log 2}, \] achieved for example at $n=2$ and $n=8$. (This is evidence only; it does not bound the true limsup.)

5) VERIFICATION

• Lemma 933.1: checked the hypotheses of LTE for $v_3(2^{3^r}+1)$: $3\mid 2+1$ and $3\nmid 2\cdot 1$ and exponent $3^r$ is odd.
• Lemma 933.2: checked the $2$-adic LTE conditions: base $3$ is odd and exponent $2^r$ is even.
• Computation: the scan used exact $v_2$ via trailing-zero count and exact division for $v_3$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here. There are infinitely many $n$ with $2^k3^l>n\log n$ (Lemma 933.1 gives an exact constant ratio $3/\log 2$ along $n=2^{3^r}$; Lemma 933.2 gives another constant $4/\log 3$ along $n=3^{2^r}-1$). Hence \[ \limsup_{n\to\infty}\frac{2^k3^l}{n\log n}\ \ge\ \frac{3}{\log 2}. \]

(ii) First gap (crisp). Either prove that the ratio $\frac{2^k3^l}{n\log n}$ is unbounded (limsup $=\infty$) or produce an explicit upper bound $\frac{2^k3^l}{n\log n}\le C$ for all sufficiently large $n$.

(iii) Top 3 next moves.

1. Search for $n$ such that one of $n,n+1$ is divisible by an unusually large power of $2$ while the other is divisible by an unusually large power of $3$, in a way that makes $2^k3^l$ close to $n^2$; this reduces to studying near-collisions of the form $2^a u \pm 1=3^b v$ with small $u,v$.
2. Extend the brute-force scan to larger $n$ using log-scale comparisons to see whether any $R(n)$ exceed $3/\log 2$ and to guess growth.
3. Try to bound $v_2(n)$ and $v_3(n\pm 1)$ simultaneously using $p$-adic methods (e.g. lifting-exponent plus constraints from exponential Diophantine equations) to either force boundedness or construct sequences with growing $v_2$ and $v_3$.

(iv) What a minimal counterexample would look like. If the conjectured limsup $=\infty$ is false, there would exist a constant $C$ and $n_0$ such that for all $n\ge n_0$, the $\{2,3\}$-part of $n(n+1)$ satisfies $2^k3^l\le C\,n\log n$. Any extremal $n$ should then avoid having simultaneously large $2$-adic valuation on one of $n,n+1$ and large $3$-adic valuation on the other.