Does the sequence built from $2,3$ by adjoining all $a_ia_j-1$ have positive density? (Erdős #424)
Statement
Start with $a_1=2$ and $a_2=3$. Repeatedly enlarge the current set of terms $a_1,\ldots,a_n$ by adjoining all values $a_ia_j-1$ with $i\ne j$; let $A$ be the set of positive integers that eventually appear. The sorted sequence begins $2,3,5,9,14,17,26,\ldots$. Does $A$ have positive lower density — that is, is there a constant $c>0$ such that $\lvert A\cap[1,x]\rvert\ge cx$ for all large $x$? (Note that $A$ cannot have density $1$: if $a,b\in\{0,2\}\pmod 3$ then $ab-1\in\{0,2\}\pmod 3$, so by induction no integer $\equiv 1\pmod 3$ ever appears, giving $A$ upper density $\le 2/3$.)
Acceptance. FULLY RESOLVES: prove that $A$ has positive lower density — exhibit an explicit $c>0$ and prove $\lvert A\cap[1,x]\rvert\ge cx$ for all large $x$ — or prove that $A$ has lower density $0$; a complete proof, machine-checkable or fully written. ADVANCES (each independently checkable): (a) prove any nontrivial lower bound on the counting function $\lvert A\cap[1,x]\rvert$ that is asymptotically larger than any proven bound in the background (which records none beyond triviality), with proof; (b) prove an upper density strictly below $2/3$, or upgrade an upper bound to a proven statement, with proof; (c) compute $A\cap[1,x]$ to a new record $x$ with reproducible code, reporting the empirical density and its trend. Deliver the proof, or the generator code plus the attained $x$ and density estimates.
Background
Asked by Hofstadter; recorded by Erdős [Er77c, p.71] and Erdős–Graham [ErGr80, p.84], and discussed in section E31 of Guy's Unsolved Problems in Number Theory. It is A005244 in the OEIS. Listed as open on erdosproblems.com/424 (fetched 2026-07-13, status 'open', tagged 'number theory'). As literally written in [ErGr80] (and Guy) the question was whether almost all integers appear, but Steinerberger observed this is trivially false — no $n\equiv 1\pmod 3$ ever occurs, capping the density at $2/3$ — so the intended and still-open question, as correctly posed in [Er77c], is whether $A$ has positive lower density. The problem also appears as Problem 63 in Ben Green's open-problems list, and a Lean 4 formalisation exists in DeepMind's formal-conjectures repository. No nontrivial lower bound on the density is known. The attacker's tool: generate $A$ up to a large $x$ (the product rule makes the raw candidate set grow fast, so careful bounding/sieving of which products land in $[1,x]$ is needed), then estimate $\lvert A\cap[1,x]\rvert/x$ and its liminf; a resolution instead needs a proof of a positive-density lower bound (or that the density is $0$).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #424 (T. F. Bloom) | website |
| REF-02 | OEIS A005244 — Hofstadter's sequence generated by a_i*a_j-1 from {2,3} | website |
| REF-03 | B. J. Green, Open problems (Problem 63) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.