Erdős Problem #347 - Discussion thread

PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.

Is there a sequence $A=\{a_1\leq a_2\leq \cdots\}$ of integers with\[\lim \frac{a_{n+1}}{a_n}=2\]such that\[P(A')= \left\{\sum_{n\in B}n : B\subseteq A'\textrm{ finite }\right\}\]has density $1$ for every cofinite subsequence $A'$ of $A$?

This has been solved in the affirmative by ebarschkis in the comments (based on idea of Tao and van Doorn, also in the comments).

View the LaTeX source

This page was last edited 22 January 2026.

Additional thanks to: ebarschkis, Terence Tao, and Wouter van Doorn

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #347, https://www.erdosproblems.com/347, accessed 2026-01-31

Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)

• I believe I have a solution based off of the ideas from Tao and Woett left here from last october:

  The construction builds \(A\) by concatenating blocks. Block \(n\) (of slowly growing length \(k_n \approx \log_2 \log_2 n\)) consists of \(M_n, 2M_n, \dots, 2^{k_n-2}M_n\), followed by the adjusted term \((2^{k_n-1}-1)M_n + 1\). The scales satisfy \(M_{n+1} \approx (2^{k_n} - 1.5)M_n\).

  Consecutive ratios inside and across blocks approach 2 as \(k_n, M_n \to \infty\).

  For any cofinite \(A'\), the tail \(T\) (full blocks from some point) allows a greedy base-like representation of nearly all numbers up to the next scale. The +1 shifts in the final position of each block provide enough carry adjustments (at least \(M_{n_0}\) such positions) to absorb any small remainder, covering all but a vanishing proportion of integers. Thus \(P(T)\) (hence \(P(A')\)) has density 1.

  Full details are in my quick note/paper here (PDF) and here (LaTeX Source).

  I also managed to get Aristotle to formalize the proof which you can find here (Lean v4.24.0).

  Any feedback is greatly appreciated!

  (The site has been updated to address this comment.)

• I think I can actually construct an example (a variant of Woett's idea). Let $k$ be large, and set $M_n := \lfloor (2^k - 1.5)^n \rfloor$ (the key point being that $M_{n+1}/M_n$ is strictly between $2^k-2$ and $2^k-1$). Consider the sequence $a_n$ defined by $a_{kn+r} = 2^r M_n$ for $r=0,\dots,k-2$, and $a_{kn+k-1} = (2^{k-1}-1)M_n + 1$. Then $a_{n+1}/a_n = 2 - O(1/2^k)$, so very close to the condition required (to upgrade this to $2-o(1)$ one needs to let $k$ grow slowly with $n$, but let me ignore this for this sketch).

  For any $k$, the subset sums of the block $a_{kn}, \dots, a_{kn+k-1}$ are the $2^k$ numbers
  $$ \{ j M_n: 0 \leq j \leq 2^{k-1}-1 \} \cup \{ jM_n + 1: 2^{k-1}-1 \leq j \leq 2^k-2\}.$$
  There is almost a collision, at $c_n := (2^{k-1}-1)M_n$ and $c_n+1 = (2^{k-1}-1)M_n+1$; we thus split the subset sums of this block into a $2^k-1$-element set
  $$ B_n := \{ j M_n: 0 \leq j \leq 2^{k-1}-1 \} \cup \{ jM_n + 1: 2^{k-1} \leq j \leq 2^k-2\}$$
  (which contains $c_n$) and a spare element $c_n+1$, which will be used for fixing "off by one" errors later.

  Suppose we are forming sums from the $a_n$ for $n \geq kn_0$ and some moderately large $n_0$. Let $n_1$ be very large. Observe that $B_n$ lies in $[0, M_{n+1}+1)$ and the gaps between consecutive entries of $B_n \cup \{M_{n+1}+1\}$ is at most $M_n+1$; thus every element in $[0, M_{n+1}+1)$ can be expressed as the sum of an element of $B_n$ and an element of $[0,M_n+1)$. Iterating this, we conclude that any number $m$ with $1 \leq m < M_{n_1+1}+1$ can almost be expressed (in a sort of "modified base $2^k-1$") as
  $$ \sum_{n=n_0}^{n_1} b_n $$
  where $b_n \in B_n$, in the sense that
  $$ \sum_{n=n_0}^{n_1} b_n \leq m < \sum_{n=n_0}^{n_1} b_n + M_{n_0}+1.$$

  So this isn't yet a density 1 set of representations. But most numbers $m$ will have at least $M_{n_0}$ of their "digits" $b_n$ in the above near-representation equal to $c_n$; the number that do not can be bounded by
  $$ (M_{n_0}+1) \times \sum_{r=0}^{M_{n_0}} \binom{n_1}{r} (2^k-2)^{n_1-r} = o( M_{n_1+1} )$$
  so this is a density zero set of exceptions as one sends $n_1 \to \infty$. If $m$ is expressible with $b_n=c_n$ for at least $M_{n_0}$ such $n$, one can flip $c_n$ to $c_n+1$ as many times as necessary to get an exact representation of $m$. Thus a density 1 set of $m$ can be expressed as a subset sum of the $a_n, n \geq kn_0$, which gives the claim.

  EDIT: Woett has offered to try to develop this idea further, perhaps all the way to a complete solution of the problem; will post further updates as appropriate.

• Graham proved that the sequence defined by $a_n = F_n - (-1)^n$ (with $F_n$ the $n$-th Fibonacci number) has the property that $P(A')$ contains all (!) large enough integers for every cofinite subsequence $A'$ of $A$. As I alluded to in my response to Terry, the latter property implies $a_{n+1} < \varphi a_n$ infinitely often, so that Graham's example is seen to be essentially best possible. This incidentally also shows for #346 that if the limit $\lim_n \frac{a_{n+1}}{a_n}$ exists in that problem, then it can be at most $\varphi$.

  As far as I'm aware no examples with the density $1$ property are even known with $a_{n+1} > \lambda a_n$ for all $n$ for some $\lambda > \varphi$. Assuming such examples do exist however, this easier question definitely feels attackable to me.

  And it is far from clear, but at least conceivable to me that $A = (a_1, a_2, \ldots)$ defined by something like $a_n = \left \lfloor \alpha^n \right \rfloor$, has the property that $P(A')$ has density $1$ for every cofinite subsequence $A'$ of $A$, as long as $\alpha < 2$. If this is even true and provable, then perhaps one can let $\alpha$ converge to $2$ sufficiently slowly.

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.