Dual View Random Solved Random Open
OPEN This is open, and cannot be resolved with a finite computation.
Let $a_1<a_2<\cdots$ be a sequence of integers such that\[\lim_{n\to \infty}\frac{a_n}{a_{n-1}^2}=1\]and $\sum\frac{1}{a_n}\in \mathbb{Q}$. Then, for all sufficiently large $n\geq 1$,\[ a_n = a_{n-1}^2-a_{n-1}+1.\]
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
ErdΕ‘s and Straus [ErSt64] proved that if $\lim a_n/a_{n-1}^2=1$ and $\sum \frac{1}{a_n}$ is rational, and $a_n$ does not satisfy the recurrence, then\[\limsup_{n\to \infty} \frac{[a_1,\ldots,a_n]}{a_{n+1}}\left(\frac{a_n^2}{a_{n+1}}-1\right)>0.\]A sequence satisfying the reucrrence $a_n = a_{n-1}^2-a_{n-1}+1$ is known as Sylvester's sequence.

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.

View the LaTeX source

This page was last edited 28 September 2025.

External data from the database - you can help update this
Formalised statement? Yes
Related OEIS sequences: A000058

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 #243, https://www.erdosproblems.com/243, accessed 2025-11-16
Order by oldest first or newest first.
  • Such sequences can be described (after discarding a finite segment) via a deterministic recurrence applied to an initial pair $b,c$ of natural numbers; in particular, there are only countably many such sequences.

    Indeed, if $\sum \frac{1}{a_n}$ is rational, write $\frac{b_n}{c_n} = \sum_{n' \geq n} \frac{1}{a_n}$, then $\frac{b_n}{c_n} = \frac{1}{a_n} + \frac{b_{n+1}}{c_{n+1}}$. Writing $b_n a_n = c_n + h_n$, we have $b_n | c_n + h_n$, $b_{n+1} = h_n$, and $c_{n+1} = c_n \frac{c_n+h_n}{b_n}$. The condition $\lim_{n \to \infty} \frac{a_n}{a_{n-1}^2}=1$ means that $a_{n+1} = (1+o(1)) a_n^2$, that $\frac{b_n}{c_n} = (1+o(1)) \frac{1}{a_n}$, and thus $\frac{b_{n+1}}{c_{n+1}} = (1+o(1)) \frac{b_n^2}{c_n^2}$, which after some more algebra leads to $h_n = (1+o(1)) b_n$. Because of this, for $n$ sufficiently large one can solve for $\frac{c_n+h_n}{b_n}$ exactly as the nearest integer $\lfloor \frac{c_n}{b_n}+1 \rceil$ to $\frac{c_n}{b_n}+1$, and so the pair $(b_n,c_n)$ iterates via the recurrence

    $$ (b_{n+1}, c_{n+1}) = (b_n \lfloor \frac{c_n}{b_n}+1 \rceil - c_n, c_n \lfloor \frac{c_n}{b_n}+1 \rceil).$$
    This iteration yields a sequence of the desired form if and only if $\mathrm{dist}(c_n/b_n, {\mathbf Z}) \to 0$ as $n \to \infty$ (or equivalently $b_{n+1} = (1+o(1)) b_n$). If the $b_n$ stayed bounded, then this would force the $b_n$ to eventually become constant, at which point the $c_n$ must be multiples of $b_n$ and one can check that one becomes a Sylvester sequence at that point. So the question comes down to whether there is a solution to the above recurrence in which the $b_{n+1}/b_n$ tend to $1$ but never actually equal $1$ (if $b_{n+1}=b_n$ one can check that $b_m = b_n$ for all $m > n$).

    Heuristically, any such sequence should have a zero probability of $b_{n+1}/b_n$ converging to 1 (it requires $c_n/b_n$ to be inexplicably close to an integer for all sufficiently large $n$), which indicates that the answer to this question is "no" [EDIT: I meant "yes"]; but the recurrence looks quite difficult to analyze (especially as the $c_n$ grow doubly exponentially fast) and I see no plausible way to rigorously prove the claim.

    • Very similar observations were made by Junnosuke Koizumi in this recent preprint. He formulated them as a conditional result: that the claim holds if and only if (what he calls) a "pseudo-greedy expansion" of a rational number (a variant of a greedy Egyptian fraction algorithm) always terminates. He gives some numerical evidence for the opposite heuristics than you, checking his Conjecture 6 for rationals $p/q$ such that $p,q\leq100000$ and also reasoning probabilistically "on average" (Remark 17). Thus, the question might in fact likely have positive answer, but it is hard to say what really is a good heuristics here.

      Slightly off-topic: I suggested exploiting a bit more the connection between (ir)rationality questions and greedy algorithms for (restricted) Egyptian fractions, under somewhat open-ended [282].

      • Thanks for the reference! I misspoke in my previous reply, I was focused on the question on whether a counterexample (non-Sylvester sequence) existed, which of course is the negation of the original problem, so I agree with Koizumi's prediction that the answer here is positive.

        • Now I see what you meant. I apologize for not reading the last paragraph carefully.

          • After reading through Koizumi's manuscript I see that basically all the observations I made here are contained in that paper already. Still, good to have it mentioned on this problem page.

  • "Perhaps", In Corollary 3.2 of "Irrationality of Fast Converging Series of Rational Numbers" by Daniel Duverney, 2001, a partial answer to this question has been given. One can see it here: https://www.ms.u-tokyo.ac.jp/journal/pdf/jms080206.pdf

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.

Log in to add a comment.

Back to the forum