Erdős Problem #244

Erdős Problem 244: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

For fixed real $C>1$, put $S_C=\{p+\lfloor C^j\rfloor:p\text{ prime},\ j\ge0\}$. Must $S_C$ have positive lower asymptotic density? We prove a uniform-in-$x$ weaker bound \[ |S_C\cap[1,x]|\gg_C \frac{x}{\log\log x}, \tag{1} \] an exact first-moment asymptotic, and the positive-density conclusion when a positive integer power of $C$ is an integer. The assertion for every real base is unresolved here. Source: https://www.erdosproblems.com/244.

These extend the earlier GPT-5.2 first-moment observations. External inputs are the prime number theorem, the classical Mertens upper product bound, and the following Selberg upper sieve estimate, stated as Lemma 2.3 in Ding's primary paper https://arxiv.org/abs/2503.22700v5: \[ \#\{p\le x:p,\ p+d\text{ prime}\} \ll \frac{x}{(\log x)^2}W(d),\qquad W(d)=\prod_{p\mid d}\left(1+\frac1p\right), \tag{2} \] uniformly for the nonzero integer differences $|d|\le x$ used below and all large $x$. No proof of the sieve input is claimed here. Ding's almost-every-base theorem is context, not used to infer a result at every fixed base.

Counting representations and identifying the missing estimate

Let $A$ be the set of distinct integers $\lfloor C^j\rfloor$. The successive floors are distinct for all sufficiently large $j$, since $(C-1)C^j>1$. Thus \[ K(x):=|A\cap[1,x]|=\frac{\log x}{\log C}+O_C(1). \] Let $r_x(n)=\#\{a\in A:n-a\text{ is prime}\}$ for $n\le x$. The first moment is \[ R(x)=\sum_{n\le x}r_x(n)=\sum_{a\in A,\ a\le x}\pi(x-a) \sim\frac{x}{\log C}. \tag{3} \] For the upper bound, use $K(x)\pi(x)$. For any fixed $0<\delta<1$, retain only $a\le\delta x$ and bound every summand below by $\pi((1-\delta)x)$. Since $K(\delta x)\sim\log x/\log C$, the lower limit of $R(x)/x$ is at least $(1-\delta)/\log C$. Letting $\delta$ decrease to zero proves $3$.

Expanding the second moment, its diagonal contribution is $R(x)$. A pair $a<b$ contributes only prime pairs of difference $b-a$, so $2$ gives \[ E(x):=\sum_{n\le x}r_x(n)^2 \le R(x)+O\left(\frac{x}{\log^2x} \sum_{a<b\le x\atop a,b\in A}W(b-a)\right). \tag{4} \] In particular the concrete condition $\sum_{a<b\le x}W(b-a)=O_C(\log^2x)$ would give $E(x)=O_C(x)$, and Cauchy--Schwarz with $3$ would prove positive lower density. This identifies a sufficient arithmetic correlation estimate, rather than assuming independence of the shifts.

An unconditional weaker conclusion from the sieve

For $1\le d\le x$, split the prime divisors in $W(d)$ at $y=\log(3x)$. Mertens' classical bound gives \[ \prod_{p\le y}(1+1/p)\le\prod_{p\le y}(1-1/p)^{-1}\ll\log y. \] There are at most $\log d/\log y$ prime factors of $d$ larger than $y$. Their product contribution is at most \[ \exp\left(\frac{\log d}{y\log y}\right)=O(1). \] Therefore $W(d)\ll\log\log(3x)$ uniformly. Substituting this and $K(x)=O_C(\log x)$ into $4$ gives $E(x)\ll_C x\log\log x$. Finally \[ |S_C\cap[1,x]|\ge\frac{R(x)^2}{E(x)}\gg_C\frac{x}{\log\log x}, \] which proves $1$. This lower bound tends to zero after division by $x$ and does not answer the problem.

A dense family of bases and the remaining gap

Romanoff's theorem is the further explicit external input that $\{p+a^j\}$ has positive lower density for each integer $a\ge2$. If $C^q=a$ is an integer for some positive integer $q$, then $\lfloor C^{qj}\rfloor=a^j$, so $S_C$ contains that set and has positive lower density. Such bases are dense in $(1,\infty)$: for any $t>1$, $(\lfloor t^q\rfloor)^{1/q}\to t$.

Density at a dense family of bases supplies no uniform bound or continuity that passes to its limits. The missing part is a sufficiently strong correlation estimate for every fixed $C$, such as the condition following $4$. The trivial upper bound $|S_C\cap[1,x]|\le R(x)$ also shows that, when $C>e$, upper density is at most $1/\log C<1$; positivity would not mean density one. No numerical experiment is used as evidence of a proof.

Completion rate estimate: 35%.

Erdős Problem #244

1) FORMAL RESTATEMENT

Fix a real number $C>1$. Define the "geometric-floor" sequence \[ t_k \coloneqq \lfloor C^k\rfloor\qquad (k\in\mathbb{Z}_{\ge 0}), \] and the set \[ \mathcal{S}_C \coloneqq \{\, p + t_k : p\in\mathcal{P},\ k\in\mathbb{Z}_{\ge 0}\,\}\subseteq\mathbb{N}, \] where $\mathcal{P}$ is the set of primes and $\lfloor\cdot\rfloor$ is the floor function.

For $x\ge 1$ write \[ \mathcal{S}_C(x) \coloneqq \#\left(\mathcal{S}_C\cap\{1,2,\dots,\lfloor x\rfloor\}\right). \] The (lower) asymptotic density of $\mathcal{S}_C$ is \[ \underline{d}(\mathcal{S}_C) \coloneqq \liminf_{x\to\infty} \frac{\mathcal{S}_C(x)}{x}. \]

Question (Romanoff--Kalmár type). Is $\underline{d}(\mathcal{S}_C)>0$ for every real $C>1$?

Remark on ambiguity. The original phrasing "has density $>0$" could mean (i) the natural density exists and is positive, or (ii) the lower asymptotic density is positive. The currently recorded results (Romanoff for integer $C$; Ding for almost all real $C$) are naturally stated in terms of positive lower asymptotic density, so I interpret the question as above.

2) QUICK LITERATURE/CONTEXT CHECK

• For integer $C=a\ge 2$, the set $\{p+a^k\}$ has positive lower asymptotic density by Romanoff (often called Romanov's theorem) [Romanoff1934]. See also the modern summary "Romanov's theorem" [WikipediaRomanov].
• The Erdős Problems database page for #244 records: Romanoff's theorem for integer $C$, and that Y. Ding $2025$ proved positivity of the lower density for almost all $C>1$ (in the sense of Lebesgue measure) [ErdosProblems244,Ding2025].
• As of the last edit recorded on the Erdős Problems site (Oct 28, 2025), the statement "for every $C>1$" remains open [ErdosProblems244].

3) ATTACK PLAN

A classical approach for $C\in\mathbb{Z}_{\ge 2}$ (Romanoff) is:

1. Let $r(n)$ count representations $n=p+a^k$.
2. Use Cauchy--Schwarz: $\#\{n\le x:r(n)>0\}\ge \frac{(\sum_{n\le x} r(n))^2}{\sum_{n\le x} r(n)^2}$.
3. Estimate $\sum r(n)$ from below and bound $\sum r(n)^2$ from above using sieve bounds for prime pairs with fixed differences $a^{k_2}-a^{k_1}$.

For general real $C>1$, one would need to control differences \[ \lfloor C^{k_2}\rfloor-\lfloor C^{k_1}\rfloor \] uniformly in $k_1,k_2$ and prevent exceptional $C$ for which these differences have "too many" small prime factors (making sieve upper bounds too large) or create excessive overlap.

A disproof strategy (if false) would seek a specific $C$ where the set of shifts $\{\lfloor C^k\rfloor\}$ forces strong congruence restrictions so that $\mathcal{S}_C$ misses a positive proportion of residue classes for infinitely many moduli; no such explicit $C$ is currently known to me.

4) WORK

4.1 A trivial but rigorous lower bound

Even without Romanoff/Ding, one always has a nontrivial growth lower bound (though it only gives density $0$):

Consequently $\mathcal{S}_C(x)/x \ge \pi(x-1)/x \sim 1/\log x$ as $x\to\infty$, so this does not approach a positive constant.

4.2 Small computational sanity checks (not proofs)

I computed the empirical density \[ \frac{\mathcal{S}_C(X)}{X} \] for a few sample values of $C$ and cutoffs $X\in\{2\cdot 10^5,10^6\}$. The computation used:

• all distinct shifts $t_k=\lfloor C^k\rfloor\le X$;
• all primes $p\le X$;
• a boolean array to mark $p+t_k\le X$.

These values are consistent with the intuition that as $C\downarrow 1$, the shifts $\lfloor C^k\rfloor$ take many small values and the union of translates of the primes covers most integers up to moderate $X$. For larger $C$ there are fewer shifts and the observed density drops.

5) VERIFICATION

• The proof of the lemma is straightforward and uses only that $t_0=1$.
• The computations were double-checked for off-by-one issues by ensuring (i) primes were generated up to $X$, (ii) only shifts $\le X$ were used, and (iii) only sums $p+t_k\le X$ were marked.
• The computational results are included only as heuristic evidence; they do not address the limiting density as $X\to\infty$.

6) FINAL

UNRESOLVED.

1. Strongest fully proved partial result obtained here: For every $C>1$, the counting function satisfies $\mathcal{S}_C(x)\ge \pi(x-1)$ for all $x\ge 2$ (Lemma above), hence $\mathcal{S}_C(x)\gg x/\log x$.
2. First gap preventing a full solution: One needs a uniform lower bound $\mathcal{S}_C(x)\ge \delta x$ for all large $x$ with some $\delta=\delta(C)>0$. Achieving this requires controlling overlaps between the shifted prime sets $\{p+\lfloor C^k\rfloor\}$ across different $k$, typically via second-moment/sieve estimates. I did not obtain such an overlap bound for an arbitrary fixed real $C>1$.
3. Most promising next move: Attempt to adapt Romanoff's Cauchy--Schwarz/second-moment method to the shift sequence $\lfloor C^k\rfloor$ for an arbitrary fixed $C$. The key technical step is bounding the number of solutions to $p_1-p_2=\lfloor C^{k_2}\rfloor-\lfloor C^{k_1}\rfloor$ with $p_1,p_2$ prime using sieve bounds, and then summing these bounds over $(k_1,k_2)$.
4. Smallest plausible counterexample (if false): A candidate would be a special constant $C$ for which the differences $\lfloor C^{k_2}\rfloor-\lfloor C^{k_1}\rfloor$ are unusually "smooth" (have many small prime factors) for many pairs $(k_1,k_2)$, inflating sieve upper bounds and potentially allowing the second-moment argument to fail. I do not know any explicit $C$ with this property.

7) COMPLETION ESTIMATE

Estimated likelihood of completion with additional work: Low ($\approx 10\%$). The known results already cover integer $C$ and almost-every $C$, suggesting that the main obstacle is controlling a thin exceptional set of $C$.