Logo
All Random Solved Random Open
94 solved out of 293 shown (show only solved or open)
OPEN - $500
If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then \[N \gg 2^{n}.\]
Erdős called this 'perhaps my first serious problem' (in [Er98] he dates it to 1931). The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser [Er56] proved \[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\] (In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.

See also [350].

Additional thanks to: Zach Hunter and Ralf Stephan
SOLVED - $1000
Can the smallest modulus of a covering system be arbitrarily large?
Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown (contrary to Erdős' expectations) that the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the upper bound on the smallest modulus to $616000$.

The best known lower bound is a covering system whose minimum modulus is $42$, due to Owens [Ow14].

Additional thanks to: Desmond Weisenberg
OPEN - $5000
If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?
This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like \[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\] would be sufficient.

Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.

Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08] (see [219]).

In [Er81] Erdős makes the stronger conjecture that \[r_k(N) \ll_C\frac{N}{(\log N)^C}\] for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].

See also [139] and [142].

SOLVED - $100
Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?
Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'. (In [Er85c] he goes further and offers 'all the money I can earn, beg, borrow or steal for [a disproof]'.)

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

Additional thanks to: Mehtaab Sawhney
Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).

Additional thanks to: Antonio Girao
SOLVED
For any finite colouring of the integers is there a covering system all of whose moduli are monochromatic?
Conjectured by Erdős and Graham, who also ask about a density-type version: for example, is \[\sum_{\substack{a\in A\\ a>N}}\frac{1}{a}\gg \log N\] a sufficient condition for $A$ to contain the moduli of a covering system? The answer (to both colouring and density versions) is no, due to the result of Hough [Ho15] on the minimum size of a modulus in a covering system - in particular one could colour all integers $<10^{18}$ different colours and all other integers a new colour.
OPEN
Let $A$ be the set of all integers not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?
Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

Additional thanks to: Ralf Stephan
OPEN
Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?
Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

See also [9], [11], and [16].

Additional thanks to: Bogdan Grechuk
OPEN
Is every odd $n$ the sum of a squarefree number and a power of 2?
Odlyzko has checked this up to $10^7$. Hercher [He24b] has verified this is true for all odd integers up to $2^{50}\approx 1.12\times 10^{15}$.

Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding primes $p$ for which $2^p\equiv 2\pmod{p^2}$ (for example this conjecture implies there are infinitely many such $p$).

Erdős often asked this under the weaker assumption that $n$ is not divisible by $4$. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.

See also [9], [10], and [16].

Additional thanks to: Milos
OPEN
We call $m$ practical if every integer $n<m$ is the sum of distinct divisors of $m$. If $m$ is practical then let $h(m)$ be such that $h(m)$ many divisors always suffice.

Are there infinitely many practical $m$ such that \[h(m) < (\log\log m)^{O(1)}?\] Is it true that $h(n!)<n^{o(1)}$? Or perhaps even $h(n!)<(\log n)^{O(1)}$?

It is easy to see that almost all numbers are not practical. Erdős originally showed that $h(n!) <n$. Vose [Vo85] proved the existence of infinitely many practical $m$ such that $h(m)\ll (\log m)^{1/2}$.

The sequence of practical numbers is A005153 in the OEIS.

See also [304] and [825].

Additional thanks to: Ralf Stephan
OPEN - $500
If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.
Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

SOLVED - $100
Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$?
The existence of such a set was asked by Sidon to Erdős in 1932. Erdős (eventually) proved the existence of such a set using probabilistic methods. This problem asks for a constructive solution.

An explicit construction was given by Jain, Pham, Sawhney, and Zakharov [JPSZ24].

SOLVED
For any permutation $\pi\in S_n$ of $\{1,\ldots,n\}$ let $S(\pi)$ count the number of distinct consecutive sums, that is, sums of the shape $\sum_{u\leq i\leq v}\pi(i)$. Is it true that \[S(\pi) = o(n^2)\] for all $\pi\in S_n$?
It is easy to see that $S(\iota)=o(n^2)$ if $\iota$ denotes the identity permutation, as studied by Erdős and Harzheim [Er77]. Motivated by this, Erdős asked if this remains true for all permutations.

This is extremely false, as shown by Konieczny [Ko15], who both constructs an explicit permutation with $S(\pi) \geq n^2/4$, and also shows that for a random permutation we have \[S(\pi)\sim \frac{1+e^{-2}}{4}n^2.\]

See also [356] and [357].

SOLVED
We say that $A\subset \mathbb{N}$ is an essential component if $d_s(A+B)>d_s(B)$ for every $B\subset \mathbb{N}$ with $0<d_s(B)<1$ where $d_s$ is the Schnirelmann density.

Can a lacunary set $A\subset\mathbb{N}$ be an essential component?

The answer is no by Ruzsa [Ru87], who proved that if $A$ is an essential component then there exists some constant $c>0$ such that $\lvert A\cap \{1,\ldots,N\}\rvert \geq (\log N)^{1+c}$ for all large $N$.
OPEN - $500
Is there an infinite Sidon set $A\subset \mathbb{N}$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all $\epsilon>0$?
The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\] and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

OPEN - $500
Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\in A$ (aside from the trivial coincidences). Is it true that \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\]
Erdős proved that if the pairwise sums $a+b$ are all distinct aside from the trivial coincidences then \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]
Additional thanks to: Zachary Chase
SOLVED
Does every finite colouring of the integers have a monochromatic solution to $1=\sum \frac{1}{n_i}$ with $2\leq n_1<\cdots <n_k$?
The answer is yes, as proved by Croot [Cr03].

See also [298].

SOLVED - $100
If $\delta>0$ and $N$ is sufficiently large in terms of $\delta$, and $A\subseteq\{1,\ldots,N\}$ is such that $\sum_{a\in A}\frac{1}{a}>\delta \log N$ then must there exist $S\subseteq A$ such that $\sum_{n\in S}\frac{1}{n}=1$?
Solved by Bloom [Bl21], who showed that the quantitative threshold \[\sum_{n\in A}\frac{1}{n}\gg \frac{\log\log\log N}{\log\log N}\log N\] is sufficient. This was improved by Liu and Sawhney [LiSa24] to \[\sum_{n\in A}\frac{1}{n}\gg (\log N)^{4/5+o(1)}.\] Erdős speculated that perhaps even $\gg (\log\log N)^2$ might be sufficient. (A construction of Pomerance, as discussed in the appendix of [Bl21], shows that this would be best possible.)

See also [46] and [298].

SOLVED
Are there infinitely many integers $n,m$ such that $\phi(n)=\sigma(m)$?
This would follow immediately from the twin prime conjecture. The answer is yes, proved by Ford, Luca, and Pomerance [FLP10].
OPEN - $250
Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$ \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\]
The sum-product problem. Erdős and Szemerédi [ErSz83] proved a lower bound of $\lvert A\rvert^{1+c}$ for some constant $c>0$, and an upper bound of \[\lvert A\rvert^2 \exp\left(-c\frac{\log\lvert A\rvert}{\log\log \lvert A\rvert}\right)\] for some constant $c>0$. The lower bound has been improved a number of times. The current record is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{1270}{951}-o(1)}\] due to Bloom [Bl25] (note $1270/951=1.33543\cdots$). A complete history of sum-product bounds can be found at this webpage.

There is likely nothing special about the integers in this question, and indeed Erdős and Szemerédi also ask a similar question about finite sets of real or complex numbers. The current best bound for sets of reals is the same bound of Rudnev and Stevens above. The best bound for complex numbers is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}},\] due to Solymosi [So05].

One can in general ask this question in any setting where addition and multiplication are defined (once one avoids any trivial obstructions such as zero divisors or finite subfields). For example, it makes sense for subsets of finite fields. The current record is that there exists $c>0$ such that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{c}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}+o(1)},\] due to Mohammadi and Stevens [MoSt23].

There is also a natural generalisation to higher-fold sum and product sets. For example, in [ErSz83] (and in [Er91]) Erdős and Szemerédi also conjecture that for any $m\geq 2$ and finite set of integers $A$ \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation and [808] for a stronger form of the original conjecture. See also [818] for a special case.

Additional thanks to: Akshat Mudgal
SOLVED
Let $A$ be a finite set of integers. Is it true that, for every $k$, if $\lvert A\rvert$ is sufficiently large depending on $k$, then there are least $\lvert A\rvert^k$ many integers which are either the sum or product of distinct elements of $A$?
Asked by Erdős and Szemerédi [ErSz83]. Solved in this form by Chang [Ch03].

Erdős and Szemerédi proved that there exist arbitrarily large sets $A$ such that the integers which are the sum or product of distinct elements of $A$ is at most \[\exp\left(c (\log \lvert A\rvert)^2\log\log\lvert A\rvert\right)\] for some constant $c>0$.

See also [52].

OPEN - $500
Is there $A\subseteq \mathbb{N}$ such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is $\neq 0$?
A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.
SOLVED - $500
If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $d,m\geq 1$ such that \[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\]
The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when $f$ takes values on the unit sphere.

In [Er81] it is further conjectured that \[\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.\]

In [Er85c] Erdős also asks about the special case when $f$ is multiplicative.

OPEN
Is \[\sum_{n\geq 2}\frac{\omega(n)}{2^n}\] irrational? (Here $\omega(n)$ counts the number of distinct prime divisors of $n$.)
Erdős [Er48] proved that $\sum_n \frac{d(n)}{2^n}$ is irrational, where $d(n)$ is the divisor function.

Pratt [Pr24] has proved this is irrational, conditional on a uniform version of the prime $k$-tuples conjecture.

Tao has observed that this is a special case of [257], since \[\sum_{n\geq 2}\frac{\omega(n)}{2^n}=\sum_p \frac{1}{2^p-1}.\]

Additional thanks to: Vjekoslav Kovac and Terence Tao
SOLVED
Any $A\subseteq \mathbb{N}$ of positive upper density contains a sumset $B+C$ where both $B$ and $C$ are infinite.
The Erdős sumset conjecture. Proved by Moreira, Richter, and Robertson [MRR19].
Additional thanks to: Antonio Girao
OPEN
Let $k\geq 3$. Can the product of any $k$ consecutive integers $N$ ever be powerful? That is, must there always exist a prime $p\mid N$ such that $p^2\nmid N$?
Conjectured by Erdős and Selfridge. There are infinitely many $n$ such that $n(n+1)$ is powerful (see [364]). Erdős and Selfridge proved that $N$ can never be a perfect power. Erdős remarked that this 'seems hopeless at present'.

In [Er82c] he further conjectures that, if $m,k$ are fixed and $n$ is sufficiently large, then there must be at least $k$ distinct primes $p$ such that \[p\mid m(m+1)\cdots (m+n)\] and yet $p^2$ does not divide the right-hand side.

See also [364].

Additional thanks to: Julius Schmerling
OPEN
Let the van der Waerden number $W(k)$ be such that whenever $N\geq W(k)$ and $\{1,\ldots,N\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $W(k)$ - for example, prove that $W(k)^{1/k}\to \infty$.
When $p$ is prime Berlekamp [Be68] has proved $W(p+1)\geq p2^p$. Gowers [Go01] has proved \[W(k) \leq 2^{2^{2^{2^{2^{k+9}}}}}.\]

In [Er81] Erdős further asks whether $W(k+1)/W(k)\to \infty$, or $W(k+1)-W(k)\to \infty$.

SOLVED - $500
Let $r_3(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $3$-term arithmetic progression. Prove that $r_3(N)\ll N/(\log N)^C$ for every $C>0$.
Proved by Kelley and Meka [KeMe23]. In [ErGr80] and [Er81] it is conjectured that this holds for every $k$-term arithmetic progression.

See also [3].

SOLVED - $250
The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.
In [Er79] asks the stronger version with $2$ replaced by any constant $c>1$.

The answer is yes (also to this stronger version), proved by Maier and Tenenbaum [MaTe84]. (Tenenbaum has told me that they received \$650 for their solution.)

See also [449] and [884].

OPEN
Let $F(k)$ be the number of solutions to \[ 1= \frac{1}{n_1}+\cdots+\frac{1}{n_k},\] where $1\leq n_1<\cdots<n_k$ are distinct integers. Find good estimates for $F(k)$.
The current best bounds known are \[2^{c^{\frac{k}{\log k}}}\leq F(k) \leq c_0^{(\frac{1}{5}+o(1))2^k},\] where $c>0$ is some absolute constant and $c_0=1.26408\cdots$ is the 'Vardi constant'. The lower bound is due to Konyagin [Ko14] and the upper bound to Elsholtz and Planitzer [ElPl21].
OPEN
Let $F(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain any set of the form $\{n,2n,3n\}$. What is \[ \lim_{N\to \infty}\frac{F(N)}{N}?\] Is this limit irrational?
This limit was proved to exist by Graham, Spencer, and Witsenhausen [GrSpWi77]. Similar questions can be asked for the density or upper density of infinite sets without such configurations.
Additional thanks to: Jonathan Chapman
OPEN
Let $k\geq 3$ and $f(k)$ be the supremum of $\sum_{n\in A}\frac{1}{n}$ as $A$ ranges over all sets of positive integers which do not contain a $k$-term arithmetic progression. Estimate $f(k)$.

Is \[\lim_{k\to \infty}\frac{f(k)}{\log W(k)}=\infty\] where $W(k)$ is the van der Waerden number?

Gerver [Ge77] has proved \[f(k) \geq (1+o(1))k\log k.\] It is trivial that \[\frac{f(k)}{\log W(k)}\geq \frac{1}{2},\] but improving the right-hand side to any constant $>1/2$ is open.
SOLVED
Is it true that for every $\epsilon>0$ and integer $t\geq 1$, if $N$ is sufficiently large and $A$ is a subset of $[t]^N$ of size at least $\epsilon t^N$ then $A$ must contain a combinatorial line $P$ (a set $P=\{p_1,\ldots,p_t\}$ where for each coordinate $1\leq j\leq t$ the $j$th coordinate of $p_i$ is either $i$ or constant).
The 'density Hales-Jewett' problem. This was proved by Furstenberg and Katznelson [FuKa91]. A new elementary proof, which gives quantitative bounds, was proved by the Polymath project [Po09].
OPEN
Is it true that in any finite colouring of $\mathbb{N}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour?
First asked by Hindman. Hindman [Hi80] has proved this is false (with 7 colours) if we ask for an infinite $A$.

Moreira [Mo17] has proved that in any finite colouring of $\mathbb{N}$ there exist $x,y$ such that $\{x,x+y,xy\}$ are all the same colour.

Alweiss [Al23] has proved that, in any finite colouring of $\mathbb{Q}\backslash \{0\}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour. Bowen and Sabok [BoSa22] had proved this earlier for the first non-trivial case of $\lvert A\rvert=2$.

Additional thanks to: Ryan Alweiss
OPEN
In any $2$-colouring of $\mathbb{R}^2$, for all but at most one triangle $T$, there is a monochromatic congruent copy of $T$.
For some colourings a single equilateral triangle has to be excluded, considering the colouring by alternating strips. Shader [Sh76] has proved this is true if we just consider a single right-angled triangle.
OPEN
A finite set $A\subset \mathbb{R}^n$ is called Ramsey if, for any $k\geq 1$, there exists some $d=d(A,k)$ such that in any $k$-colouring of $\mathbb{R}^d$ there exists a monochromatic copy of $A$. Characterise the Ramsey sets in $\mathbb{R}^n$.
Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS73] proved that every Ramsey set is 'spherical': it lies on the surface of some sphere. Graham has conjectured that every spherical set is Ramsey. Leader, Russell, and Walters [LRW12] have alternatively conjectured that a set is Ramsey if and only if it is 'subtransitive': it can be embedded in some higher-dimensional set on which rotations act transitively.

Sets known to be Ramsey include vertices of $k$-dimensional rectangles [EGMRSS73], non-degenerate simplices [FrRo90], trapezoids [Kr92], and regular polygons/polyhedra [Kr91].

SOLVED
Show that, for any $n\geq 5$, the binomial coefficient $\binom{2n}{n}$ is not squarefree.
It is easy to see that $4\mid \binom{2n}{n}$ except when $n=2^k$, and hence it suffices to prove this when $n$ is a power of $2$.

Proved by Sárkzözy [Sa85] for all sufficiently large $n$, and by Granville and Ramaré [GrRa96] for all $n\geq 5$.

More generally, if $f(n)$ is the largest integer such that, for some prime $p$, we have $p^{f(n)}$ dividing $\binom{2n}{n}$, then $f(n)$ should tend to infinity with $n$. Can one even disprove that $f(n)\gg \log n$?

OPEN
Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that \[ \left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell.\] Find good upper bounds for $N(k,\ell)$. Is it true that for any $c>0$ there exists some $C>1$ such that \[N(k,ck)\leq C^k?\] What about \[N(k,2)\leq C^k\] or \[N(k,\sqrt{k})\leq C^k?\]
Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then \[N(k,1)=2^t(k-1)+1.\] Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$. Probabilistic methods imply that, for every fixed constant $c>0$, we have $N(k,ck)>C_c^k$ for some $C_c>1$.
OPEN
Find the smallest $h(d)$ such that the following holds. There exists a function $f:\mathbb{N}\to\{-1,1\}$ such that, for every $d\geq 1$, \[\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),\] where $P_d$ ranges over all finite arithmetic progressions with common difference $d$.
Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.
Additional thanks to: Zach Hunter
SOLVED
Let $A_1,A_2,\ldots$ be an infinite collection of infinite sets of integers, say $A_i=\{a_{i1}<a_{i2}<\cdots\}$. Does there exist some $f:\mathbb{N}\to\{-1,1\}$ such that \[\max_{m, 1\leq i\leq d} \left\lvert \sum_{1\leq j\leq m} f(a_{ij})\right\rvert \ll_d 1\] for all $d\geq 1$?
Erdős remarks 'it seems certain that the answer is affirmative'. This was solved by Beck [Be81]. Recently Beck [Be17] proved that one can replace $\ll_d 1$ with $\ll d^{4+\epsilon}$ for any $\epsilon>0$.
Additional thanks to: Zach Hunter
SOLVED
Let $1\leq k<\ell$ be integers and define $F_k(N,\ell)$ to be minimal such that every set $A\subset \mathbb{N}$ of size $N$ which contains at least $F_k(N,\ell)$ many $k$-term arithmetic progressions must contain an $\ell$-term arithmetic progression. Find good upper bounds for $F_k(N,\ell)$. Is it true that \[F_3(N,4)=o(N^2)?\] Is it true that for every $\ell>3$ \[\lim_{N\to \infty}\frac{\log F_3(N,\ell)}{\log N}=2?\]
Erdős remarks the upper bound $o(N^2)$ is certainly false for $\ell >\epsilon \log N$. The answer is yes: Fox and Pohoata [FoPo20] have shown that, for all fixed $1\leq k<\ell$, \[F_k(N,\ell)=N^{2-o(1)}\] and in fact \[F_{k}(N,\ell) \leq \frac{N^2}{(\log\log N)^{C_\ell}}\] where $C_\ell>0$ is some constant. In fact, they show that, if $r_\ell(N)$ is the size of the largest subset of $\{1,\ldots,N\}$ without an $\ell$-term arithmetic progression then there exists some absolute constant $c>0$ such that \[\left(c \frac{r_\ell(N)}{N}\right)^{2(k-1)}N^2 < F_k(N,\ell) <\left(\frac{r_\ell(N)}{N}\right)^{O(1)}N^2.\] Any improved bounds for Szemerédi's theorem (see [139]) therefore yield improved bounds for $F_k(N,\ell)$. In particular, the bounds of Leng, Sah, and Sawhney [LSS24] imply \[F_k(N,\ell) \leq \frac{N^2}{\exp((\log\log N)^{c_\ell})}\] for some constant $c_\ell>0$.
Additional thanks to: Zach Hunter
SOLVED
Let $F(N)$ be the maximal size of $A\subseteq \{1,\ldots,N\}$ which is 'non-averaging', so that no $n\in A$ is the arithmetic mean of at least two elements in $A$. What is the order of growth of $F(N)$?
Originally due to Straus. It is known that \[N^{1/4}\ll F(N) \ll N^{1/4+o(1)}.\] The lower bound is due to Bosznay [Bo89] and the upper bound to Pham and Zakharov [PhZa24], improving an earlier bounds of Conlon, Fox, and Pham [CFP23]. The original upper bound of Erdős and Sárközy [ErSa90] was $\ll (N\log N)^{1/2}$).

See also [789].

Additional thanks to: Zachary Chase
OPEN
Find the best function $f(d)$ such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference $d$ of length $f(d)$ for infinitely many $d$.
Originally asked by Cohen. Erdős observed that colouring according to whether $\{ \sqrt{2}n\}<1/2$ or not implies $f(d) \ll d$ (using the fact that $\|\sqrt{2}q\| \gg 1/q$ for all $q$, where $\|x\|$ is the distance to the nearest integer). Beck [Be80] has improved this using the probabilistic method, constructing a colouring that shows $f(d)\leq (1+o(1))\log_2 d$. Van der Waerden's theorem implies $f(d)\to \infty$ is necessary.
Additional thanks to: Zach Hunter
OPEN
What is the smallest $k$ such that $\mathbb{R}^2$ can be red/blue coloured with no pair of red points unit distance apart, and no $k$-term arithmetic progression of blue points with distance $1$?
Juhász [Ju79] has shown that $k\geq 5$. Erdős and Graham claim that $k\leq 10000000$ ('more or less'), but give no proof.

Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.

It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).

Additional thanks to: Noga Alon
SOLVED
If $\mathbb{R}^2$ is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area?
Graham [Gr80] has shown that this is true if we replace rectangle by right-angled triangle. The same question can be asked for parallelograms. It is not true for rhombuses.

This is false; Kovač [Ko23] provides an explicit (and elegantly simple) colouring using 25 colours such that no colour class contains the vertices of a rectangle of area $1$. The question for parallelograms remains open.

Additional thanks to: Ryan Alweiss, Vjekoslav Kovac
OPEN
Let $H(k)$ be the smallest $N$ such that in any finite colouring of $\{1,\ldots,N\}$ (into any number of colours) there is always either a monochromatic $k$-term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate $H(k)$. Is it true that \[H(k)^{1/k}/k \to \infty\] as $k\to\infty$?
This type of problem belongs to 'canonical' Ramsey theory. The existence of $H(k)$ follows from Szemerédi's theorem, and it is easy to show that $H(k)^{1/k}\to\infty$.
SOLVED
Let $C>0$ be arbitrary. Is it true that, if $n$ is sufficiently large depending on $C$, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq C?\]
The answer is yes, which was proved by Rödl [Ro03].

In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]

This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]

Additional thanks to: Mehtaab Sawhney
SOLVED
Let $A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d$ be an infinite sequence such that $a_{i+1}-a_i$ is a positive unit vector (i.e. is of the form $(0,0,\ldots,1,0,\ldots,0)$). For which $d$ must $A$ contain a three-term arithmetic progression?
This is true for $d\leq 3$ and false for $d\geq 4$.

This problem is equivalent to one on 'abelian squares' (see [231]). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.

This problem is therefore equivalent to asking for which $d$ there exists an infinite string over $\{1,\ldots,d\}$ with no abelian squares. It is easy to check that in fact any finite string of length $7$ over $\{1,2,3\}$ contains an abelian square.

An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results, and a blog post by Renan for an entertaining and educational discussion.

Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN
Let $S\subseteq \mathbb{Z}^3$ be a finite set and let $A=\{a_1,a_2,\ldots,\}\subset \mathbb{Z}^3$ be an infinite $S$-walk, so that $a_{i+1}-a_i\in S$ for all $i$. Must $A$ contain three collinear points?
Originally conjectured by Gerver and Ramsey [GeRa79], who showed that the answer is yes for $\mathbb{Z}^2$, and for $\mathbb{Z}^3$ that the largest number of collinear points can be bounded.
Additional thanks to: Terence Tao
SOLVED
Let $k\geq 3$. Must any ordering of $\mathbb{R}$ contain a monotone $k$-term arithmetic progression, that is, some $x_1<\cdots<x_k$ which forms an increasing or decreasing $k$-term arithmetic progression?
The answer is no, even for $k=3$, as shown by Ardal, Brown, and Jungić [ABJ11].

See also [195] and [196].

OPEN
What is the smallest $k$ such that in any permutation of $\mathbb{Z}$ there must exist a monotone $k$-term arithmetic progression $x_1<\cdots<x_k$?
Geneson [Ge19] proved that $k\leq 5$. Adenwalla [Ad22] proved that $k\leq 4$.

See also [194] and [196].

Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN
Must every permutation of $\mathbb{N}$ contain a monotone 4-term arithmetic progression $x_1<x_2<x_3<x_4$?
Davis, Entringer, Graham, and Simmons [DEGS77] have shown that there must exist a monotone 3-term arithmetic progression and need not contain a 5-term arithmetic progression.

See also [194] and [195].

Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN
Can $\mathbb{N}$ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
If three sets are allowed then this is possible.
Additional thanks to: Boris Alexeev and Dustin Mixon
SOLVED
If $A\subset \mathbb{N}$ is a Sidon set then must the complement of $A$ contain an infinite arithmetic progression?
The answer is yes, as shown by Baumgartner [Ba75].
SOLVED
If $A\subset \mathbb{R}$ does not contain a 3-term arithmetic progression then must $\mathbb{R}\backslash A$ contain an infinite arithmetic progression?
The answer is no, as shown by Baumgartner [Ba75] (whose construction uses the axiom of choice).
OPEN
Does the longest arithmetic progression of primes in $\{1,\ldots,N\}$ have length $o(\log N)$?
It follows from the prime number theorem that such a progression has length $\leq(1+o(1))\log N$.
OPEN
Let $G_k(N)$ be such that any set of $N$ integers contains a subset of size at least $G_k(N)$ which does not contain a $k$-term arithmetic progression. Determine the size of $G_k(N)$. How does it relate to $R_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a $k$-term arithmetic progression? Is it true that \[\lim_{N\to \infty}\frac{R_3(N)}{G_3(N)}=1?\]
First asked and investigated by Riddell [Ri69]. It is trivial that $G_k(N)\leq R_k(N)$, and it is possible that $G_k(N) <R_k(N)$ (for example with $k=3$ and $N=14$). Komlós, Sulyok, and Szemerédi [KSS75] have shown that $R_k(N) \ll_k G_k(N)$.
Additional thanks to: Zachary Chase
OPEN
Let $n_1<\cdots < n_r\leq N$ with associated $a_i\pmod{n_i}$ such that the congruence classes are disjoint (that is, every integer is $\equiv a_i\pmod{n_i}$ for at most one $1\leq i\leq r$). How large can $r$ be in terms of $N$?
Let $f(N)$ be the maximum possible $r$. Erdős and Stein conjectured that $f(N)=o(N)$, which was proved by Erdős and Szemerédi [ErSz68], who showed that, for every $\epsilon>0$, \[\frac{N}{\exp((\log N)^{1/2+\epsilon})} \ll_\epsilon f(N) < \frac{N}{(\log N)^c}\] for some $c>0$. Erdős believed the lower bound is closer to the truth.

These bounds were improved by Croot [Cr03b] who proved \[\frac{N}{L(N)^{\sqrt{2}+o(1)}}< f(N)<\frac{N}{L(N)^{1/6-o(1)}},\] where $f(N)=\exp(\sqrt{\log N\log\log N})$. These bounds were further improved by Chen [Ch05] and then by de la Bretéche, Ford, and Vandehey [BFV13] to \[\frac{N}{L(N)^{1+o(1)}}<f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}.\] The latter authors conjecture that the lower bound here is the truth.

OPEN
Is there an integer $m$ with $(m,6)=1$ such that none of $2^k3^\ell m+1$ are prime, for any $k,\ell\geq 0$?
There are odd integers $m$ such that none of $2^km+1$ are prime, which arise from covering systems (i.e. one shows that there exists some $n$ such that $(2^km+1,n)>1$ for all $k\geq 1$). Erdős and Graham also ask whether there is such an $m$ where a covering system is not 'responsible'. The answer is probably no since otherwise this would imply there are infinitely many Fermat primes of the form $2^{2^t}+1$.
SOLVED
Are there $n$ such that there is a covering system with moduli the divisors of $n$ which is 'as disjoint as possible'?

That is, for all $d\mid n$ with $d>1$ there is an associated $a_d$ such that every integer is congruent to some $a_d\pmod{d}$, and if there is some integer $x$ with \[x\equiv a_d\pmod{d}\textrm{ and }x\equiv a_{d'}\pmod{d'}\] then $(d,d')=1$.

The density of such $n$ is zero. Erdős and Graham believed that no such $n$ exist.

Adenwalla [Ad25] has proved there are no such $n$.

In general, for any $n$ one can try to choose such $a_d$ to maximise the density of integers so covered, and ask what this density is. This was also investigated by Adenwalla [Ad25].

Additional thanks to: Sarosh Adenwalla
OPEN
Is it true that all sufficiently large $n$ can be written as $2^k+m$ for some $k\geq 0$, where $\Omega(m)<\log\log m$? (Here $\Omega(m)$ is the number of prime divisors of $m$ counted with multiplicity.) What about $<\epsilon \log\log m$? Or some more slowly growing function?
It is easy to see by probabilistic methods that this holds for almost all integers. Romanoff [Ro34] showed that a positive density set of integers are representable as the sum of $2^k+p$ for prime $p$, and Erdős used covering systems to show that there is a positive density set of odd integers which cannot be so represented.

See also [851].

SOLVED
Let $x>0$ be a real number. For any $n\geq 1$ let \[R_n(x) = \sum_{i=1}^n\frac{1}{m_i}<x\] be the maximal sum of $n$ distinct unit fractions which is $<x$.

Is it true that, for almost all $x$, for sufficiently large $n$, we have \[R_{n+1}(x)=R_n(x)+\frac{1}{m},\] where $m$ is minimal such that $m$ does not appear in $R_n(x)$ and the right-hand side is $<x$? (That is, are the best underapproximations eventually always constructed in a 'greedy' fashion?)

Erdős and Graham write it is 'not difficult' to construct irrational $x$ such that this fails (although give no proof or reference, and it seems to still be an open problem to actually construct some such irrational $x$). Curtiss [Cu22] showed that this is true for $x=1$ and Erdős [Er50b] showed it is true for all $x=1/m$ with $m\geq 1$. Nathanson [Na23] has shown it is true for $x=a/b$ when $a\mid b+1$ and Chu [Ch23b] has shown it is true for a larger class of rationals; it is still unknown whether this is true for all rational $x>0$.

Without the 'eventually' condition this can fail for some rational $x$ (although Erdős [Er50b] showed it holds without the eventually for rationals of the form $1/m$). For example \[R_1(\tfrac{11}{24})=\frac{1}{3}\] but \[R_2(\tfrac{11}{24})=\frac{1}{4}+\frac{1}{5}.\]

Kovač [Ko24b] has proved that this is false - in fact as false as possible: the set of $x\in (0,\infty)$ for which the best underapproximations are eventually 'greedy' has Lebesgue measure zero. (It remains an open problem to give any explicit example of a number which is not eventually greedy, despite the fact that almost all numbers have this property.)

Additional thanks to: Vjekoslav Kovac
SOLVED - $500
Let $n\geq 1$ and \[A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.\] Is it true that \[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?\]
The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact found the correct order of magnitude with the power $2$ replaced by any $\gamma\geq 1$ (which was also asked by Erdős in [Er73]).
OPEN - $100
Let $f(N)$ be the maximum size of $A\subseteq \{1,\ldots,N\}$ such that the sums $a+b+c$ with $a,b,c\in A$ are all distinct (aside from the trivial coincidences). Is it true that \[ f(N)\sim N^{1/3}?\]
Originally asked to Erdős by Bose. Bose and Chowla [BoCh62] provided a construction proving one half of this, namely \[(1+o(1))N^{1/3}\leq f(N).\] The best upper bound known to date is due to Green [Gr01], \[f(N) \leq ((7/2)^{1/3}+o(1))N^{1/3}\] (note that $(7/2)^{1/3}\approx 1.519\cdots$).

More generally, Bose and Chowla conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then \[\lvert A\rvert \sim N^{1/r}.\] This is known only for $r=2$ (see [30]).

Additional thanks to: Cedric Pilatte
OPEN
For every $n>2$ there exist distinct integers $1\leq x<y<z$ such that \[\frac{4}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.\]
The Erdős-Straus conjecture. The existence of a representation of $4/n$ as the sum of at most four distinct unit fractions follows trivially from a greedy algorithm.

Schinzel conjectured the generalisation that, for any fixed $a$, if $n$ is sufficiently large in terms of $a$ then there exist distinct integers $1\leq x<y<z$ such that \[\frac{a}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.\]

OPEN
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.\]
A sequence defined in such a fashion is known as Sylvester's sequence.
SOLVED
Let $A\subseteq \mathbb{N}$ be an infinite set such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that \[\limsup_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}\geq 3?\]
Erdős writes it is 'easy to see' that this holds with $3$ replaced by $2$, and that $3$ would be best possible here. We do not see an easy argument that this holds with $2$, but this follows e.g. from the main result of Mann [Ma60].

The answer is yes, proved by Freiman [Fr73].

See also [899] for the difference set analogue.

Additional thanks to: Zachary Chase
OPEN
Let $n_1<n_2<\cdots$ be a sequence of integers such that \[\limsup \frac{n_k}{k}=\infty.\] Is \[\sum_{k=1}^\infty \frac{1}{2^{n_k}}\] transcendental?
Erdős [Er75c] proved the answer is yes under the stronger condition that $\limsup n_k/k^t=\infty$ for all $t\geq 1$.
OPEN
Are there infinitely many $n$ such that, for all $k\geq 1$, \[ \omega(n+k) \ll k?\] (Here $\omega(n)$ is the number of distinct prime divisors of $n$.)
Related to [69]. Erdős and Graham [ErGr80] write 'we just know too little about sieves to be able to handle such a question ("we" here means not just us but the collective wisdom (?) of our poor struggling human race).'

See also [679] and [827].

OPEN
Is \[\sum_n \frac{\phi(n)}{2^n}\] irrational? Here $\phi$ is the Euler totient function.
The decimal expansion of this sum is A256936 on the OEIS.
SOLVED
Is \[\sum \frac{\sigma(n)}{2^n}\] irrational? (Here $\sigma(n)$ is the sum of divisors function.)
The answer is yes, as shown by Nesterenko [Ne96].
OPEN
Is \[\sum \frac{p_n}{2^n}\] irrational? (Here $p_n$ is the $n$th prime.)
The decimal expansion of this sum is A098990 on the OEIS.
OPEN
Let $k\geq 1$ and $\sigma_k(n)=\sum_{d\mid n}d^k$. Is \[\sum \frac{\sigma_k(n)}{n!}\] irrational?
This is known now for $1\leq k\leq 4$. The cases $k=1,2$ are reasonably straightforward, as observed by Erdős [Er52]. The case $k=3$ was proved independently by Schlage-Puchta [ScPu06] and Friedlander, Luca, and Stoiciu [FLC07]. The case $k=4$ was proved by Pratt [Pr22].
OPEN
Let $A\subseteq \mathbb{N}$ be an infinite set. Is \[\sum_{n\in A}\frac{1}{2^n-1}\] irrational?
If $A=\mathbb{N}$ then this series is $\sum_{n}\frac{d(n)}{2^n}$, where $d(n)$ is the number of divisors of $n$, which Erdős [Er48] proved is irrational.

The case when $A$ is the set of primes is [69].

OPEN
Let $a_n\to \infty$. Is \[\sum_{n} \frac{d(n)}{a_1\cdots a_n}\] irrational, where $d(n)$ is the number of divisors of $n$?
Erdős and Straus [ErSt71] have proved this is true if $a_n$ is monotone, i.e. $a_{n-1}\leq a_n$ for all $n$. Erdős [Er48] proved that $\sum_n \frac{d(n)}{t^n}$ is irrational for any integer $t\geq 2$.
OPEN
Is the sum \[\sum_{n} \mu(n)^2\frac{n}{2^n}\] irrational?
Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN
Let $a_n$ be a sequence such that $a_n/n\to \infty$. Is the sum \[\sum_n \frac{a_n}{2^{a_n}}\] irrational?
This is true under either of the stronger assumptions that
  • $a_{n+1}-a_n\to \infty$ or
  • $a_n \gg n\sqrt{\log n\log\log n}$.
Erdős and Graham speculate that the condition $\limsup a_{n+1}-a_n=\infty$ is not sufficient, but know of no example.
OPEN
Are there infinitely many $n$ such that there exists some $t\geq 2$ and $a_1,\ldots,a_t\geq 1$ such that \[\frac{n}{2^n}=\sum_{1\leq k\leq t}\frac{a_k}{2^{a_k}}?\] Is this true for all $n$? Is there a rational $x$ such that \[x = \sum_{k=1}^\infty \frac{a_k}{2^{a_k}}\] has at least $2^{\aleph_0}$ solutions?
Related to [260].

In [Er88c] Erdős notes that Cusick had a simple proof that there do exist infinitely many such $n$. Erdődoes not record what this was, but Kovač has provided the following proof: for every positive integer $m$ and $n=2^{m+1}-m-2$ we have \[\frac{n}{2^n}=\sum_{n<k\leq n+m}\frac{k}{2^k}.\]

Additional thanks to: Zachary Chase and Vjekoslav Kovac
SOLVED
Suppose $a_1<a_2<\cdots$ is a sequence of integers such that for all integer sequences $t_n$ with $t_n\geq 1$ the sum \[\sum_{n=1}^\infty \frac{1}{t_na_n}\] is irrational. How slowly can $a_n$ grow?
One possible definition of an 'irrationality sequence' (see also [263] and [264]). An example of such a sequence is $a_n=2^{2^n}$, while a non-example is $a_n=n!$. It is known that if $a_n$ is such a sequence then $a_n^{1/n}\to\infty$.

This was essentially solved by Hančl [Ha91], who proved that such a sequence needs to satisfy \[\limsup_{n\to \infty} \frac{\log_2\log_2 a_n}{n} \geq 1.\] More generally, if $a_n\ll 2^{2^{n-F(n)}}$ with $F(n)<n$ and $\sum 2^{-F(n)}<\infty$ then $a_n$ cannot be an irrationality sequence.

Additional thanks to: Vjekoslav Kovac and Terence Tao
OPEN
Let $a_n$ be a sequence of integers such that for every sequence of integers $b_n$ with $b_n/a_n\to 1$ the sum \[\sum\frac{1}{b_n}\] is irrational. Is $a_n=2^{2^n}$ such a sequence? Must such a sequence satisfy $a_n^{1/n}\to \infty$?
One possible definition of an 'irrationality sequence' (see also [262] and [264]). A folklore result states that $\sum \frac{1}{a_n}$ is irrational whenever $\lim a_n^{1/2^n}=\infty$.

Kovač and Tao [KoTa24] have proved that any strictly increasing sequence such that $\sum \frac{1}{a_n}$ converges and $\lim a_{n+1}/a_n^2=0$ is not such an irrationality sequence. On the other hand, if \[\liminf \frac{a_{n+1}}{a_n^{2+\epsilon}}>0\] for some $\epsilon>0$ then the above folklore result implies that $a_n$ is such an irrationality sequence.

OPEN
Let $a_n$ be a sequence of integers such that for every bounded sequence of integers $b_n$ (with $a_n+b_n\neq 0$ and $b_n\neq 0$ for all $n$) the sum \[\sum \frac{1}{a_n+b_n}\] is irrational. Are $a_n=2^n$ or $a_n=n!$ examples of such a sequence?
A possible definition of an 'irrationality sequence' (see also [262] and [263]). One example is $a_n=2^{2^n}$. In [ErGr80] they also ask whether such a sequence can have polynomial growth, but Erdős later retracted this in [Er88c], claiming 'It is not hard to show that it cannot increase slower than exponentially'.

Kovač and Tao [KoTa24c] have proved that $2^n$ is not such an irrationality sequence. More generally, they prove that any strictly increasing sequence of positive integers such that $\sum\frac{1}{a_n}$ converges and \[\liminf \left(a_n^2\sum_{k>n}\frac{1}{a_k^2}\right) >0 \] is not such an irrationality sequence. In particular, any strictly increasing sequence with $\limsup a_{n+1}/a_n <\infty$ is not such an irrationality sequence.

On the other hand, Kovač and Tao do prove that for any function $F$ with $\lim F(n+1)/F(n)=\infty$ there exists such an irrationality sequence with $a_n\sim F(n)$.

Additional thanks to: Vjekoslav Kovac
OPEN
How fast can $a_n\to \infty$ grow if \[\sum\frac{1}{a_n}\quad\textrm{and}\quad\sum\frac{1}{a_n-1}\] are both rational?
Cantor observed that $a_n=\binom{n}{2}$ is such a sequence. If we replace $-1$ by a different constant then higher degree polynomials can be used - for example if we consider $\sum_{n\geq 2}\frac{1}{a_n}$ and $\sum_{n\geq 2}\frac{1}{a_n-12}$ then $a_n=n^3+6n^2+5n$ is an example of both series being rational.

Erdős believed that $a_n^{1/n}\to \infty$ is possible, but $a_n^{1/2^n}\to 1$ is necessary.

This has been almost completely solved by Kovač and Tao [KoTa24], who prove that such a sequence can grow doubly exponentially. More precisely, there exists such a sequence such that $a_n^{1/\beta^n}\to \infty$ for some $\beta >1$.

It remains open whether one can achieve \[\limsup a_n^{1/2^n}>1.\] A folklore result states that $\sum \frac{1}{a_n}$ is irrational whenever $\lim a_n^{1/2^n}=\infty$, and hence such a sequence cannot grow faster than doubly exponentially - the remaining question is the precise exponent possible.

Additional thanks to: Vjekoslav Kovac
SOLVED
Let $a_n$ be an infinite sequence of positive integers such that $\sum \frac{1}{a_n}$ converges. There exists some integer $t\geq 1$ such that \[\sum \frac{1}{a_n+t}\] is irrational.
This conjecture is due to Stolarsky.

A negative answer was proved by Kovač and Tao [KoTa24], who proved even more: there exists a strictly increasing sequence of positive integers $a_n$ such that \[\sum \frac{1}{a_n+t}\] converges to a rational number for every $t\in \mathbb{Q}$ (with $t\neq -a_n$ for all $n$).

OPEN
Let $F_1=F_2=1$ and $F_{n+1}=F_n+F_{n-1}$ be the Fibonacci sequence. Let $n_1<n_2<\cdots $ be an infinite sequence with $n_{k+1}/n_k \geq c>1$. Must \[\sum_k\frac{1}{F_{n_k}}\] be irrational?
It may be sufficient to have $n_k/k\to \infty$. Good [Go74] and Bicknell and Hoggatt [BiHo76] have shown that $\sum \frac{1}{F_{2^n}}$ is irrational.

The sum $\sum \frac{1}{F_n}$ itself was proved to be irrational by André-Jeannin [An89].

SOLVED
Let $X\subseteq \mathbb{R}^3$ be the set of all points of the shape \[\left( \sum_{n\in A} \frac{1}{n},\sum_{n\in A}\frac{1}{n+1},\sum_{n\in A} \frac{1}{n+2}\right) \] as $A\subseteq\mathbb{N}$ ranges over all infinite sets with $\sum_{n\in A}\frac{1}{n}<\infty$. Does $X$ contain an open set?
Erdős and Straus proved the answer is yes for the 2-dimensional version, where $X\subseteq \mathbb{R}^2$ is the set of \[\left( \sum_{n\in A} \frac{1}{n},\sum_{n\in A}\frac{1}{n+1}\right) \] as $A\subseteq\mathbb{N}$ ranges over all infinite sets with $\sum_{n\in A}\frac{1}{n}<\infty$.

The answer is yes, proved by Kovač [Ko24], who constructs an explicit open ball inside the set. Kovač and Tao [KoTa24] have proved an analogous result for all higher dimensions.

OPEN
Let $P$ be a finite set of primes with $\lvert P\rvert \geq 2$ and let $\{a_1<a_2<\cdots\}=\{ n\in \mathbb{N} : \textrm{if }p\mid n\textrm{ then }p\in P\}$. Is the sum \[\sum_{n=1}^\infty \frac{1}{[a_1,\ldots,a_n]},\] where $[a_1,\ldots,a_n]$ is the lowest common multiple of $a_1,\ldots,a_n$, rational or irrational?
If $P$ is infinite this sum is always irrational.
OPEN
Let $f(n)\to \infty$ as $n\to \infty$. Is it true that \[\sum_n \frac{1}{(n+1)\cdots (n+f(n))}\] is irrational?
Erdős and Graham write 'the answer is almost surely in the affirmative if $f(n)$ is assumed to be nondecreasing'. Even the case $f(n)=n$ is unknown, although Hansen [Ha75] has shown that \[\sum_n \frac{1}{\binom{2n}{n}}=\sum_n \frac{n!}{(n+1)\cdots (n+n)}=\frac{1}{3}+\frac{2\pi}{3^{5/2}}\] is transcendental.
OPEN
For any $n$, let $A(n)=\{0<n<\cdots\}$ be the infinite sequence with $a_0=0$ and $a_1=n$, and for $k\geq 1$ we define $a_{k+1}$ as the least integer such that there is no three-term arithmetic progression in $\{a_0,\ldots,a_{k+1}\}$.

Can the $a_k$ be explicitly determined? How fast do they grow?

It is easy to see that $A(1)$ is the set of integers which have no 2 in their base 3 expansion. Odlyzko and Stanley have found similar characterisations are known for $A(3^k)$ and $A(2\cdot 3^k)$ for any $k\geq 0$, see [OdSt78], and conjectured in general that such a sequence always eventually either satisfies \[a_k\asymp k^{\log_23}\] or \[a_k \asymp \frac{k^2}{\log k}.\] There is no known sequence which satisfies the second growth rate, but Lindhurst [Li90] gives data which suggests that $A(4)$ has such growth ($A(4)$ is given as A005487 in the OEIS).

Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$.

In general, sequences which begin with some initial segment and thereafter are continued in a greedy fashion to avoid three-term arithmetic progressions are known as Stanley sequences.

Additional thanks to: Ralf Stephan
OPEN
Let $N\geq 1$. What is the largest $t$ such that there are $A_1,\ldots,A_t\subseteq \{1,\ldots,N\}$ with $A_i\cap A_j$ a non-empty arithmetic progression for all $i\neq j$?
Simonovits and Sós [SiSo81] have shown that $t\ll N^2$. It is possible that the maximal $t$ is achieved when we take the $A_i$ to be all arithmetic progressions in $\{1,\ldots,N\}$ containing some fixed element.

If we drop the non-empty requirement then Simonovits, Sós, and Graham [SiSoGr80] have shown that \[t\leq \binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1\] and this is best possible.

Additional thanks to: Zachary Hunter
OPEN
Is there a covering system all of whose moduli are of the form $p-1$ for some primes $p\geq 5$?
Selfridge has found an example using divisors of $360$ if $p=3$ is allowed.
OPEN
If $G$ is an abelian group then can there exist an exact covering of $G$ by more than one cosets of different sizes? (i.e. each element is contained in exactly one of the cosets)
A problem of Herzog and Schönheim. In [Er97c] Erdős asks this for finite (not necessarily abelian) groups.
Additional thanks to: Boris Alexeev and Dustin Mixon
SOLVED
If a finite system of $r$ congruences $\{ a_i\pmod{n_i} : 1\leq i\leq r\}$ covers $2^r$ consecutive integers then it covers all integers.
This is best possible as the system $2^{i-1}\pmod{2^i}$ shows. This was proved indepedently by Selfridge and Crittenden and Vanden Eynden [CrVE70].
OPEN
Is there an infinite Lucas sequence $a_0,a_1,\ldots,$ where $(a_0,a_1)=1$ and $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$ such that all $a_k$ are composite, and yet no integer has a common factor with every term of the sequence?
Whether such a composite Lucas sequence even exists was open for a while, but using covering systems Graham [Gr64] showed that \[a_0 = 1786772701928802632268715130455793\] \[a_1 = 1059683225053915111058165141686995\] generate such a sequence. This problem asks whether one can have a composite Lucas sequence without 'an underlying system of covering congruences responsible'.
OPEN
Let $A=\{n_1<\cdots<n_r\}$ be a finite set of integers. What is the maximum density of integers covered by a suitable choice of congruences $a_i\pmod{n_i}$?

Is the minimum density achieved when all the $a_i$ are equal?

Simpson [Si86] has observed that the density of integers covered is at least \[\sum_i \frac{1}{n_i}-\sum_{i<j}\frac{1}{[n_i,n_j]}+\sum_{i<j<k}\frac{1}{[n_i,n_j,n_k]}-\cdot\] (where $[\cdots]$ denotes the least common multiple) which is achieved when all $a_i$ are equal, settling the second question.
Additional thanks to: Sarosh Adenwalla
OPEN
Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$ for every prime $p$ such that all except finitely many integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?
Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that \[\lvert A\cap [1,N]\rvert \gg N/\log N\] and \[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\] as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

OPEN
Let $n_1<n_2<\cdots $ be an infinite sequence of integers with associated $a_i\pmod{n_i}$, such that for some $\epsilon>0$ we have $n_k>(1+\epsilon)k\log k$ for all $k$. Then \[\#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for }1\leq i\leq k\}\neq o(k).\]
Erdős and Graham [ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).

Note that since the $k$th prime is $\sim k\log k$ the lower bound $n_k>(1+\epsilon)k\log k$ is best possible here.

OPEN
Let $n_1<n_2<\cdots$ be an infinite sequence such that, for any choice of congruence classes $a_i\pmod{n_i}$, the set of integers not satisfying any of the congruences $a_i\pmod{n_i}$ has density $0$.

Is it true that for every $\epsilon>0$ there exists some $k$ such that, for every choice of congruence classes $a_i$, the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?

The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$. If the $n_i$ are pairwise relatively prime then it is sufficient that $\sum \frac{1}{n_i}=\infty$.
Additional thanks to: Sarosh Adenwalla
OPEN
Let $A\subseteq \mathbb{N}$ be an infinite set and consider the following greedy algorithm for a rational $x\in (0,1)$: choose the minimal $n\in A$ such that $n\geq 1/x$ and repeat with $x$ replaced by $x-\frac{1}{n}$. If this terminates after finitely many steps then this produces a representation of $x$ as the sum of distinct unit fractions with denominators from $A$.

Does this process always terminate if $x$ has odd denominator and $A$ is the set of odd numbers? More generally, for which pairs $x$ and $A$ does this process terminate?

In 1202 Fibonacci observed that this process terminates for any $x$ when $A=\mathbb{N}$. The problem when $A$ is the set of odd numbers is due to Stein.

Graham [Gr64b] has shown that $\frac{m}{n}$ is the sum of distinct unit fractions with denominators $\equiv a\pmod{d}$ if and only if \[\left(\frac{n}{(n,(a,d))},\frac{d}{(a,d)}\right)=1.\] Does the greedy algorithm always terminate in such cases?

Graham [Gr64c] has also shown that $x$ is the sum of distinct unit fractions with square denominators if and only if $x\in [0,\pi^2/6-1)\cup [1,\pi^2/6)$. Does the greedy algorithm for this always terminate? Erdős and Graham believe not - indeed, perhaps it fails to terminate almost always.

Additional thanks to: Zachary Hunter
OPEN
Let $p:\mathbb{Z}\to \mathbb{Z}$ be a polynomial whose leading coefficient is positive and such that there exists no $d\geq 2$ with $d\mid p(n)$ for all $n\geq 1$. Is it true that, for all sufficiently large $m$, there exist integers $1\leq n_1<\cdots <n_k$ such that \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\] and \[m=p(n_1)+\cdots+p(n_k)?\]
Graham [Gr63] has proved this when $p(x)=x$. Cassels [Ca60] has proved that these conditions on the polynomial imply every sufficiently large integer is the sum of $p(n_i)$ with distinct $n_i$. Burr has proved this if $p(x)=x^k$ with $k\geq 1$ and if we allow $n_i=n_j$.

Alekseyev [Al19] has proved this when $p(x)=x^2$, for all $m>8542$. For example, \[1=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}\] and \[200 = 2^2+4^2+6^2+12^2.\]

Additional thanks to: Wouter van Doorn
SOLVED
Let $f(k)$ be the maximal value of $n_1$ such that there exist $n_1<n_2<\cdots <n_k$ with \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Is it true that \[f(k)=(1+o(1))\frac{k}{e-1}?\]
The upper bound $f(k) \leq (1+o(1))\frac{k}{e-1}$ is trivial since for any $u\geq 1$ we have \[\sum_{u\leq n\leq eu}\frac{1}{n}=1+o(1),\] and hence if $f(k)=u$ then we must have $k\geq (e-1-o(1))u$. Essentially solved by Croot [Cr01], who showed that for any $N>1$ there exists some $k\geq 1$ and \[N<n_1<\cdots <n_k \leq (e+o(1))N\] with $1=\sum \frac{1}{n_i}$.
Additional thanks to: Zachary Hunter
SOLVED
Let $f(k)$ be the minimal value of $n_k$ such that there exist $n_1<n_2<\cdots <n_k$ with \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Is it true that \[f(k)=(1+o(1))\frac{e}{e-1}k?\]
It is trivial that $f(k)\geq (1+o(1))\frac{e}{e-1}k$, since for any $u\geq 1$ \[\sum_{e\leq n\leq eu}\frac{1}{n}= 1+o(1),\] and so if $eu\approx f(k)$ then $k\leq \frac{e-1}{e}f(k)$. Proved by Martin [Ma00].
Additional thanks to: Zachary Hunter
SOLVED
Let $k\geq 2$. Is it true that there exists an interval $I$ of width $(e-1+o(1))k$ and integers $n_1<\cdots<n_k\in I$ such that \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}?\]
The answer is yes, proved by Croot [Cr01].
OPEN
Let $k\geq 2$. Is it true that, for any distinct integers $n_1<\cdots <n_k$ such that \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\] we must have $\max(n_{i+1}-n_i)\geq 3$?
The example $1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$ shows that $3$ would be best possible here. The lower bound of $\geq 2$ is equivalent to saying that $1$ is not the sum of reciprocals of consecutive integers, proved by Erdős [Er32].

This conjecture would follow for all but at most finitely many exceptions if it were known that, for all large $N$, there exists a prime $p\in [N,2N]$ such that $\frac{p+1}{2}$ is also prime.

OPEN
Is it true that there are only finitely many pairs of intervals $I_1,I_2$ such that \[\sum_{n_1\in I_1}\frac{1}{n_1}+\sum_{n_2\in I_2}\frac{1}{n_2}\in \mathbb{N}?\]
For example, \[\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{20}=1.\] This is still open even if $\lvert I_2\rvert=1$. It is perhaps true with two intervals replaced by any $k$ intervals.
Additional thanks to: Bhavik Mehta
OPEN
Is it true that, for all sufficiently large $k$, there exist finite intervals $I_1,\ldots,I_k\subset \mathbb{N}$ with $\lvert I_i\rvert \geq 2$ for $1\leq i\leq k$ such that \[1=\sum_{i=1}^k \sum_{n\in I_i}\frac{1}{n}?\]
SOLVED
Let $a\geq 1$. Must there exist some $b>a$ such that \[\sum_{a\leq n\leq b}\frac{1}{n}=\frac{r_1}{s_1}\textrm{ and }\sum_{a\leq n\leq b+1}\frac{1}{n}=\frac{r_2}{s_2},\] with $(r_i,s_i)=1$ and $s_2<s_1$? If so, how does this $b(a)$ grow with $a$?
For example, \[\sum_{3\leq n\leq 5}\frac{1}{n} = \frac{47}{60}\textrm{ and }\sum_{3\leq n\leq 6}\frac{1}{n}=\frac{19}{20}.\]

The smallest $b$ for each $a$ are listed at A375081 at the OEIS.

This was resolved in the affirmative by van Doorn [vD24], who proved $b=b(a)$ always exists, and in fact $b(a) \ll a$. Indeed, if $a\in (3^k,3^{k+1}]$ then one can take $b=2\cdot 3^{k+1}-1$. van Doorn also proves that $b(a)>a+(1/2-o(1))\log a$, and considers various generalisations of the original problem.

It seems likely that $b(a)\leq (1+o(1))a$, and perhaps even $b(a)\leq a+(\log a)^{O(1)}$.

Additional thanks to: Ralf Stephan and Wouter van Doorn
OPEN
Let $n\geq 1$ and define $L_n$ to be the least common multiple of $\{1,\ldots,n\}$ and $a_n$ by \[\sum_{1\leq k\leq n}\frac{1}{k}=\frac{a_n}{L_n}.\] Is it true that $(a_n,L_n)=1$ and $(a_n,L_n)>1$ both occur for infinitely many $n$?
Steinerberger has observed that the answer to the second question is trivially yes: for example, any $n$ which begins with a $2$ in base $3$ has $3\mid (a_n,L_n)$.

More generally, if the leading digit of $n$ in base $p$ is $p-1$ then $p\mid (a_n,L_n)$. There is in fact a necessary and sufficient condition: a prime $p\leq n$ divides $(a_n,L_n)$ if and only if $p$ divides the numerator of $1+\cdots+\frac{1}{k}$, where $k$ is the leading digit of $n$ in base $p$. This can be seen by writing \[a_n = \frac{L_n}{1}+\cdots+\frac{L_n}{n}\] and observing that the right-hand side is congruent to $1+\cdots+1/k$ modulo $p$. (The previous claim about $p-1$ follows immediately from Wolstenholme's theorem.)

This leads to a heuristic prediction (see for example a preprint of Shiu [Sh16]) of $\asymp\frac{x}{\log x}$ for the number of $n\in [1,x]$ such that $(a_n,L_n)=1$. In particular, there should be infinitely many $n$, but the set of such $n$ should have density zero. Unfortunately this heuristic is difficult to turn into a proof.

Additional thanks to: Stefan Steinerberger
SOLVED
Let $A$ be the set of $n\in \mathbb{N}$ such that there exist $1\leq m_1<\cdots <m_k=n$ with $\sum\tfrac{1}{m_i}=1$. Explore $A$. In particular, does $A$ have density $1$?
Straus observed that $A$ is closed under multiplication. Furthermore, it is easy to see that $A$ does not contain any prime power.

The answer is yes, as proved by Martin [Ma00], who in fact proved that if $B=\mathbb{N}\backslash A$ then, for all large $x$, \[\frac{\lvert B\cap [1,x]\rvert}{x}\asymp \frac{\log\log x}{\log x},\] and also gave an essentially complete description of $B$ as those integers which are small multiples of prime powers.

van Doorn has observed that if $n\in A$ (with $n>1$) then $2n\in A$ also, since if $\sum \frac{1}{m_i}=1$ then $\frac{1}{2}+\sum\frac{1}{2m_i}=1$ also.

Additional thanks to: Zach Hunter and Wouter van Doorn
OPEN
Let $k\geq 1$ and let $v(k)$ be the minimal integer which does not appear as some $n_i$ in a solution to \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\] with $1\leq n_1<\cdots <n_k$. Estimate the growth of $v(k)$.
Results of Bleicher and Erdős [BlEr75] imply $v(k) \gg k!$. It may be that $v(k)$ grows doubly exponentially in $\sqrt{k}$ or even $k$.

An elementary inductive argument shows that $n_k\leq ku_k$ where $u_1=1$ and $u_{i+1}=u_i(u_i+1)$, and hence \[v(k) \leq kc_0^{2^k},\] where \[c_0=\lim_n u_n^{1/2^n}=1.26408\cdots\] is the 'Vardi constant'.

Additional thanks to: Zachary Hunter
SOLVED
Let $N\geq 1$ and let $t(N)$ be the least integer $t$ such that there is no solution to \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\] with $t=n_1<\cdots <n_k\leq N$. Estimate $t(N)$.
Erdős and Graham [ErGr80] could show \[t(N)\ll\frac{N}{\log N},\] but had no idea of the true value of $t(N)$.

Solved by Liu and Sawhney [LiSa24] (up to $(\log\log N)^{O(1)}$), who proved that \[\frac{N}{(\log N)(\log\log N)^3(\log\log\log N)^{O(1)}}\ll t(N) \ll \frac{N}{\log N}.\]

OPEN
Let $N\geq 1$ and let $k(N)$ denote the smallest $k$ such that there exist $N\leq n_1<\cdots <n_k$ with \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Is it true that \[\lim_{N\to \infty} k(N)-(e-1)N=\infty?\]
Erdős and Straus [ErSt71b] have proved the existence of some constant $c>0$ such that \[-c < k(N)-(e-1)N \ll \frac{N}{\log N}.\]
SOLVED
Let $N\geq 1$ and let $k(N)$ be maximal such that there are $k$ disjoint $A_1,\ldots,A_k\subseteq \{1,\ldots,N\}$ with $\sum_{n\in A_i}\frac{1}{n}=1$ for all $i$. Estimate $k(N)$. Is it true that $k(N)=o(\log N)$?
More generally, how many disjoint $A_i$ can be found in $\{1,\ldots,N\}$ such that the sums $\sum_{n\in A_i}\frac{1}{n}$ are all equal? Using sunflowers it can be shown that there are at least $N\exp(-O(\sqrt{\log N}))$ such sets.

Hunter and Sawhney have observed that Theorem 3 of Bloom [Bl21] (coupled with the trivial greedy approach) implies that $k(N)=(1-o(1))\log N$.

Additional thanks to: Zachary Hunter and Mehtaab Sawhney
SOLVED
Let $N\geq 1$. How many $A\subseteq \{1,\ldots,N\}$ are there such that $\sum_{n\in A}\frac{1}{n}=1$?
It was not even known for a long time whether this is $2^{cN}$ for some $c<1$ or $2^{(1+o(1))N}$. In fact the former is true, and the correct value of $c$ is now known.
  • Steinerberger [St24] proved the relevant count is at most $2^{0.93N}$;
  • Independently, Liu and Sawhney [LiSa24] gave both upper and lower bounds, proving that the count is \[2^{(0.91\cdots+o(1))N},\] where $0.91\cdots$ is an explicit number defined as the solution to a certain integral equation;
  • Again independently this same asymptotic was proved (with a different proof) by Conlon, Fox, He, Mubayi, Pham, Suk, and Verstraëte [CFHMPSV24], who prove more generally, for any $x\in \mathbb{Q}_{>0}$, a similar expression for the number of $A\subseteq \{1,\ldots,N\}$ such that $\sum_{n\in A}\frac{1}{n}=x$;
  • The above papers all appeared within weeks of each other in 2024; in 2017 a similar question (with $\leq 1$ rather than $=1$) was asked on MathOverflow by Mikhail Tikhomirov and proofs of the correct asymptotic were sketched by Lucia, RaphaelB4, and js21.
Additional thanks to: Zachary Chase
SOLVED
Does every set $A\subseteq \mathbb{N}$ of positive density contain some finite $S\subset A$ such that $\sum_{n\in S}\frac{1}{n}=1$?
The answer is yes, proved by Bloom [Bl21].

See also [46] and [47].

SOLVED
Is there an infinite sequence $a_1<a_2<\cdots $ such that $a_{i+1}-a_i=O(1)$ and no finite sum of $\frac{1}{a_i}$ is equal to $1$?
There does not exist such a sequence, which follows from the positive solution to [298] by Bloom [Bl21].
SOLVED
Let $A(N)$ denote the maximal cardinality of $A\subseteq \{1,\ldots,N\}$ such that $\sum_{n\in S}\frac{1}{n}\neq 1$ for all $S\subseteq A$. Estimate $A(N)$.
Erdős and Graham believe the answer is $A(N)=(1+o(1))N$. Croot [Cr03] disproved this, showing the existence of some constant $c<1$ such that $A(N)<cN$ for all large $N$. It is trivial that $A(N)\geq (1-\frac{1}{e}+o(1))N$.

Liu and Sawhney [LiSa24] have proved that $A(N)=(1-1/e+o(1))N$.

Additional thanks to: Zachary Hunter
OPEN
Let $f(N)$ be the size of the largest $A\subseteq \{1,\ldots,N\}$ such that there are no solutions to \[\frac{1}{a}\neq \frac{1}{b_1}+\cdots+\frac{1}{b_k}\] with distinct $a,b_1,\ldots,b_k\in A$?

Estimate $f(N)$. In particular, is $f(N)=(\tfrac{1}{2}+o(1))N$?

The example $A=(N/2,N]\cap \mathbb{N}$ shows that $f(N)\geq N/2$.

Wouter van Doorn has given an elementary argument that proves \[f(N)\leq (25/28+o(1))N.\] Indeed, consider the sets $S_a=\{2a,3a,4a,6a,12a\}\cap [1,N]$ as $a$ ranges over all integers of the form $8^b9^cd$ with $(d,6)=1$. All such $S_a$ are disjoint and, if $A$ has no solutions to the given equation, then $A$ must omit at least two elements of $S_a$ when $a\leq N/12$ and at least one element of $S_a$ when $N/12<a\leq N/6$, and an elementary calculation concludes the proof.

Stijn Cambie and Wouter van Doorn have proved that, if we allow solutions to this equation with non-distinct $b_i$, then the size of the maximal set is at most $N/2$. Indeed, this is the classical threshold for the existence of some distinct $a,b\in A$ such that $a\mid b$.

See also [302] and [327].

Additional thanks to: Stijn Cambie, Zach Hunter, and Wouter van Doorn
OPEN
Let $f(N)$ be the size of the largest $A\subseteq \{1,\ldots,N\}$ such that there are no solutions to \[\frac{1}{a}\neq \frac{1}{b}+\frac{1}{c}\] with distinct $a,b,c\in A$?

Estimate $f(N)$. In particular, is $f(N)=(\tfrac{1}{2}+o(1))N$?

The colouring version of this is [303], which was solved by Brown and Rödl [BrRo91]. One can take either $A$ to be all odd integers in $[1,N]$ or all integers in $[N/2,N]$ to show $f(N)\geq (1/2+o(1))N$.

Wouter van Doorn has proved, in an unpublished note, that \[f(N) \leq (9/10+o(1))N.\] Stijn Cambie has observed that \[f(N)\geq (5/8+o(1))N,\] taking $A$ to be all odd integers $\leq N/4$ and all integers in $[N/2,N]$.

Stijn Cambie has also observed that, if we allow $b=c$, then there is a solution to this equation when $\lvert A\rvert \geq (\tfrac{2}{3}+o(1))N$, since then there must exist some $n,2n\in A$.

See also [301] and [327].

Additional thanks to: Stijn Cambie, Zachary Hunter, Mehtaab Sawhney, and Wouter van Doorn
SOLVED
Is it true that in any finite colouring of the integers there exists a monochromatic solution to \[\frac{1}{a}=\frac{1}{b}+\frac{1}{c}\] with distinct $a,b,c$?
The density version of this is [302]. This colouring version is true, as proved by Brown and Rödl [BrRo91].
OPEN
For integers $1\leq a<b$ let $N(a,b)$ denote the minimal $k$ such that there exist integers $1<n_1<\cdots<n_k$ with \[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Estimate $N(b)=\max_{1\leq a<b}N(a,b)$. Is it true that $N(b) \ll \log\log b$?
Erdős [Er50c] proved that \[\log\log b \ll N(b) \ll \frac{\log b}{\log\log b}.\] The upper bound was improved by Vose [Vo85] to \[N(b) \ll \sqrt{\log b}.\] One can also investigate the average of $N(a,b)$ for fixed $b$, and it is known that \[\frac{1}{b}\sum_{1\leq a<b}N(a,b) \gg \log\log b.\]

Related to [18].

Additional thanks to: Zachary Hunter
SOLVED
For integers $1\leq a<b$ let $D(a,b)$ be the minimal value of $n_k$ such that there exist integers $1\leq n_1<\cdots <n_k$ with \[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Estimate $D(b)=\max_{1\leq a<b}D(a,b)$. Is it true that \[D(b) \ll b(\log b)^{1+o(1)}?\]
Bleicher and Erdős [BlEr76] have shown that \[D(b)\ll b(\log b)^2.\] If $b=p$ is a prime then \[D(p) \gg p\log p.\]

This was solved by Yokota [Yo88], who proved that \[D(b)\ll b(\log b)(\log\log b)^4(\log\log\log b)^2.\] This was improved by Liu and Sawhney [LiSa24] to \[D(b)\ll b(\log b)(\log\log b)^3(\log\log\log b)^{O(1)}.\]

OPEN
Let $a/b\in \mathbb{Q}_{>0}$ with $b$ squarefree. Are there integers $1<n_1<\cdots<n_k$, each the product of two distinct primes, such that \[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}?\]
For $n_i$ the product of three distinct primes, this is true when $b=1$, as proved by Butler, Erdős and Graham [BEG15] (this paper is perhaps Erdős' last paper, appearing 19 years after his death).
OPEN
Are there two finite sets of primes $P,Q$ such that \[1=\left(\sum_{p\in P}\frac{1}{p}\right)\left(\sum_{q\in Q}\frac{1}{q}\right)?\]
Asked by Barbeau [Ba76]. Can this be done if we drop the requirement that all $p\in P$ are prime and just ask for them to be relatively coprime, and similarly for $Q$?
SOLVED
Let $N\geq 1$. What is the smallest integer not representable as the sum of distinct unit fractions with denominators from $\{1,\ldots,N\}$? Is it true that the set of integers representable as such has the shape $\{1,\ldots,m\}$ for some $m$?
This was essentially solved by Croot [Cr99], who proved that if $f(N)$ is the smallest integer not representable then \[\left\lfloor\sum_{n\leq N}\frac{1}{n}-\frac{9}{2}(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor\leq f(N)\] and \[f(N)\leq \left\lfloor\sum_{n\leq N}\frac{1}{n}-\frac{1}{2}(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor.\] It follows that, if $m_N=\lfloor \sum_{n\leq N}\frac{1}{n}\rfloor$, then the set of integers representable is, for all $N$ sufficiently large, either $\{1,\ldots,m_N-1\}$ or $\{1,\ldots,m_N\}$.
Additional thanks to: Wouter van Doorn
SOLVED
Let $N\geq 1$. How many integers can be written as the sum of distinct unit fractions with denominators from $\{1,\ldots,N\}$? Are there $o(\log N)$ such integers?
The answer to the second question is no: there are at least $(1-o(1))\log N$ many such integers, which follows from a more precise result of Croot [Cr99], who showed that every integer at most \[\leq \sum_{n\leq N}\frac{1}{n}-(\tfrac{9}{2}+o(1))\frac{(\log\log N)^2}{\log N}\] can be so represented.
Additional thanks to: Zachary Hunter and Mehtaab Sawhney
SOLVED
Let $\alpha >0$ and $N\geq 1$. Is it true that for any $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert \geq \alpha N$ there exists some $S\subseteq A$ such that \[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\] with $a\leq b =O_\alpha(1)$?
Liu and Sawhney [LiSa24] observed that the main result of Bloom [Bl21] implies a positive solution to this conjecture. They prove a more precise version, that if $(\log N)^{-1/7+o(1)}\leq \alpha \leq 1/2$ then there is some $S\subseteq A$ such that \[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\] with $a\leq b \leq \exp(O(1/\alpha))$. They also observe that the dependence $b\leq \exp(O(1/\alpha))$ is sharp.
OPEN
What is the minimal value of $\lvert 1-\sum_{n\in A}\frac{1}{n}\rvert$ as $A$ ranges over all subsets of $\{1,\ldots,N\}$ which contain no $S$ such that $\sum_{n\in S}\frac{1}{n}=1$? Is it \[e^{-(c+o(1))N}\] for some constant $c\in (0,1)$?
It is trivially at least $1/[1,\ldots,N]$.
OPEN
Does there exist some $c>0$ such that, for any $K>1$, whenever $A$ is a sufficiently large finite multiset of integers with $\sum_{n\in A}\frac{1}{n}>K$ there exists some $S\subseteq A$ such that \[1-e^{-cK} < \sum_{n\in S}\frac{1}{n}\leq 1?\]
Erdős and Graham knew this with $e^{-cK}$ replaced by $c/K^2$.
Additional thanks to: Mehtaab Sawhney
OPEN
Are there infinitely many solutions to \[\frac{1}{p_1}+\cdots+\frac{1}{p_k}=1-\frac{1}{m},\] where $m\geq 2$ is an integer and $p_1<\cdots<p_k$ are distinct primes?
For example, \[\frac{1}{2}+\frac{1}{3}=1-\frac{1}{6}.\]
SOLVED
Let $n\geq 1$ and let $m$ be minimal such that $\sum_{n\leq k\leq m}\frac{1}{k}\geq 1$. We define \[\epsilon(n) = \sum_{n\leq k\leq m}\frac{1}{k}-1.\] How small can $\epsilon(n)$ be? Is it true that \[\liminf n^2\epsilon(n)=0?\]
This is true, and shown by Lim and Steinerberger [LiSt24] who proved that there exist infinitely many $n$ such that \[\epsilon(n)n^2\ll \left(\frac{\log\log n}{\log n}\right)^{1/2}.\] Erdős and Graham (and also Lim and Steinerberger) believe that the exponent of $2$ is best possible here, in that $\liminf \epsilon(n) n^{2+\delta}=\infty$ for all $\delta>0$.
OPEN
Let $u_1=2$ and $u_{n+1}=u_n^2-u_n+1$. Let $a_1<a_2<\cdots $ be any other sequence with $\sum \frac{1}{a_k}=1$. Is it true that \[\liminf a_n^{1/2^n}<\lim u_n^{1/2^n}=c_0=1.264085\cdots?\]
$c_0$ is called the Vardi constant and the sequence $u_n$ is Sylvester's sequence.

In [ErGr80] this problem is stated with the sequence $u_1=1$ and $u_{n+1}=u_n(u_n+1)$, but Quanyu Tang has pointed out this is probably an error (since with that choice we do not have $\sum \frac{1}{u_n}=1$). This question with Sylvester's sequence is the most natural interpretation of what they meant to ask.

Additional thanks to: Quanyu Tang
SOLVED
Is it true that if $A\subset \mathbb{N}\backslash\{1\}$ is a finite set with $\sum_{n\in A}\frac{1}{n}<2$ then there is a partition $A=A_1\sqcup A_2$ such that \[\sum_{n\in A_i}\frac{1}{n}<1\] for $i=1,2$?
This is not true if $A$ is a multiset, for example $2,3,3,5,5,5,5$.

This is not true in general, as shown by Sándor [Sa97], who observed that the proper divisors of $120$ form a counterexample. More generally, Sándor shows that for any $n\geq 2$ there exists a finite set $A\subseteq \mathbb{N}\backslash\{1\}$ with $\sum_{k\in A}\frac{1}{k}<n$ and no partition into $n$ parts each of which has $\sum_{k\in A_i}\frac{1}{k}<1$.

The minimal counterexample is $\{2,3,4,5,6,7,10,11,13,14,15\}$, found by Tom Stobart.

Additional thanks to: Tom Stobart
OPEN
Is there some constant $c>0$ such that for every $n\geq 1$ there exists some $\delta_k\in \{-1,0,1\}$ for $1\leq k\leq n$ with \[0< \left\lvert \sum_{1\leq k\leq n}\frac{\delta_k}{k}\right\rvert < \frac{c}{2^n}?\] Is it true that for sufficiently large $n$, for any $\delta_k\in \{-1,0,1\}$, \[\left\lvert \sum_{1\leq k\leq n}\frac{\delta_k}{k}\right\rvert > \frac{1}{[1,\ldots,n]}\] whenever the left-hand side is not zero?
Inequality is obvious for the second claim, the problem is strict inequality. This fails for small $n$, for example \[\frac{1}{2}-\frac{1}{3}-\frac{1}{4}=-\frac{1}{12}.\]
Additional thanks to: Zachary Chase
OPEN
Let $A\subseteq \mathbb{N}$ be an infinite arithmetic progression and $f:A\to \{-1,1\}$ be a non-constant function. Must there exist a finite non-empty $S\subset A$ such that \[\sum_{n\in S}\frac{f(n)}{n}=0?\] What about if $A$ is an arbitrary set of positive density? What if $A$ is the set of squares excluding $1$?
Erdős and Straus [ErSt75] proved this when $A=\mathbb{N}$. Sattler [Sa75] proved this when $A$ is the set of odd numbers. For the squares $1$ must be excluded or the result is trivially false, since \[\sum_{k\geq 2}\frac{1}{k^2}<1.\]
Additional thanks to: Hayato Egami
OPEN
What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that there is a function $\delta:A\to \{-1,1\}$ such that \[\sum_{n\in A}\frac{\delta_n}{n}=0\] and \[\sum_{n\in A'}\frac{\delta_n}{n}\neq 0\] for all non-empty $A'\subsetneq A$?
Additional thanks to: Hayato Egami
OPEN
Let $S(N)$ count the number of distinct sums of the form $\sum_{n\in A}\frac{1}{n}$ for $A\subseteq \{1,\ldots,N\}$. Estimate $S(N)$.
Bleicher and Erdős [BlEr75] proved the lower bound \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq \frac{\log S(N)}{\log 2},\] valid for $k\geq 4$ and $\log_kN\geq k$, and also [BlEr76b] proved the upper bound \[\log S(N)\leq \log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for $r\geq 1$ and $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [321].

Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN
What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that all sums $\sum_{n\in S}\frac{1}{n}$ are distinct for $S\subseteq A$?
Let $R(N)$ be the maximal such size. Results of Bleicher and Erdős from [BlEr75] and [BlEr76b] imply that \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq R(N)\leq \frac{1}{\log 2}\log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for any $k\geq 4$ with $\log_kN\geq k$ and any $r\geq 1$ with $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [320].

Additional thanks to: Boris Alexeev, Zachary Hunter, and Dustin Mixon
OPEN
Let $k\geq 3$ and $A\subset \mathbb{N}$ be the set of $k$th powers. What is the order of growth of $1_A^{(k)}(n)$, i.e. the number of representations of $n$ as the sum of $k$ many $k$th powers? Does there exist some $c>0$ and infinitely many $n$ such that \[1_A^{(k)}(n) >n^c?\]
Connected to Waring's problem. The famous Hypothesis $K$ of Hardy and Littlewood was that $1_A^{(k)}(n)\leq n^{o(1)}$, but this was disproved by Mahler [Ma36] for $k=3$, who constructed infinitely many $n$ such that \[1_A^{(3)}(n)\gg n^{1/12}\] (where $A$ is the set of cubes). Erdős believed Hypothesis $K$ fails for all $k\geq 4$, but this is unknown. Hardy and Littlewood made the weaker Hypothesis $K^*$ that for all $N$ and $\epsilon>0$ \[\sum_{n\leq N}1_A^{(k)}(n)^2 \ll_\epsilon N^{1+\epsilon}.\] Erdős and Graham remark: 'This is probably true but no doubt very deep. However, it would suffice for most applications.'

Independently Erdős [Er36] and Chowla proved that for all $k\geq 3$ and infinitely many $n$ \[1_A^{(k)}(n) \gg n^{c/\log\log n}\] for some constant $c>0$ (depending on $k$).

OPEN
Let $1\leq m\leq k$ and $f_{k,m}(x)$ denote the number of integers $\leq x$ which are the sum of $m$ many nonnegative $k$th powers. Is it true that \[f_{k,k}(x) \gg_\epsilon x^{1-\epsilon}\] for all $\epsilon>0$? Is it true that if $m<k$ then \[f_{k,m}(x) \gg x^{m/k}\] for sufficiently large $x$?
This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'. The case $k=2$ was resolved by Landau, who showed \[f_{2,2}(x) \sim \frac{cx}{\sqrt{\log x}}\] for some constant $c>0$.

For $k>2$ it is not known if $f_{k,k}(x)=o(x)$.

OPEN
Does there exist a polynomial $f(x)\in\mathbb{Z}[x]$ such that all the sums $f(a)+f(b)$ with $a<b$ nonnegative integers are distinct?
Erdős and Graham describe this problem as 'very annoying'. Probably $f(x)=x^5$ should work.
OPEN
Let $k\geq 3$ and $f_{k,3}(x)$ denote the number of integers $\leq x$ which are the sum of three nonnegative $k$th powers. Is it true that \[f_{k,3}(x) \gg x^{3/k}\] or even $\gg_\epsilon x^{3/k-\epsilon}$?
Mahler and Erdős [ErMa38] proved that $f_{k,2}(x) \gg x^{2/k}$. For $k=3$ the best known is due to Wooley [Wo15], \[f_{3,3}(x) \gg x^{0.917\cdots}.\]
OPEN
Let $A\subset \mathbb{N}$ be an additive basis of order $2$. Must there exist $B=\{b_1<b_2<\cdots\}\subseteq A$ which is also a basis such that \[\lim_{k\to \infty}\frac{b_k}{k^2}\] does not exist?
Erdős originally asked whether this was true with $A=B$, but this was disproved by Cassels [Ca57].
OPEN
Suppose $A\subseteq \{1,\ldots,N\}$ is such that if $a,b\in A$ and $a\neq b$ then $a+b\nmid ab$. Can $A$ be 'substantially more' than the odd numbers?

What if $a,b\in A$ with $a\neq b$ implies $a+b\nmid 2ab$? Must $\lvert A\rvert=o(N)$?

The connection to unit fractions comes from the observation that $\frac{1}{a}+\frac{1}{b}$ is a unit fraction if and only if $a+b\mid ab$.

Wouter van Doorn has given an elementary argument that proves that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert \geq (25/28+o(1))N$ then $A$ must contain $a\neq b$ with $a+b\mid ab$ (see the discussion in [301]).

See also [302].

Additional thanks to: Wouter van Doorn
SOLVED
Suppose $A\subseteq\mathbb{N}$ and $C>0$ is such that $1_A\ast 1_A(n)\leq C$ for all $n\in\mathbb{N}$. Can $A$ be partitioned into $t$ many subsets $A_1,\ldots,A_t$ (where $t=t(C)$ depends only on $C$) such that $1_{A_i}\ast 1_{A_i}(n)<C$ for all $1\leq i\leq t$ and $n\in \mathbb{N}$?
Asked by Erdős and Newman. Nešetřil and Rödl have shown the answer is no for all $C$ (source is cited as 'personal communication' in [ErGr80]). Erdős had previously shown the answer is no for $C=3,4$ and infinitely many other values of $C$.
OPEN
Suppose $A\subseteq \mathbb{N}$ is a Sidon set. How large can \[\limsup_{N\to \infty}\frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}\] be?
Erdős proved that $1/2$ is possible and Krückeberg [Kr61] proved $1/\sqrt{2}$ is possible. Erdős and Turán [ErTu41] have proved this $\limsup$ is always $\leq 1$.

The fact that $1$ is possible would follow if any finite Sidon set is a subset of a perfect difference set (see [707]).

OPEN
Suppose $A\subset\mathbb{N}$ is a minimal basis with positive density. Is it true that, for any $n\in A$, the (upper) density of integers which cannot be represented without using $n$ is positive?
Asked by Erdős and Nathanson.
SOLVED
Let $A,B\subseteq \mathbb{N}$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}\] and \[\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.\] Is it true that there are infinitely many solutions to $a_1-a_2=b_1-b_2\neq 0$ with $a_1,a_2\in A$ and $b_1,b_2\in B$?
Ruzsa has observed that there is a simple counterexample: take $A$ to be the set of numbers whose binary representation has only non-zero digits in even places, and $B$ similarly but with non-zero digits only in odd places. It is easy to see $A$ and $B$ both grow like $\gg N^{1/2}$ and yet for any $n\geq 1$ there is exactly one solution to $n=a+b$ with $a\in A$ and $b\in B$.

Ruzsa suggests that a non-trivial variant of this problem arises if one imposes the stronger condition that \[\lvert A\cap \{1,\ldots,N\}\rvert \sim c_AN^{1/2}\] for some constant $c_A>0$ as $N\to \infty$, and similarly for $B$.

Additional thanks to: Imre Ruzsa
OPEN
Let $A\subseteq \mathbb{N}$ and $D(A)$ be the set of those numbers which occur infinitely often as $a_1-a_2$ with $a_1,a_2\in A$. What conditions on $A$ are sufficient to ensure $D(A)$ has bounded gaps?
Prikry, Tijdeman, Stewart, and others (see the survey articles [St78] and [Ti79]) have shown that a sufficient condition is that $A$ has positive density.

One can also ask what conditions are sufficient for $D(A)$ to have positive density, or for $\sum_{d\in D(A)}\frac{1}{d}=\infty$, or even just $D(A)\neq\emptyset$.

OPEN
Let $A\subseteq \mathbb{N}$ be a set of density zero. Does there exist a basis $B$ such that $A\subseteq B+B$ and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large $N$?
Erdős and Newman [ErNe77] have proved this is true when $A$ is the set of squares.

See also [806].

OPEN
Find the best function $f(n)$ such that every $n$ can be written as $n=a+b$ where both $a,b$ are $f(n)$-smooth (that is, are not divisible by any prime $p>f(n)$.)
Erdős originally asked if even $f(n)\leq n^{1/3}$ is true. This is known, and the best bound is due to Balog [Ba89] who proved that \[f(n) \ll_\epsilon n^{\frac{4}{9\sqrt{e}}+\epsilon}\] for all $\epsilon>0$. (Note $\frac{4}{9\sqrt{e}}=0.2695\ldots$.)

It is likely that $f(n)\leq n^{o(1)}$, or even $f(n)\leq e^{O(\sqrt{\log n})}$.

Additional thanks to: Zachary Hunter
OPEN
Let $d(A)$ denote the density of $A\subseteq \mathbb{N}$. Characterise those $A,B\subseteq \mathbb{N}$ with positive density such that \[d(A+B)=d(A)+d(B).\]
One way this can happen is if there exists $\theta>0$ such that \[A=\{ n>0 : \{ n\theta\} \in X_A\}\textrm{ and }B=\{ n>0 : \{n\theta\} \in X_B\}\] where $\{x\}$ denotes the fractional part of $x$ and $X_A,X_B\subseteq \mathbb{R}/\mathbb{Z}$ are such that $\mu(X_A+X_B)=\mu(X_A)+\mu(X_B)$. Are all possible $A$ and $B$ generated in a similar way (using other groups)?
OPEN
For $r\geq 2$ let $h(r)$ be the maximal finite $k$ such that there exists a basis $A\subseteq \mathbb{N}$ of order $r$ (so every large integer is the sum of at most $r$ integers from $A$) and exact order $k$ (i.e. $k$ is minimal such that every large integer is the sum of exactly $k$ integers from $A$). Find the value of \[\lim_r \frac{h(r)}{r^2}.\]
Erdős and Graham [ErGr80b] have shown that a basis $A$ has an exact order if and only if $a_2-a_1,a_3-a_2,a_4-a_3,\ldots$ are coprime. They also prove that \[\frac{1}{4}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{5}{4}.\] It is known that $h(2)=4$, but even $h(3)$ is unknown (it is $\geq 7$).
Additional thanks to: Zachary Hunter
SOLVED
Let $A\subseteq \mathbb{N}$ be an additive basis (of any finite order) such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that \[\lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty?\]
The answer is no, and a counterexample was provided by Turjányi [Tu84]. This was generalised (to the replacement of $A+A$ by the $h$-fold sumset $hA$ for any $h\geq 2$) by Ruzsa and Turjányi [RT85]. Ruzsa and Turjányi do prove (under the same hypotheses) that \[\lim_{N\to \infty}\frac{\lvert (A+A+A)\cap \{1,\ldots,3N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty,\] and conjecture that the same should be true with $(A+A)\cap \{1,\ldots,2N\}$ in the numerator.
Additional thanks to: Zachary Chase, Zach Hunter
OPEN
The restricted order of a basis is the least integer $t$ (if it exists) such that every large integer is the sum of at most $t$ distinct summands from $A$. What are necessary and sufficient conditions that this exists? Can it be bounded (when it exists) in terms of the order of the basis? What are necessary and sufficient conditions that this is equal to the order of the basis?
Bateman has observed that for $h\geq 3$ there is a basis of order $h$ with no restricted order, taking \[A=\{1\}\cup \{x>0 : h\mid x\}.\] Kelly [Ke57] has shown that any basis of order $2$ has restricted order at most $4$ and conjectured it always has restricted order at most $3$ (which he proved under the additional assumption that the basis has positive lower density). Kelly's conjecture was disproved by Hennecart [He05], who constructed a basis of order $2$ with restricted order $4$.

The set of squares has order $4$ and restricted order $5$ (see [Pa33]) and the set of triangular numbers has order $3$ and restricted order $3$ (see [Sc54]).

Is it true that if $A\backslash F$ is a basis for all finite sets $F$ then $A$ must have a restricted order? What if they are all bases of the same order?

Hegyvári, Hennecart, and Plagne [HHP07] have shown that for all $k\geq2$ there exists a basis of order $k$ which has restricted order at least \[2^{k-2}+k-1.\]

Additional thanks to: Euro Sampaio
OPEN
Let $A\subseteq \mathbb{N}$ be a basis of order $r$. Must the set of integers representable as the sum of exactly $r$ distinct elements from $A$ have positive density?
OPEN
Let $A=\{1,2,4,8,13,21,31,45,66,81,97,\ldots\}$ be the greedy Sidon sequence: we begin with $1$ and iteratively include the next smallest integer that preserves the Sidon property. What is the order of growth of $A$? Is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2-\epsilon}\] for all $\epsilon>0$ and large $N$?
Erdős and Graham [ErGr80] also asked about the difference set $A-A$, whether this has positive density, and whether this contains $22$. It does contain $22$, since $a_{15}-a_{14}=204-182=22$. The smallest integer which is unknown to be in $A-A$ is $33$. It may be true that all or almost all integers are in $A-A$.

This sequence is at OEIS A005282.

Additional thanks to: Vjekoslav Kovac
OPEN
Let $A=\{a_1<\cdots<a_k\}$ be a finite set of integers and extend it to an infinite sequence $\overline{A}=\{a_1<a_2<\cdots \}$ by defining $a_{n+1}$ for $n\geq k$ to be the least integer exceeding $a_n$ which is not of the form $a_i+a_j$ with $i,j\leq n$. Is it true that the sequence of differences $a_{m+1}-a_m$ is eventually periodic?
An old problem of Dickson. Even a starting set as small as $\{1,4,9,16,25\}$ requires thousands of terms before periodicity occurs.
OPEN
With $a_1=1$ and $a_2=2$ let $a_{n+1}$ for $n\geq 2$ be the least integer $>a_n$ which can be expressed uniquely as $a_i+a_j$ for $i<j\leq n$.

What can be said about this sequence? Do infinitely many pairs $a,a+2$ occur? Does this sequence eventually have periodic differences? Is the density $0$?

A problem of Ulam. The sequence is \[1,2,3,4,6,8,11,13,16,18,26,28,\ldots\] at OEIS A002858.
SOLVED
If $A\subseteq \mathbb{N}$ is a multiset of integers such that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N\] for all $N$ then must $A$ be subcomplete? That is, must \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\] contain an infinite arithmetic progression?
A problem of Folkman. Folkman [Fo66] showed that this is true if \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1+\epsilon}\] for some $\epsilon>0$ and all $N$.

The original question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer is yes).

This is best possible, since Folkman [Fo66] showed that for all $\epsilon>0$ there exists a multiset $A$ with \[\lvert A\cap \{1,\ldots,N\}\rvert\ll N^{1+\epsilon}\] for all $N$, such that $A$ is not subcomplete.

Additional thanks to: Zachary Hunter
SOLVED
If $A\subseteq \mathbb{N}$ is a set of integers such that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2}\] for all $N$ then must $A$ be subcomplete? That is, must \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\] contain an infinite arithmetic progression?
Folkman proved this under the stronger assumption that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2+\epsilon}\] for some $\epsilon>0$.

This is true, and was proved by Szemerédi and Vu [SzVu06]. The stronger conjecture that this is true under \[\lvert A\cap \{1,\ldots,N\}\rvert\geq (2N)^{1/2}\] seems to be still open (this would be best possible as shown by [Er61b].

OPEN
Let $A\subseteq \mathbb{N}$ be a complete sequence, and define the threshold of completeness $T(A)$ to be the least integer $m$ such that all $n\geq m$ are in \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\] (the existence of $T(A)$ is guaranteed by completeness).

Is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?

Erdős and Graham [ErGr80] remark that very little is known about $T(A)$ in general. It is known that \[T(n)=1, T(n^2)=128, T(n^3)=12758,\] \[T(n^4)=5134240,\textrm{ and }T(n^5)=67898771.\] Erdős and Graham remark that a good candidate for the $n$ in the question are $k=2^t$ for large $t$, perhaps even $t=3$, because of the highly restricted values of $n^{2^t}$ modulo $2^{t+1}$.
OPEN
Let $A=\{a_1< a_2<\cdots\}$ be a set of integers such that
  • $A\backslash B$ is complete for any finite subset $B$ and
  • $A\backslash B$ is not complete for any infinite subset $B$.
Is it true that if $a_{n+1}/a_n \geq 1+\epsilon$ for some $\epsilon>0$ and all $n$ then \[\lim_n \frac{a_{n+1}}{a_n}=\frac{1+\sqrt{5}}{2}?\]
Graham [Gr64d] has shown that the sequence $a_n=F_n-(-1)^{n}$, where $F_n$ is the $n$th Fibonacci number, has these properties. Erdős and Graham [ErGr80] remark that it is easy to see that if $a_{n+1}/a_n>\frac{1+\sqrt{5}}{2}$ then the second property is automatically satisfied, and that it is not hard to construct very irregular sequences satisfying both properties.
OPEN
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$?
OPEN
For what values of $0\leq m<n$ is there a complete sequence $A=\{a_1\leq a_2\leq \cdots\}$ of integers such that
  • $A$ remains complete after removing any $m$ elements, but
  • $A$ is not complete after removing any $n$ elements?
The Fibonacci sequence $1,1,2,3,5,\ldots$ shows that $m=1$ and $n=2$ is possible. The sequence of powers of $2$ shows that $m=0$ and $n=1$ is possible. The case $m=2$ and $n=3$ is not known.
OPEN
For what values of $t,\alpha \in (0,\infty)$ is the sequence $\lfloor t\alpha^n\rfloor$ complete?
Even in the range $t\in (0,1)$ and $\alpha\in (1,2)$ the behaviour is surprisingly complex. For example, Graham [Gr64e] has shown that for any $k$ there exists some $t_k\in (0,1)$ such that the set of $\alpha$ such that the sequence is complete consists of at least $k$ disjoint line segments. It seems likely that the sequence is complete for all $t>0$ and all $1<\alpha < \frac{1+\sqrt{5}}{2}$. Proving this seems very difficult, since we do not even known whether $\lfloor (3/2)^n\rfloor$ is odd or even infinitely often.
SOLVED
If $A\subset\mathbb{N}$ is a finite set of integers all of whose subset sums are distinct then \[\sum_{n\in A}\frac{1}{n}<2.\]
This was proved by Ryavec. The stronger statement that, for all $s\geq 0$, \[\sum_{n\in A}\frac{1}{n^s} <\frac{1}{1-2^{-s}},\] was proved by Hanson, Steele, and Stenger [HSS77].

See also [1].

OPEN
Let $p(x)\in \mathbb{Q}[x]$. Is it true that \[A=\{ p(n)+1/n : n\in \mathbb{N}\}\] is strongly complete, in the sense that, for any finite set $B$, \[\left\{\sum_{n\in X}n : X\subseteq A\backslash B\textrm{ finite }\right\}\] contains all sufficiently large rational numbers?
Graham [Gr64f] proved this is true when $p(n)=n$. Erdős and Graham also ask which rational functions $r(x)\in\mathbb{Z}[x]$ force $\{ r(n) : n\in\mathbb{N}\}$ to be complete?
OPEN
Let $\alpha,\beta\in \mathbb{R}_{>0}$ such that $\alpha/\beta$ is irrational. Is \[\{ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots\}\cup \{ \lfloor \beta\rfloor,\lfloor 2\beta\rfloor,\lfloor 4\beta\rfloor,\ldots\}\] complete? What if $2$ is replaced by some $\gamma\in(1,2)$?
OPEN
Is there a lacunary sequence $A\subseteq \mathbb{N}$ (so that $A=\{a_1<a_2<\cdots\}$ and there exists some $\lambda>1$ such that $a_{n+1}/a_n\geq \lambda$ for all $n\geq 1$) such that \[\left\{ \sum_{a\in A'}\frac{1}{a} : A'\subseteq A\textrm{ finite}\right\}\] contain all rationals in some open interval?
Bleicher and Erdős conjecture the answer is no.
Additional thanks to: Will Sawin and Stefan Steinerberger
SOLVED
Is there some $c>0$ such that, for all sufficiently large $n$, there exist integers $a_1<\cdots<a_k\leq n$ such that there are at least $cn^2$ distinct integers of the form $\sum_{u\leq i\leq v}a_i$?
This fails for $a_i=i$ for example. Erdős and Graham also ask what happens if we drop the monotonicity restriction and just ask that the $a_i$ are distinct. Perhaps some permutation of $\{1,\ldots,n\}$ has at least $cn^2$ such distinct sums (this was solved by Konieczny [Ko15], see [34]).

The original problem was solved (in the affirmative) by Beker [Be23b].

They also ask how many consecutive integers $>n$ can be represented as such a sum? Is it true that, for any $c>0$ at least $cn$ such integers are possible (for sufficiently large $n$)?

See also [34] and [357].

Additional thanks to: Adrian Beker
OPEN
Let $1\leq a_1<\cdots <a_k\leq n$ be integers such that all sums of the shape $\sum_{u\leq i\leq v}a_i$ are distinct. Let $f(n)$ be the maximal such $k$.

How does $f(n)$ grow? Is $f(n)=o(n)$?

Asked by Erdős and Harzheim.

If $g(n)$ is the maximal $k$ such that there are $1\leq a_1,\ldots,a_k\leq n$ with all consecutive sums distinct (i.e. we drop the monotonicity assumption in the definition of $f$) then Hegyvári [He86] has proved that \[\left(\frac{1}{3}+o(1)\right) n\leq g(n)\leq \left(\frac{2}{3}+o(1)\right)n.\]

A similar question can be asked if we replace strict monotonicity with weak monotonicity (i.e. we allow $a_i=a_j$).

Erdős and Harzheim also ask what is the least $m$ which is not a sum of the given form? Can it be much larger than $n$? Erdős and Harzheim can show that $\sum_{x<a_i<x^2}\frac{1}{a_i}\ll 1$. Is it true that $\sum_i \frac{1}{a_i}\ll 1$?

See also [34] and [356].

Additional thanks to: Sarosh Adenwalla
OPEN
Is there a sequence $A=\{1\leq a_1<a_2<\cdots\}$ such that every large integer is the sum of consecutive elements of $A$? Can the number of representations of $n$ in this form tend to infinity with $n$?
Erdős and Moser [Mo63] considered the case when $A$ is the set of primes, and conjectured that the $\limsup$ of the number of such representations in this case is infinite. They could not even prove that the upper density of the set of integers representable in this form is positive.

Hayato Egami has observed that the answer for the first question is trivially yes as written, since one can take $a_n=n$. Presumably Erdős and Graham meant to impose some condition to rule out this sequence, but it is not clear what was intended.

Additional thanks to: Hayato Egami
OPEN
Let $a_1<a_2<\cdots$ be an infinite sequence of integers such that $a_1=n$ and $a_{i+1}$ is the least integer which is not a sum of consecutive earlier $a_j$s. What can be said about the density of this sequence?

In particular, in the case $n=1$, can one prove that $a_k/k\to \infty$ and $a_k/k^{1+c}\to 0$ for any $c>0$?

A problem of MacMahon, studied by Andrews [An75]. When $n=1$ this sequence begins \[1,2,4,5,8,10,14,15,\ldots.\] This sequence is A002048 in the OEIS. Andrews conjectures \[a_k\sim \frac{k\log k}{\log\log k}.\]

See also [839].

Additional thanks to: Desmond Weisenberg
SOLVED
Let $f(n)$ be minimal such that $\{1,\ldots,n\}$ can be partitioned into $f(n)$ classes so that $n$ cannot be expressed as a sum of distinct elements from the same class. How fast does $f(n)$ grow?
Alon and Erdős [AlEr96] proved that $f(n) = n^{1/3+o(1)}$, and more precisely \[\frac{n^{1/3}}{(\log n)^{4/3}}\ll f(n) \ll \frac{n^{1/3}}{(\log n)^{1/3}}(\log\log n)^{1/3}.\] Vu [Vu07] improved the lower bound to \[f(n) \gg \frac{n^{1/3}}{\log n}.\] Conlon, Fox, and Pham [CFP21] determined the order of growth of $f(n)$ up to a multiplicative constant, proving \[f(n) \asymp \frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log n)^{2/3}}.\]
Additional thanks to: Noga Alon
OPEN
Let $c>0$ and $n$ be some large integer. What is the size of the largest $A\subseteq \{1,\ldots,\lfloor cn\rfloor\}$ such that $n$ is not a sum of a subset of $A$? Does this depend on $n$ in an irregular way?
SOLVED
Let $A\subseteq \mathbb{N}$ be a finite set of size $N$. Is it true that, for any fixed $t$, there are \[\ll \frac{2^N}{N^{3/2}}\] many $S\subseteq A$ such that $\sum_{n\in S}n=t$?

If we further ask that $\lvert S\rvert=l$ (for any fixed $l$) then is the number of solutions \[\ll \frac{2^N}{N^2},\] with the implied constant independent of $l$ and $t$?

Erdős and Moser proved the first bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65], thereby answering the first question in the affirmative. Stanley [St80] has shown that this quantity is maximised when $A$ is an arithmetic progression and $t=\tfrac{1}{2}\sum_{n\in A}n$.

The second question was answered in the affirmative by Halász [Ha77], as a consequence of a more general multi-dimensional result.

Additional thanks to: Adrian Beker and Zachary Chase
SOLVED
Is it true that there are only finitely many collections of disjoint intervals $I_1,\ldots,I_n$ of size $\lvert I_i\rvert \geq 4$ for $1\leq i\leq n$ such that \[\prod_{1\leq i\leq n}\prod_{m\in I_i}m\] is a square?
Erdős and Selfridge have proved that the product of consecutive integers is never a power. The condition $\lvert I_i\rvert \geq 4$ is necessary here, since Pomerance has observed that the product of \[(2^{n-1}-1)2^{n-1}(2^{n-1}+1),\] \[(2^n-1)2^n(2^n+1),\] \[(2^{2n-1}-2)(2^{2n-1}-1)2^{2n-1},\] and \[(2^{2n-2}-2)(2^{2n}-1)2^{2n}\] is always a square.

This is false: Ulas [Ul05] has proved there are infinitely many solutions when $n=4$ or $n\geq 6$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Bauer and Bennett [BaBe07] proved there are infinitely many solutions when $n=3$ or $n=5$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Furthermore, Bennett and Van Luijk [BeVL12] have found infinitely many solutions when $n\geq 5$ and $\lvert I_i\rvert=5$ for $1\leq i\leq n$.

In general, Ulas conjectures there are infinitely many solutions for any fixed size of $\lvert I_i\rvert$, provided $n$ is sufficiently large.

See also [930] for a more general question.

Additional thanks to: Euro Vidal Sampaio and Julia Schmerling
OPEN
Are there any triples of consecutive positive integers all of which are powerful (i.e. if $p\mid n$ then $p^2\mid n$)?
Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Erdős [Er76d] believed the answer to this question is no, and in fact if $n_k$ is the $k$th powerful number then \[n_{k+2}-n_k > n_k^c\] for some constant $c>0$.

It is trivial that there are no quadruples of consecutive powerful numbers since one must be $2\pmod{4}$.

See also [137] and [365].

Additional thanks to: Zachary Chase
OPEN
Do all pairs of consecutive powerful numbers $n$ and $n+1$ come from solutions to Pell equations? In other words, must either $n$ or $n+1$ be a square?

Is the number of such $n\leq x$ bounded by $(\log x)^{O(1)}$?

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=2^3y^2+1$.

The list of $n$ such that $n$ and $n+1$ are both powerful is A060355 in the OEIS.

The answer to the first question is no: Golomb [Go70] observed that both $12167=23^3$ and $12168=2^33^213^2$ are powerful. Walker [Wa76] proved that the equation \[7^3x^2=3^3y^2+1\] has infinitely many solutions, giving infinitely many counterexamples.

See also [364].

OPEN
Are there any 2-full $n$ such that $n+1$ is 3-full? That is, if $p\mid n$ then $p^2\mid n$ and if $p\mid n+1$ then $p^3\mid n+1$.
Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Stephan has found no such $n$ below $10^8$.

Note that $8$ is 3-full and $9$ is 2-full. Erdős and Graham asked if this is the only pair of such consecutive integers. Stephan has observed that $12167=23^3$ and $12168=2^33^213^2$ (a pair already known to Golomb [Go70]) is another example, but there are no other examples below $10^8$.

In [Er76d] Erdős asks the weaker question of whether there are any consecutive pairs of $3$-full integers.

Additional thanks to: Ralf Stephan
OPEN
Let $B_2(n)$ be the 2-full part of $n$ (that is, $B_2(n)=n/n'$ where $n'$ is the product of all primes that divide $n$ exactly once). Is it true that, for every fixed $k\geq 1$, \[\prod_{n\leq m<n+k}B_2(m) \ll n^{2+o(1)}?\] Or perhaps even $\ll_k n^2$?
It would also be interesting to find upper and lower bounds for the analogous product with $B_r$ for $r\geq 3$, where $B_r(n)$ is the $r$-full part of $n$ (that is, the product of prime powers $p^a \mid n$ such that $p^{a+1}\nmid n$ and $a\geq r$). Is it true that, for every fixed $r,k\geq 2$ and $\epsilon>0$, \[\limsup \frac{\prod_{n\leq m<n+k}B_r(m) }{n^{1+\epsilon}}\to\infty?\]
OPEN
How large is the largest prime factor of $n(n+1)$?
Let $F(n)$ be the prime in question. Pólya [Po18] proved that $F(n)\to \infty$ as $n\to\infty$. Mahler [Ma35] showed that $F(n)\gg \log\log n$. Schinzel [Sc67b] observed that for infinitely many $n$ we have $F(n)\leq n^{O(1/\log\log\log n)}$.

The truth is probably $F(n)\gg (\log n)^2$ for all $n$. Erdős [Er76d] conjectured that, for every $\epsilon>0$, there are infinitely many $n$ such that $F(n) <(\log n)^{2+\epsilon}$.

Pasten [Pa24b] has proved that \[F(n) \gg \frac{(\log\log n)^2}{\log\log\log n}.\] The largest prime factors of $n(n+1)$ are listed as A074399 in the OEIS.

Additional thanks to: Ralf Stephan and Desmond Weisenberg
OPEN
Let $\epsilon>0$ and $k\geq 2$. Is it true that, for all sufficiently large $n$, there is a sequence of $k$ consecutive integers in $\{1,\ldots,n\}$ all of which are $n^\epsilon$-smooth?
Erdős and Graham state that this is open even for $k=2$ and 'the answer should be affirmative but the problem seems very hard'.

Unfortunately the problem is trivially true as written (simply taking $\{1,\ldots,k\}$ and $n>k^{1/\epsilon}$). There are (at least) two possible variants which are non-trivial, and it is not clear which Erdős and Graham meant. Let $P$ be the sequence of $k$ consecutive integers sought for. The potential strengthenings which make this non-trivial are:

  • Each $m\in P$ must be $m^\epsilon$-smooth. If this is the problem then the answer is yes, which follows from a result of Balog and Wooley [BaWo98]: for any $\epsilon>0$ and $k\geq 2$ there exist infinitely many $m$ such that $m+1,\ldots,m+k$ are all $m^\epsilon$-smooth.
  • Each $m\in P$ must be in $[n/2,n]$ (say). In this case a positive answer also follows from the result of Balog and Wooley [BaWo98] for infinitely many $n$, but the case of all sufficiently large $n$ is open.

See also [370].

Additional thanks to: Cedric Pilatte
SOLVED
Are there infinitely many $n$ such that the largest prime factor of $n$ is $<n^{1/2}$ and the largest prime factor of $n+1$ is $<(n+1)^{1/2}$?
Pomerance has observed that if we replace $1/2$ in the exponent by $1/\sqrt{e}-\epsilon$ for any $\epsilon>0$ then this is true for density reasons (since the density of integers $n$ whose greatest prime factor is $\leq n^{1/\sqrt{e}}$ is $1/2$).

Steinerberger has pointed out this problem has a trivial solution: take $n=m^2-1$, and then it is obvious that the largest prime factor of $n$ is $\leq m+1\ll n^{1/2}$ and the largest prime factor of $n+1$ is $\leq m\ll (n+1)^{1/2}$ (these $\ll$ can be replaced by $<$ if we choose $m$ such that $m,m+1$ are both composite).

Given that Erdős and Graham describe the above observation of Pomerance and explicitly say about this problem that 'we know very little about this', it is strange that such a trivial obstruction was overlooked. Perhaps the problem they intended was subtly different, and the problem in this form was the result of a typographical error, but I have no good guess what was intended here.

See also [369].

Additional thanks to: Stefan Steinerberger
OPEN
Let $P(n)$ denote the largest prime factor of $n$. Show that the set of $n$ with $P(n+1)>P(n)$ has density $1/2$.
Conjectured by Erdős and Pomerance [ErPo78], who proved that this set and its complement both have positive upper density.

In [Er79e] Erdős also asks whether, for every $\alpha>0$, the density of the set of $n$ where \[P(n+1)>P(n)n^\alpha\] exists.

The sequence of such $n$ is A070089 in the OEIS.

SOLVED
Let $P(n)$ denote the largest prime factor of $n$. There are infinitely many $n$ such that $P(n)>P(n+1)>P(n+2)$.
Conjectured by Erdős and Pomerance [ErPo78], who proved the analogous result for $P(n)<P(n+1)<P(n+2)$. Solved by Balog [Ba01], who proved that this is true for $\gg \sqrt{x}$ many $n\leq x$ (for all large $x$).
OPEN
Show that the equation \[n! = a_1!a_2!\cdots a_k!,\] with $n-1>a_1\geq a_2\geq \cdots \geq a_k$, has only finitely many solutions.
This would follow if $P(n(n+1))/\log n\to \infty$, where $P(m)$ denotes the largest prime factor of $m$ (see Problem [368]). Erdős [Er76d] proved that this problem would also follow from showing that $P(n(n-1))>4\log n$.

Hickerson conjectured the largest solution is \[16! = 14! 5!2!.\] The condition $a_1<n-1$ is necessary to rule out the trivial solutions when $n=a_2!\cdots a_k!$.

Surányi was the first to conjecture that the only non-trivial solution to $a!b!=n!$ is $6!7!=10!$.

OPEN
For any $m\in \mathbb{N}$, let $F(m)$ be the minimal $k\geq 2$ (if it exists) such that there are $a_1<\cdots <a_k=m$ with $a_1!\cdots a_k!$ a square. Let $D_k=\{ m : F(m)=k\}$. What is the order of growth of $\lvert D_k\cap\{1,\ldots,n\}\rvert$ for $3\leq k\leq 6$? For example, is it true that $\lvert D_6\cap \{1,\ldots,n\}\rvert \gg n$?
Studied by Erdős and Graham [ErGr76] (see also [LSS14]). It is known, for example, that:
  • no $D_k$ contains a prime,
  • $D_2=\{ n^2 : n>1\}$,
  • $\lvert D_3\cap \{1,\ldots,n\}\rvert = o(\lvert D_4\cap \{1,\ldots,n\}\rvert)$,
  • the least element of $D_6$ is $527$, and
  • $D_k=\emptyset$ for $k>6$.
Additional thanks to: Zachary Chase
OPEN
Is it true that for any $n,k\geq 1$, if $n+1,\ldots,n+k$ are all composite then there are distinct primes $p_1,\ldots,p_k$ such that $p_i\mid n+i$ for $1\leq i\leq k$?
Note this is trivial when $k\leq 2$. Originally conjectured by Grimm [Gr69]. This is a very difficult problem, since it in particular implies $p_{n+1}-p_n <p_n^{1/2-c}$ for some constant $c>0$, in particular resolving Legendre's conjecture.

Grimm proved that this is true if $k\ll \log n/\log\log n$. Erdős and Selfridge improved this to $k\leq (1+o(1))\log n$. Ramachandra, Shorey, and Tijdeman [RST75] have improved this to \[k\ll\left(\frac{\log n}{\log\log n}\right)^3.\]

OPEN
Are there infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $105$?
Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown that, for any two odd primes $p$ and $q$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$.

The sequence of such $n$ is A030979 in the OEIS.

OPEN
Is there some absolute constant $C>0$ such that \[\sum_{p\leq n}1_{p\nmid \binom{2n}{n}}\frac{1}{p}\leq C\] for all $n$?
A question of Erdős, Graham, Ruzsa, and Straus [EGRS75], who proved that if $f(n)$ is the sum in question then \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n) = \sum_{k=2}^\infty \frac{\log k}{2^k}=\gamma_0\] and \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n)^2 = \gamma_0^2,\] so that for almost all integers $f(m)=\gamma_0+o(1)$. They also prove that, for all large $n$, \[f(n) \leq c\log\log n\] for some constant $c<1$. (It is trivial from Mertens estimates that $f(n)\leq (1+o(1))\log\log n$.)

A positive answer would imply that \[\sum_{p\leq n}1_{p\mid \binom{2n}{n}}\frac{1}{p}=(1-o(1))\log\log n,\] and Erdős, Graham, Ruzsa, and Straus say there is 'no doubt' this latter claim is true.

Additional thanks to: Julius Schmerling
OPEN
Let $r\geq 0$. Does the density of integers $n$ for which $\binom{n}{k}$ is squarefree for at least $r$ values of $1\leq k<n$ exist? Is this density $>0$?
Erdős and Graham state they can prove that, for $k$ fixed and large, the density of $n$ such that $\binom{n}{k}$ is squarefree is $o_k(1)$. They can also prove that there are infinitely many $n$ such that $\binom{n}{k}$ is not squarefree for $1\leq k<n$, and expect that the density of such $n$ is positive.
OPEN
Let $S(n)$ denote the largest integer such that, for all $1\leq k<n$, the binomial coefficient $\binom{n}{k}$ is divisible by $p^{S(n)}$ for some prime $p$ (depending on $k$). Is it true that \[\limsup S(n)=\infty?\]
If $s(n)$ denotes the largest integer such that $\binom{n}{k}$ is divisible by $p^{s(n)}$ for some prime $p$ for at least one $1\leq k<n$ then it is easy to see that $s(n)\to \infty$ as $n\to \infty$ (and in fact that $s(n) \asymp \log n$).
OPEN
We call an interval $[u,v]$ 'bad' if the greatest prime factor of $\prod_{u\leq m\leq v}m$ occurs with an exponent greater than $1$. Let $B(x)$ count the number of $n\leq x$ which are contained in at least one bad interval. Is it true that \[B(x)\sim \#\{ n\leq x: p\mid n\rightarrow p\leq n^{1/2}\}?\]
Erdős and Graham only knew that $B(x) > x^{1-o(1)}$. Similarly, we call an interval $[u,v]$ 'very bad' if $\prod_{u\leq m\leq v}m$ is powerful. The number of integers $n\leq x$ contained in at least one very bad interval should be $\ll x^{1/2}$. In fact, it should be asymptotic to the number of powerful numbers $\leq x$.

See also [382].

OPEN
Let $u\leq v$ be such that the largest prime dividing $\prod_{u\leq m\leq v}m$ appears with exponent at least $2$. Is it true that $v-u=v^{o(1)}$? Can $v-u$ be arbitrarily large?
Erdős and Graham report it follows from results of Ramachandra that $v-u\leq v^{1/2+o(1)}$.

See also [380].

OPEN
Is it true that for every $k$ there are infinitely many primes $p$ such that the largest prime divisor of \[\prod_{0\leq i\leq k}(p^2+i)\] is $p$?
SOLVED
If $1<k<n-1$ then $\binom{n}{k}$ is divisible by a prime $p<n/2$ (except $\binom{7}{3}=5\cdot 7$).
A conjecture of Erdős and Selfridge. Proved by Ecklund [Ec69], who made the stronger conjecture that whenever $n>k^2$ the binomial coefficient $\binom{n}{k}$ is divisible by a prime $p<n/k$. They have proved the weaker inequality $p\ll n/k^c$ for some constant $c>0$.
Additional thanks to: Zachary Chase
OPEN
Let \[F(n) = \max_{\substack{m<n\\ m\textrm{ composite}}} m+p(m),\] where $p(m)$ is the least prime divisor of $m$. Is it true that $F(n)>n$ for all sufficiently large $n$? Does $F(n)-n\to \infty$ as $n\to\infty$?
A question of Erdős, Eggleton, and Selfridge, who write that 'plausible conjectures on primes' imply that $F(n)\leq n$ for only finitely many $n$, and in fact it is possible that this quantity is always at least $n+(1-o(1))\sqrt{n}$ (note that it is trivially $\leq n+\sqrt{n}$).

Tao has discussed this problem in a blog post.

Sarosh Adenwalla has observed that the first question is equivalent to [430]. Indeed, if $n$ is large and $a_i$ is the sequence defined in the latter problem, then [430] implies tha there is a composite $a_j$ such that $a_j-p(a_j)>n$ and hence $F(n)>n$.

Additional thanks to: Sarosh Adenwalla
OPEN
Can $\binom{n}{k}$ be the product of consecutive primes infinitely often? For example \[\binom{21}{2}=2\cdot 3\cdot 5\cdot 7.\]
Erdős and Graham write that 'a proof that this cannot happen infinitely often for $\binom{n}{2}$ seems hopeless; probably this can never happen for $\binom{n}{k}$ if $3\leq k\leq n-3$.'

Weisenberg has provided four easy examples that show Erdős and Graham were too optimistic here: \[\binom{7}{3}=5\cdot 7,\] \[\binom{10}{4}= 2\cdot 3\cdot 5\cdot 7,\] \[\binom{14}{4} = 7\cdot 11\cdot 13,\] and \[\binom{15}{6}=5\cdot 7\cdot 11\cdot 13.\]

Additional thanks to: Desmond Weisenberg
OPEN
Is there an absolute constant $c>0$ such that, for all $1\leq k< n$, the binomial coefficient $\binom{n}{k}$ has a divisor in $(cn,n]$?
Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58].
Additional thanks to: Zachary Chase
OPEN
Can one classify all solutions of \[\prod_{1\leq i\leq k_1}(m_1+i)=\prod_{1\leq j\leq k_2}(m_2+j)\] where $1<k_1<k_2$ and $m_1+k_1\leq m_2$? Are there only finitely many solutions?
More generally, if $k_1>2$ then for fixed $a$ and $b$ \[a\prod_{1\leq i\leq k_1}(m_1+i)=b\prod_{1\leq j\leq k_2}(m_2+j)\] should have only a finite number of solutions.

See also [363] and [931].

OPEN
Is it true that for every $n\geq 1$ there is a $k$ such that \[n(n+1)\cdots(n+k-1)\mid (n+k)\cdots (n+2k-1)?\]
Asked by Erdős and Straus. For example when $n=2$ we have $k=5$: \[2\times 3 \times 4 \times 5\times 6 \mid 7 \times 8 \times 9\times 10\times 11.\] and when $n=3$ we have $k=4$: \[3\times 4\times 5\times 6 \mid 7\times 8\times 9\times 10.\] Bhavik Mehta has computed the minimal such $k$ for $1\leq n\leq 18$ (now available as A375071 on the OEIS).
Additional thanks to: Bhavik Mehta
OPEN
Let $f(n)$ be the minimal $m$ such that \[n! = a_1\cdots a_k\] with $n< a_1<\cdots <a_k=m$. Is there (and what is it) a constant $c$ such that \[f(n)-2n \sim c\frac{n}{\log n}?\]
Erdős, Guy, and Selfridge [EGS82] have shown that \[f(n)-2n \asymp \frac{n}{\log n}.\]
OPEN
Let $t(n)$ be maximal such that there is a representation \[n!=a_1\cdots a_n\] with $t(n)=a_1\leq \cdots \leq a_n$. Obtain good bounds for $t(n)/n$. In particular, is it true that \[\lim \frac{t(n)}{n}=\frac{1}{e}?\] Furthermore, does there exist some constant $c>0$ such that \[\frac{t(n)}{n} \leq \frac{1}{e}-\frac{c}{\log n}\] for infinitely many $n$?
It is easy to see that \[\lim \frac{t(n)}{n}\leq \frac{1}{e}.\] Erdős [Er96b] wrote he, Selfridge, and Straus had proved a corresponding lower bound, so that $\lim \frac{t(n)}{n}=\frac{1}{e}$, and 'believed that Straus had written up our proof. Unfortunately Straus suddenly died and no trace was ever found of his notes. Furthermore, we never could reconstruct our proof, so our assertion now can be called only a conjecture.'

Alladi and Grinstead [AlGr77] have obtained similar results when the $a_i$ are restricted to prime powers.

OPEN
Let $A(n)$ denote the least value of $t$ such that \[n!=a_1\cdots a_t\] with $a_1\leq \cdots \leq a_t\leq n^2$. Is it true that \[A(n)=\frac{n}{2}-\frac{n}{2\log n}+o\left(\frac{n}{\log n}\right)?\]
If we change the condition to $a_t\leq n$ it can be shown that \[A(n)=n-\frac{n}{\log n}+o\left(\frac{n}{\log n}\right)\] via a greedy decomposition (use $n$ as often as possible, then $n-1$, and so on). Other questions can be asked for other restrictions on the sizes of the $a_t$.
OPEN
Let $f(n)$ denote the minimal $m$ such that \[n! = a_1\cdots a_t\] with $a_1<\cdots <a_t=a_1+m$. What is the behaviour of $f(n)$?
Erdős and Graham write that they do not even know whether $f(n)=1$ infinitely often (i.e. whether a factorial is the product of two consecutive integers infinitely often).
SOLVED
Let $t_k(n)$ denote the least $m$ such that \[n\mid (m+1)(m+2)\cdots (m+k).\] Is it true that \[\sum_{1\leq n\leq N}t_2(n)=o(N)?\]
The answer is yes, proved by Hall. It is probably true that the sum is $o(N/(\log N)^c)$ for some constant $c>0$. Similar questions can be asked for other $k\geq 3$.
Additional thanks to: Zachary Chase
OPEN
Is it true that for every $k$ there exists $n$ such that \[\prod_{0\leq i\leq k}(n-i) \mid \binom{2n}{n}?\]
Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$ (indeed $\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number), but it is quite rare that $n$ divides $\binom{2n}{n}$.

Pomerance [Po14] has shown that for any $k\geq 0$ there are infinitely many $n$ such that $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$. Pomerance also shows that the set of $n$ such that \[\prod_{1\leq i\leq k}(n+i)\mid \binom{2n}{n}\] has density $1$.

The smallest $n$ for each $k$ are listed as A375077 on the OEIS.

Additional thanks to: Ralf Stephan
OPEN
Are there only finitely many solutions to \[\prod_i \binom{2m_i}{m_i}=\prod_j \binom{2n_j}{n_j}\] with the $m_i,n_j$ distinct?
OPEN
Are the only solutions to \[n!=x^2-1\] when $n=4,5,7$?
The Brocard-Ramanujan conjecture. Erdős and Graham describe this as an old conjecture, and write it 'is almost certainly true but it is intractable at present'.

Overholt [Ov93] has shown that this has only finitely many solutions assuming a weak form of the abc conjecture.

There are no other solutions below $10^9$ (see the OEIS page).

SOLVED
Is it true that there are no solutions to \[n! = x^k\pm y^k\] with $x,y,n\in \mathbb{N}$, with $xy>1$ and $k>2$?
Erdős and Obláth [ErOb37] proved this is true when $(x,y)=1$ and $k\neq 4$. Pollack and Shapiro [PoSh73] proved there are no solutions to $n!=x^4-1$. The known methods break down without the condition $(x,y)=1$.

Jonas Barfield has found the solution \[10! = 48^4 - 36^4=12^4\cdot 175.\]

Additional thanks to: Jonas Barfield and Zachary Chase
OPEN
For any $k\geq 2$ let $g_k(n)$ denote the maximal value of \[n-(a_1+\cdots+a_k)\] where $a_1,\ldots,a_k$ are integers such that $a_1!\cdots a_k! \mid n!$. Can one show that \[\sum_{n\leq x}g_k(n) \sim c_k x\log x\] for some constant $c_k$? Is it true that there is a constant $c_k$ such that for almost all $n<x$ we have \[g_k(n)=c_k\log x+o(\log x)?\]
Erdős and Graham write that it is easy to show that $g_k(n) \ll_k \log n$ always, but the best possible constant is unknown.

See also [401].

OPEN
Is there some function $\omega(r)$ such that $\omega(r)\to \infty$ as $r\to\infty$, such that for all large $n$ there exist $a_1,a_2$ with \[a_1+a_2> n+\omega(r)\log n\] such that $a_1!a_2! \mid n!2^n3^n\cdots p_r^n$?
See also [400].
SOLVED
Prove that, for any finite set $A\subset\mathbb{N}$, there exist $a,b\in A$ such that \[\mathrm{gcd}(a,b)\leq a/\lvert A\rvert.\]
A conjecture of Graham [Gr70], who also conjectured that (assuming $A$ itself has no common divisor) the only cases where equality is achieved are when $A=\{1,\ldots,n\}$ or $\{L/1,\ldots,L/n\}$ (where $L=\mathrm{lcm}(1,\ldots,n)$) or $\{2,3,4,6\}$.

Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87].

Proved for all sets by Balasubramanian and Soundararajan [BaSo96].

SOLVED
Does the equation \[2^m=a_1!+\cdots+a_k!\] with $a_1<a_2<\cdots <a_k$ have only finitely many solutions?
Asked by Burr and Erdős. Frankl and Lin [Li76] independently showed that the answer is yes, and the largest solution is \[2^7=2!+3!+5!.\] In fact Lin showed that the largest power of $2$ which can divide a sum of distinct factorials containing $2$ is $2^{254}$, and that there are only 5 solutions to $3^m=a_1!+\cdots+a_k!$ (when $m=0,1,2,3,6$).

See also [404].

OPEN
Let $f(a,p)$ be the largest $k$ such that there are $a=a_1<\cdots<a_k$ such that \[p^k \mid (a_1!+\cdots+a_k!).\] Is $f(a,p)$ bounded by some absolute constant? What if this constant is allowed to depend on $a$ and $p$?

Is there a prime $p$ and an infinite sequence $a_1<a_2<\cdots$ such that if $p^{m_k}$ is the highest power of $p$ dividing $\sum_{i\leq k}a_i!$ then $m_k\to \infty$?

See also [403]. Lin [Li76] has shown that $f(2,2) \leq 254$.
SOLVED
Let $p$ be an odd prime. Is it true that the equation \[(p-1)!+a^{p-1}=p^k\] has only finitely many solutions?
Erdős and Graham remark that it is probably true that in general $(p-1)!+a^{p-1}$ is rarely a power at all (although this can happen, for example $6!+2^6=28^2$).

Erdős and Graham ask this allowing the case $p=2$, but this is presumably an oversight, since clearly there are infinitely many solutions to this equation when $p=2$.

Brindza and Erdős [BrEr91] proved that are finitely many such solutions. Yu and Liu [YuLi96] showed that the only solutions are \[2!+1^4=3\] \[2!+5^4=3^3\] and \[4!+1^5=5^2.\]

Additional thanks to: Bhavik Mehta and Euro Sampaio
OPEN
Is it true that there are only finitely many powers of $2$ which have only the digits $0$ and $1$ when written in base $3$?
The only examples seem to be $4=1+3$ and $256=1+3+3^2+3^5$. If we only allow the digits $1$ and $2$ then $2^{15}$ seems to be the largest such power of $2$.

This would imply via Kummer's theorem that \[3\mid \binom{2^{k+1}}{2^k}\] for all large $k$.

SOLVED
Let $w(n)$ count the number of solutions to \[n=2^a+3^b+2^c3^d\] with $a,b,c,d\geq 0$ integers. Is it true that $w(n)$ is bounded by some absolute constant?
A conjecture originally due to Newman.

This is true, and was proved by Evertse, Györy, Stewart, and Tijdeman [EGST88].

OPEN
Let $\phi(n)$ be the Euler totient function and $\phi_k(n)$ be the iterated $\phi$ function, so that $\phi_1(n)=\phi(n)$ and $\phi_k(n)=\phi(\phi_{k-1}(n))$. Let \[f(n) = \min \{ k : \phi_k(n)=1\}.\] Does $f(n)/\log n$ have a distribution function? Is $f(n)/\log n$ almost always constant? What can be said about the largest prime factor of $\phi_k(n)$ when, say, $k=\log\log n$?
Pillai [Pi29] was the first to investigate this function, and proved \[\log_3 n < f(n) < \log_2 n\] for all large $n$. Shapiro [Sh50] proved that $f(n)$ is essentially multiplicative.

Erdős, Granville, Pomerance, and Spiro [EGPS90] have proved that the answer to the first two questions is yes, conditional on a form of the Elliott-Halberstam conjecture.

It is likely true that, if $k\to \infty$ however slowly with $n$, then for almost $n$ the largest prime factor of $\phi_k(n)$ is $\leq n^{o(1)}$.

Additional thanks to: Zachary Chase
OPEN
How many iterations of $n\mapsto \phi(n)+1$ are needed before a prime is reached? Can infinitely many $n$ reach the same prime? What is the density of $n$ which reach any fixed prime?
A problem of Finucane. One can also ask about $n\mapsto \sigma(n)-1$.

The number of iterations required is A039651 in the OEIS.

OPEN
Let $\sigma_1(n)=\sigma(n)$, the sum of divisors function, and $\sigma_k(n)=\sigma(\sigma_{k-1}(n))$. Is it true that \[\lim_{k\to \infty} \sigma_k(n)^{1/k}=\infty?\]
OPEN
Let $g_1=g(n)=n+\phi(n)$ and $g_k(n)=g(g_{k-1}(n))$. For which $n$ and $r$ is it true that $g_{k+r}(n)=2g_k(n)$ for all large $k$?
The known solutions to $g_{k+2}(n)=2g_k(n)$ are $n=10$ and $n=94$. Selfridge and Weintraub found solutions to $g_{k+9}(n)=9g_k(n)$ and Weintraub found \[g_{k+25}(3114)=729g_k(3114)\] for all $k\geq 6$.
OPEN
Let $\sigma_1(n)=\sigma(n)$, the sum of divisors function, and $\sigma_k(n)=\sigma(\sigma_{k-1}(n))$.

Is it true that, for every $m,n\geq 2$, there exist some $i,j$ such that $\sigma_i(m)=\sigma_j(n)$?

In [Er79d] Erdős attributes this conjecture to van Wijngaarden, who told it to Erdős in the 1950s.

That is, there is (eventually) only one possible sequence that the iterated sum of divisors function can settle on. Selfridge reports numerical evidence which suggests the answer is no, but Erdős and Graham write 'it seems unlikely that anything can be proved about this in the near future'.

See also [413] and [414].

Additional thanks to: Hayato Egami
OPEN
Let $\omega(n)$ count the number of distinct primes dividing $n$. Are there infinitely many $n$ such that, for all $m<n$, we have $m+\omega(m) \leq n$?

Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \omega(m)\leq n$ for all $m<n$?

In [Er79] Erdős calls such an $n$ a 'barrier' for $\omega$. Some other natural number theoretic functions (such as $\phi$ and $\sigma$) have no barriers because they increase too rapidly. Erdős believed that $\omega$ should have infinitely many barriers. In [Er79d] he proves that $F(n)=\prod k_i$, where $n=\prod p_i^{k_i}$, has infinitely many barriers (in fact the set of barriers has positive density in the integers).

Erdős also believed that $\Omega$, the count of the number of prime factors with multiplicity), should have infinitely many barriers. Selfridge found the largest barrier for $\Omega$ which is $<10^5$ is $99840$.

In [ErGr80] this problem is suggested as a way of showing that the iterated behaviour of $n\mapsto n+\omega(n)$ eventually settles into a single sequence, regardless of the starting value of $n$ (see also [412] and [414]).

Erdős and Graham report it could be attacked by sieve methods, but 'at present these methods are not strong enough'.

See also [647] and [679].

OPEN
Let $h_1(n)=h(n)=n+\tau(n)$ (where $\tau(n)$ counts the number of divisors of $n$) and $h_k(n)=h(h_{k-1}(n))$. Is it true, for any $m,n$, there exist $i$ and $j$ such that $h_i(m)=h_j(n)$?
Asked by Spiro. That is, there is (eventually) only one possible sequence that the iterations of $n\mapsto h(n)$ can settle on. Erdős and Graham believed the answer is yes. Similar questions can be asked by the iterates of many other functions. See also [412] and [413].
OPEN
For any $n$ let $F(n)$ be the largest $k$ such that any of the $k!$ possible ordering patterns appears in some sequence of $\phi(m+1),\ldots,\phi(m+k)$ with $m+k\leq n$. Is it true that \[F(n)=(c+o(1))\log\log\log n\] for some constant $c$? Is the first pattern which fails to appear always \[\phi(m+1)>\phi(m+2)>\cdots \phi(m+k)?\] Is it true that 'natural' ordering which mimics what happens to $\phi(1),\ldots,\phi(k)$ is the most likely to appear?
Erdős [Er36b] proved that \[F(n)\asymp \log\log\log n,\] and similarly if we replace $\phi$ with $\sigma$ or $\tau$ or $\nu$ or any 'decent' additive or multiplicative function.
OPEN
Let $V(x)$ count the number of $n\leq x$ such that $\phi(m)=n$ is solvable. Does $V(2x)/V(x)\to 2$? Is there an asymptotic formula for $V(x)$?
Pillai [Pi29] proved $V(x)=o(x)$. Erdős [Er35b] proved $V(x)=x(\log x)^{-1+o(1)}$.

The behaviour of $V(x)$ is now almost completely understood. Maier and Pomerance [MaPo88] proved \[V(x)=\frac{x}{\log x}e^{(C+o(1))(\log\log\log x)^2},\] for some explicit constant $C>0$. Ford [Fo98] improved this to \[V(x)\asymp\frac{x}{\log x}e^{C_1(\log\log\log x-\log\log\log\log x)^2+C_2\log\log\log x-C_3\log\log\log\log x}\] for some explicit constants $C_1,C_2,C_3>0$. Unfortunately this falls just short of an asymptotic formula for $V(x)$ and determining whether $V(2x)/V(x)\to 2$.

In [Er79e] Erdős asks further to estimate the number of $n\leq x$ such that the smallest solution to $\phi(m)=n$ satisfies $kx<m\leq (k+1)x$.

See also [417] and [821].

Additional thanks to: Kevin Ford
OPEN
Let \[V'(x)=\#\{\phi(m) : 1\leq m\leq x\}\] and \[V(x)=\#\{\phi(m) \leq x : 1\leq m\}.\] Does $\lim V(x)/V'(x)$ exist? Is it $>1$?
It is trivial that $V'(x) \leq V(x)$. In [Er98] Erdős suggests the limit may be infinite. See also [416].
SOLVED
Are there infinitely many integers not of the form $n-\phi(n)$?
Asked by Erdős and Sierpiński. It follows from the Goldbach conjecture that every odd number can be written as $n-\phi(n)$. What happens for even numbers?

Erdős [Er73b] has shown that a positive density set of integers cannot be written as $\sigma(n)-n$.

This is true, as shown by Browkin and Schinzel [BrSc95], who show that any integer of the shape $2^{k}\cdot 509203$ is not of this form. It seems to be open whether there is a positive density set of integers not of this form.

Additional thanks to: Stefan Steinerberger
SOLVED
If $\tau(n)$ counts the number of divisors of $n$, then what is the set of limit points of \[\frac{\tau((n+1)!)}{\tau(n!)}?\]
Erdős and Graham noted that any number of the shape $1+1/k$ for $k\geq 1$ is a limit point (and thus so too is $1$), but knew of no others.

Mehtaab Sawhney has shared the following simple argument that proves that the above limit points are in fact the only ones.

If $v_p(m)$ is the largest $k$ such that $p^k\mid m$ then $\tau(m)=\prod_p (v_p(m)+1)$ and so \[\frac{\tau((n+1)!)}{\tau(n!)} = \prod_{p|n+1}\left(1+\frac{v_p(n+1)}{v_p(n!)+1}\right).\] Note that $v_p(n!)\geq n/p$, and furthermore $n+1$ has $<\log n$ prime divisors, each of which satisfy $v_p(n+1)<\log n$. It follows that the contribution from $p\leq n^{2/3}$ is at most \[\left(1+\frac{\log n}{n^{1/3}}\right)^{\log n}\leq 1+o(1).\]

There is at most one $p\mid n+1$ with $p\geq n^{2/3}$ which (if present) contributes exactly \[\left(1+\frac{1}{\frac{n+1}{p}}\right).\] We have proved the claim, since these two facts combined show that the ratio in question is either $1+o(1)$ or $1+1/k+o(1)$, the latter occurring if $n+1=pk$ for some $p>n^{2/3}$.

After receiving Sawhney's argument I found that this had already been proved, with essentially the same argument, by Erdős, Graham, Ivić, and Pomerance [EGIP].

Additional thanks to: Zachary Chase, Mehtaab Sawhney
OPEN
If $\tau(n)$ counts the number of divisors of $n$ then let \[F(f,n)=\frac{\tau((n+\lfloor f(n)\rfloor)!)}{\tau(n!)}.\] Is it true that \[\lim_{n\to \infty}F((\log n)^C,n)=\infty\] for large $C$? Is it true that $F(\log n,n)$ is everywhere dense in $(1,\infty)$? More generally, if $f(n)\leq \log n$ is a monotonic function then is $F(f,n)$ everywhere dense?
Erdős and Graham write that it is easy to show that $\lim F(n^{1/2},n)=\infty$, and in fact the $n^{1/2}$ can be replaced by $n^{1/2-c}$ for some small constant $c>0$.
OPEN
Is there a sequence $1\leq d_1<d_2<\cdots$ with density $1$ such that all products $\prod_{u\leq i\leq v}d_i$ are distinct?
OPEN
Let $f(1)=f(2)=1$ and for $n>2$ \[f(n) = f(n-f(n-1))+f(n-f(n-2)).\] Does $f(n)$ miss infinitely many integers? What is its behaviour?
Asked by Hofstadter. The sequence begins $1,1,2,3,3,4,\ldots$ and is A005185 in the OEIS. It is not even known whether $f(n)$ is well-defined for all $n$.
OPEN
Let $a_1=1$ and $a_2=2$ and for $k\geq 3$ we choose $a_k$ to be the least integer $>a_{k-1}$ which is the sum of at least two consecutive terms of the sequence. What is the asymptotic behaviour of this sequence?
Asked by Hofstadter. The sequence begins $1,2,3,5,6,8,10,11,\ldots$ and is A005243 in the OEIS.
OPEN
Let $a_1=2$ and $a_2=3$ and continue the sequence by appending to $a_1,\ldots,a_n$ all possible values of $a_ia_j-1$ with $i\neq j$. Is it true that the set of integers which eventually appear has positive density?
Asked by Hofstadter. The sequence begins $2,3,5,9,14,17,26,\ldots$ and is A005244 in the OEIS. This problem is also discussed in section E31 of Guy's book Unsolved Problems in Number Theory.

In [ErGr80] (and in Guy's book) this problem as written is asking for whether almost all integers appear in this sequence, but the answer to this is trivially no (as pointed out to me by Steinerberger): no integer $\equiv 1\pmod{3}$ is ever in the sequence, so the set of integers which appear has density at most $2/3$. This is easily seen by induction, and the fact that if $a,b\in \{0,2\}\pmod{3}$ then $ab-1\in \{0,2\}\pmod{3}$.

Presumably it is the weaker question of whether a positive density of integers appear (as correctly asked in [Er77c]) that was also intended in [ErGr80].

Additional thanks to: Mehtaab Sawhney, Stefan Steinerberger
OPEN
Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that the products $ab$ are distinct for all $a<b$. Is there a constant $c$ such that \[F(n)=\pi(n)+(c+o(1))n^{3/4}(\log n)^{-3/2}?\]

If $A\subseteq \{1,\ldots,n\}$ is such that all products $a_1\cdots a_r$ are distinct for $a_1<\cdots <a_r$ then is it true that \[\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?\]

Erdős [Er68] proved that there exist some constants $0<c_1\leq c_2$ such that \[\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.\] Surprisingly, if we consider the corresponding problem in the reals (so consider the largest $A\subset [1,x]$ such that for any distinct $a,b,c,d\in A$ we have $\lvert ab-cd\rvert \geq 1$) then Alexander proved that $\lvert A\rvert> x/8e$ is possible (disproving an earlier conjecture of Erdős [Er73] that $m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is.

See also [490], [793], and [796].

Additional thanks to: Rishika Agrawal
SOLVED
Is it true that, for every $n$ and $d$, there exists $k$ such that \[d \mid p_{n+1}+\cdots+p_{n+k},\] where $p_r$ denotes the $r$th prime?
Cedric Pilatte has observed that a positive solution to this follows from a result of Shiu [Sh00]: for any $k\geq 1$ and $(a,q)=1$ there exist infinitely many $k$-tuples of consecutive primes $p_m,\ldots,p_{m+{k-1}}$ all of which are congruent to $a$ modulo $q$.

Indeed, we apply this with $k=q=d$ and $a=1$ and let $p_m,\ldots,p_{m+{d-1}}$ be consecutive primes all congruent to $1$ modulo $d$, with $m>n+1$. If $p_{n+1}+\cdots+p_{m-1}\equiv r\pmod{d}$ with $1\leq r\leq d$ then \[d \mid p_{n+1}+\cdots +p_m+\cdots+p_{m+d+r-1}.\]

Additional thanks to: Sarosh Adenwalla and Cedric Pilatte
OPEN
Is there a set $A\subseteq \mathbb{N}$ such that, for infinitely many $n$, all of $n-a$ are prime for all $a\in A$ with $0<a<n$ and \[\liminf\frac{\lvert A\cap [1,x]\rvert}{\pi(x)}>0?\]
Erdős and Graham could show this is true (assuming the prime $k$-tuple conjecture) if we replace $\liminf$ by $\limsup$.
SOLVED
Is it true that, if $A\subseteq \mathbb{N}$ is sparse enough and does not cover all residue classes modulo $p$ for any prime $p$, then there exists some $n$ such that $n+a$ is prime for all $a\in A$?
Weisenberg [We24] has shown the answer is no: $A$ can be arbitrarily sparse and missing at least one residue class modulo every prime $p$, and yet $A+n$ is not contained in the primes for any $n\in \mathbb{Z}$. (Weisenberg gives several constructions of such an $A$.)
OPEN
Fix some integer $n$ and define a decreasing sequence in $[1,n)$ by $a_1=n-1$ and, for $k\geq 2$, letting $a_k$ be the greatest integer in $[1,a_{k-1})$ such that all of the prime factors of $a_k$ are $>n-a_k$.

Is it true that, for sufficiently large $n$, not all of this sequence can be prime?

Erdős and Graham write 'preliminary calculations made by Selfridge indicate that this is the case but no proof is in sight'. For example if $n=8$ we have $a_1=7$ and $a_2=5$ and then must stop.

Sarosh Adenwalla has observed that this problem is equivalent to (the first part of) [385]. Indeed, assuming a positive answer to that, for all large $n$, there exists a composite $m<n$ such that all primes dividing $m$ are $>n-m$. It follows that such an $m$ is equal to some $a_i$ in the sequence defined for $[1,n)$, and $m$ is composite by assumption.

Additional thanks to: Sarosh Adenwalla
OPEN
Are there two infinite sets $A$ and $B$ such that $A+B$ agrees with the set of prime numbers up to finitely many exceptions?
A problem of Ostmann, sometimes known as the 'inverse Goldbach problem'. The answer is surely no. The best result in this direction is due to Elsholtz and Harper [ElHa15], who showed that if $A,B$ are such sets then for all large $x$ we must have \[\frac{x^{1/2}}{\log x\log\log x} \ll \lvert A \cap [1,x]\rvert \ll x^{1/2}\log\log x\] and similarly for $B$.

Elsholtz [El01] has proved there are no infinite sets $A,B,C$ such that $A+B+C$ agrees with the set of prime numbers up to finitely many exceptions.

See also [432].

OPEN
Let $A,B\subseteq \mathbb{N}$ be two infinite sets. How dense can $A+B$ be if all elements of $A+B$ are pairwise relatively prime?
Asked by Straus, inspired by a problem of Ostmann (see [431]).
OPEN
If $A\subset \mathbb{N}$ is a finite set then let $G(A)$ denote the greatest integer which is not expressible as a finite sum of elements from $A$ (with repetitions allowed). Let \[g(n,t)=\max G(A)\] where the maximum is taken over all $A\subseteq \{1,\ldots,t\}$ of size $\lvert A\rvert=n$ which has no common divisor. Is it true that \[g(n,t)\sim \frac{t^2}{n-1}?\]
This type of problem is associated with Frobenius. Erdős and Graham [ErGr72] proved $g(n,t)<2t^2/n$, and there are examples which show that \[g(n,t) \geq \frac{t^2}{n-1}-5t\] for $n\geq 2$.

The problem is written as Erdős and Graham describe it, but presumably they had in mind the regime where $n$ is fixed and $t\to \infty$.

OPEN
Let $k\leq n$. What choice of $A\subseteq \{1,\ldots,n\}$ of size $\lvert A\rvert=k$ maximises the number of integers not representable as the sum of finitely many elements from $A$ (with repetitions allowed)? Is it $\{n,n-1,\ldots,n-k+1\}$?
Associated with problems of Frobenius.
OPEN
Let $n\in\mathbb{N}$ with $n\neq p^k$ for any prime $p$ and $k\geq 0$. What is the largest integer not of the form \[\sum_{1\leq i<n}c_i\binom{n}{i}\] where the $c_i\geq 0$ are integers?
OPEN
If $p$ is a prime and $k,m\geq 2$ then let $r(k,m,p)$ be the minimal $r$ such that $r,r+1,\ldots,r+m-1$ are all $k$th power residues modulo $p$. Let \[\Lambda(k,m)=\limsup_{p\to \infty} r(k,m,p).\] Is it true that $\Lambda(k,2)$ is finite for all $k$? Is $\Lambda(k,3)$ finite for all odd $k$? How large are they?
Asked by Lehmer and Lehmer [LeLe62]. For example $\Lambda(2,2)=9$ and $\Lambda(3,2)=77$. It is known that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k$.

This has been partially resolved: Hildebrand [Hi91] has shown that $\Lambda(k,2)$ is finite for all $k$.

SOLVED
Let $1\leq a_1<\cdots<a_k\leq x$. How many of the partial products $a_1,a_1a_2,\ldots,a_1\cdots a_k$ can be squares? Is it true that, for any $\epsilon>0$, there can be more than $x^{1-\epsilon}$ squares?
Erdős and Graham write it is 'trivial' that there are $o(x)$ many such squares, although this is not quite trivial, using Siegel's theorem.

A positive answer follows from work of Bui, Pratt, and Zaharescu [BPZ24], as noted by Tao in this blog post. In particular Tao shows that, if $L(x)$ is the maximal number of such squares possible, and $u(x)=(\log x\log\log x)^{1/2}$, then \[x\exp(-(2^{1/2}+o(1))u(x)) \leq L(x) \leq x\exp(-(2^{-1/2}+o(1))u(x)).\]

See also [841].

SOLVED
How large can $A\subseteq \{1,\ldots,N\}$ be if $A+A$ contains no square numbers?
Taking all integers $\equiv 1\pmod{3}$ shows that $\lvert A\rvert\geq N/3$ is possible. This can be improved to $\tfrac{11}{32}N$ by taking all integers $\equiv 1,5,9,13,14,17,21,25,26,29,30\pmod{32}$, as observed by Massias.

Lagarias, Odlyzko, and Shearer [LOS83] proved this is sharp for the modular version of the problem; that is, if $A\subseteq \mathbb{Z}/N\mathbb{Z}$ is such that $A+A$ contains no squares then $\lvert A\rvert\leq \tfrac{11}{32}N$. They also prove the general upper bound of $\lvert A\rvert\leq 0.475N$ for the integer problem.

In fact $\frac{11}{32}$ is sharp in general, as shown by Khalfalah, Lodha, and Szemerédi [KLS02], who proved that the maximal such $A$ satisfies $\lvert A\rvert\leq (\tfrac{11}{32}+o(1))N$.

See also [439] and [587].

SOLVED
Is it true that, in any finite colouring of the integers, there must be two integers $x\neq y$ of the same colour such that $x+y$ is a square? What about a $k$th power?
A question of Roth, Erdős, Sárközy, and Sós [ESS89] (according to some reports, although in [Er80c] Erdős claims this arose in a conversation with Silverman in 1977). Erdős, Sárközy, and Sós [ESS89] proved this for $2$ or $3$ colours.

In other words, if $G$ is the infinite graph on $\mathbb{N}$ where we connect $m,n$ by an edge if and only if $n+m$ is a square, then is the chromatic number of $G$ equal to $\aleph_0$?

This is true, as proved by Khalfalah and Szemerédi [KhSz06], who in fact prove the general result with $x+y=z^2$ replaced by $x+y=f(z)$ for any non-constant $f(z)\in \mathbb{Z}[z]$ such that $2\mid f(z)$ for some $z\in \mathbb{Z}$.

See also [438].

Additional thanks to: Deepak Bal
OPEN
Let $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$ be infinite and let $A(x)$ count the number of indices for which $\mathrm{lcm}(a_i,a_{i+1})\leq x$. Is it true that $A(x) \ll x^{1/2}$? How large can \[\liminf \frac{A(x)}{x^{1/2}}\] be?
It is easy to give a sequence with \[\limsup\frac{A(x)}{x^{1/2}}=c>0.\] There are related results (particularly for the more general case of $\mathrm{lcm}(a_i,a_{i+1},\ldots,a_{i+k})$) in a paper of Erdős and Szemerédi [ErSz80].
Additional thanks to: Zachary Chase
SOLVED
Let $N\geq 1$. What is the size of the largest $A\subset \{1,\ldots,N\}$ such that $\mathrm{lcm}(a,b)\leq N$ for all $a,b\in A$?

Is it attained by choosing all integers in $[1,(N/2)^{1/2}]$ together with all even integers in $[(N/2)^{1/2},(2N)^{1/2}]$?

Let $g(N)$ denote the size of the largest such $A$. The construction mentioned proves that \[g(N) \geq \left(\tfrac{9}{8}n\right)^{1/2}+O(1).\] Erdős [Er51b] proved $g(N) \leq (4n)^{1/2}+O(1)$, which was improved by Choi [Ch72b]. Chen [Ch98] established the asymptotic \[g(N) \sim \left(\tfrac{9}{8}n\right)^{1/2}.\] Chen and Dai [DaCh06] proved that \[g(N)\leq \left(\tfrac{9}{8}n\right)^{1/2}+O\left(\left(\frac{N}{\log N}\right)^{1/2}\log\log N\right).\] In [ChDa07] the same authors prove that, infinitely often, Erdős' construction is not optimal: if $B$ is that construction and $A$ is such that $\lvert A\rvert=g(N)$ then, for infinitely many $N$, \[\lvert A\rvert\geq \lvert B\rvert+t,\] where $t\geq 0$ is defined such that the $t$-fold iterated logarithm of $N$ is in $[0,1)$.
Additional thanks to: Terence Tao
SOLVED
Is it true that if $A\subseteq\mathbb{N}$ is such that \[\frac{1}{\log\log x}\sum_{n\in A\cap [1,x)}\frac{1}{n}\to \infty\] then \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\to \infty?\]
Tao [Ta24b] has shown this is false: there exists $A\subset\mathbb{N}$ such that \[\sum_{n\in A\cap [1,x)}\frac{1}{n}\gg \exp((\tfrac{1}{2}+o(1))\sqrt{\log\log x}\log\log\log x)\] and \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\ll 1.\] Moreover, Tao shows this is the best possible result, in that if $\sum_{n\in A\cap [1,x)}\frac{1}{n}$ grows faster than $\exp(O(\sqrt{\log\log x}\log\log\log x))$ then \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\to \infty.\]
OPEN
Let $m,n\geq 1$. What is \[\# \{ k(m-k) : 1\leq k\leq m/2\} \cap \{ l(n-l) : 1\leq l\leq n/2\}?\] Can it be arbitrarily large? Is it $\leq (mn)^{o(1)}$ for all suffiicently large $m,n$?
SOLVED
Let $A\subseteq\mathbb{N}$ be infinite and $d_A(n)$ count the number of $a\in A$ which divide $n$. Is it true that, for every $k$, \[\limsup_{x\to \infty} \frac{\max_{n<x}d_A(n)}{\left(\sum_{n\in A\cap[1,x)}\frac{1}{n}\right)^k}=\infty?\]
The answer is yes, proved by Erdős and Sárkőzy [ErSa80].
OPEN
Is it true that, for any $c>1/2$, if $p$ is a large prime and $n$ is sufficiently large (both depending on $c$) then there exist $a,b\in(n,n+p^c)$ such that $ab\equiv 1\pmod{p}$?
An unpublished result of Heilbronn guarantees this for $c$ sufficiently close to $1$.
SOLVED
Let $\delta(n)$ denote the density of integers which are divisible by some integer in $(n,2n)$. What is the growth rate of $\delta(n)$?

If $\delta'(n)$ is the density of integers which have exactly one divisor in $(n,2n)$ then is it true that $\delta'(n)=o(\delta(n))$?

Besicovitch [Be34] proved that $\liminf \delta(n)=0$. Erdős [Er35] proved that $\delta(n)=o(1)$. Erdős [Er60] proved that $\delta(n)=(\log n)^{-\alpha+o(1)}$ where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\] This estimate was refined by Tenenbaum [Te84], and the true growth rate of $\delta(n)$ was determined by Ford [Fo08] who proved \[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}.\]

Among many other results in [Fo08], Ford also proves that the second conjecture is false, and more generally that if $\delta_r(n)$ is the density of integers with exactly $r$ divisors in $(n,2n)$ then $\delta_r(n)\gg_r\delta(n)$.

See also [448], [692], and [693].

Additional thanks to: Zachary Chase and Kevin Ford
SOLVED
Let $\tau(n)$ count the divisors of $n$ and $\tau^+(n)$ count the number of $k$ such that $n$ has a divisor in $[2^k,2^{k+1})$. Is it true that, for all $\epsilon>0$, \[\tau^+(n) < \epsilon \tau(n)\] for almost all $n$?
This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$).

A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll\epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function.

Erdős and Graham also asked whether there is a good inequality known for $\sum_{n\leq x}\tau^+(n)$. This was provided by Ford [Fo08] who proved \[\sum_{n\leq x}\tau^+(n)\asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}}\] where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]

See also [446] and [449].

Additional thanks to: Kevin Ford
SOLVED
Let $r(n)$ count the number of $d_1,d_2$ such that $d_1\mid n$ and $d_2\mid n$ and $d_1<d_2<2d_1$. Is it true that, for every $\epsilon>0$, \[r(n) < \epsilon \tau(n)\] for almost all $n$, where $\tau(n)$ is the number of divisors of $n$?
This is false - indeed, for any constant $K>0$ we have $r(n)>K\tau(n)$ for a positive density set of $n$. Kevin Ford has observed this follows from the negative solution to [448]: the Cauchy-Schwarz inequality implies \[r(n)+\tau(n)\geq \tau(n)^2/\tau^+(n)\] where $\tau^+(n)$ is as defined in [448], and the negative solution to [448] implies the right-hand side is at least $(K+1)\tau(n)$ for a positive density set of $n$. (This argument is given for an essentially identical problem by Hall and Tenenbaum [HaTe88], Section 4.6.)

See also [448].

Additional thanks to: Kevin Ford
OPEN
How large must $y=y(\epsilon,n)$ be such that the number of integers in $(x,x+y)$ with a divisor in $(n,2n)$ is at most $\epsilon y$?
OPEN
Estimate $n_k$, the smallest integer such that $\prod_{1\leq i\leq k}(n_k-i)$ has no prime factor in $(k,2k)$.
Erdős and Graham write 'we can prove $n_k>k^{1+c}$ but no doubt much more is true'.

In [Er79d] Erdős writes that probably $n_k<e^{o(k)}$ but $n_k>k^d$ for all constant $d$.

OPEN
Let $\omega(n)$ count the number of distinct prime factors of $n$. What is the size of the largest interval $I\subseteq [x,2x]$ such that $\omega(n)>\log\log n$ for all $n\in I$?
Erdős [Er37] proved that the density of integers $n$ with $\omega(n)>\log\log n$ is $1/2$. The Chinese remainder theorem implies that there is such an interval with \[\lvert I\rvert \geq (1+o(1))\frac{\log x}{(\log\log x)^2}.\] It could be true that there is such an interval of length $(\log x)^{k}$ for arbitrarily large $k$.
SOLVED
Is it true that, for all sufficiently large $n$, \[p_n^2 \leq p_{n+i}p_{n-i}\] for all $i<n$, where $p_k$ is the $k$th prime?
Asked by Erdős and Straus. The answer is no, as shown by Pomerance [Po79].
OPEN
Let \[f(n) = \min_{i<n} (p_{n+i}+p_{n-i}),\] where $p_k$ is the $k$th prime. Is it true that \[\limsup_n (f(n)-2p_n)=\infty?\]
Pomerance [Po79] has proved the $\limsup$ is at least $2$.
OPEN
Let $q_1<q_2<\cdots$ be a sequence of primes such that \[q_{n+1}-q_n\geq q_n-q_{n-1}.\] Must \[\lim_n \frac{q_n}{n^2}=\infty?\]
Richter [Ri76] proved that \[\liminf_n \frac{q_n}{n^2}>0.352\cdots.\]
Additional thanks to: Terence Tao
OPEN
Let $p_n$ be the smallest prime $\equiv 1\pmod{n}$ and let $m_n$ be the smallest integer such that $n\mid \phi(m_n)$. Is it true that $p_n>m_n$ for almost all $n$? Does $p_n/m_n\to \infty$ for almost all $n$? Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?
Linnik's theorem implies that $p_n\leq n^{O(1)}$. Erdős [Er79e] writes it is 'easy to show' that for infinitely many $n$ we have $p_n <m_n$.
OPEN
Is there some $\epsilon>0$ such that there are infinitely many $n$ where all primes $p\leq (2+\epsilon)\log n$ divide \[\prod_{1\leq i\leq \log n}(n+i)?\]
A problem of Erdős and Pomerance.

More generally, let $q(n,k)$ denote the least prime which does not divide $\prod_{1\leq i\leq k}(n+i)$. This problem asks whether $q(n,\log n)\geq (2+\epsilon)\log n$ infinitely often. Taking $n$ to be the product of primes between $\log n$ and $(2+o(1))\log n$ gives an example where \[q(n,\log n)\geq (2+o(1))\log n.\]

Can one prove that $q(n,\log n)<(1-\epsilon)(\log n)^2$ for all large $n$ and some $\epsilon>0$?

See also [663].

OPEN
Let $[1,\ldots,n]$ denote the least common multiple of $\{1,\ldots,n\}$. Is it true that, for all $k\geq 1$, \[[1,\ldots,p_{k+1}-1]< p_k[1,\ldots,p_k]?\]
Erdős and Graham write this is 'almost certainly' true, but the proof is beyond our ability, for two reasons (at least):
  • Firstly, one has to rule out the possibility of many primes $q$ such that $p_k<q^2<p_{k+1}$. There should be at most one such $q$, which would follow from $p_{k+1}-p_k<p_k^{1/2}$, which is essentially the notorious Legendre's conjecture.
  • The small primes also cause trouble.
Additional thanks to: Zachary Chase
OPEN
Let $f(u)$ be the largest $v$ such that no $m\in (u,v)$ is composed entirely of primes dividing $uv$. Estimate $f(u)$.
OPEN
Let $a_0=n$ and $a_1=1$, and in general $a_k$ is the least integer $>a_{k-1}$ for which $(n-a_k,n-a_i)=1$ for all $1\leq i<k$. Does \[\sum_{i}\frac{1}{a_i}\to \infty\] as $n\to \infty$? What about if we restrict the sum to those $i$ such that $n-a_j$ is divisible by some prime $\leq a_j$, or the complement of such $i$?
This question arose in work of Eggleton, Erdős, and Selfridge.
OPEN
Let $s_t(n)$ be the $t$-smooth component of $n$ - that is, the product of all primes $p$ (with multiplicity) dividing $n$ such that $p<t$. Let $f(n,t)$ count the number of distinct possible values for $s_t(m)$ for $m\in [n+1,n+t]$. Is it true that \[f(n,t)\gg t\] (uniformly, for all $t$ and $n$)?
Erdős and Graham report they can show \[f(n,t) \gg \frac{t}{\log t}.\]
OPEN
Let $p(n)$ denote the least prime factor of $n$. There is a constant $c>0$ such that \[\sum_{\substack{n<x\\ n\textrm{ not prime}}}\frac{p(n)}{n}\sim c\frac{x^{1/2}}{(\log x)^2}.\] Is it true that there exists a constant $C>0$ such that \[\sum_{x\leq n\leq x+Cx^{1/2}(\log x)^2}\frac{p(n)}{n} \gg 1\] for all large $x$?
Additional thanks to: Zachary Chase
OPEN
Is there a function $f$ with $f(n)\to \infty$ as $n\to \infty$ such that, for all large $n$, there is a composite number $m$ such that \[n+f(n)<m<n+p(m)?\] (Here $p(m)$ is the least prime factor of $m$.)
SOLVED
Let $A=\{n_1<n_2<\cdots\}\subset \mathbb{N}$ be a lacunary sequence (so there exists some $\epsilon>0$ with $n_{k+1}\geq (1+\epsilon)n_k$ for all $k$). Must there exist an irrational $\theta$ such that \[\{ \|\theta n_k\| : k\geq 1\}\] is not dense in $[0,1]$ (where $\| x\|$ is the distance to the nearest integer)?
Solved independently by de Mathan [dM80] and Pollington [Po79b], who showed that, given any such $A$, there exists such a $\theta$, with \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon^4}{\log(1/\epsilon)}.\] This bound was improved by Katznelson [Ka01], Akhunzhanov and Moshchevitin [AkMo04], and Dubickas [Du06], before Peres and Schlag [PeSc10] improved it to \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon}{\log(1/\epsilon)},\] and note that the best bound possible here would be $\gg \epsilon$.

This problem has consequences for [894].

Additional thanks to: Euro Vidal Sampaio
SOLVED
Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is it true that, for any $0<\delta<1/2$, we have \[N(X,\delta)=o(X)?\] In fact, is it true that (for any fixed $\delta>0$) \[N(X,\delta)<X^{1/2+o(1)}?\]

The first conjecture was proved by Sárközy [Sa76], who in fact proved \[N(X,\delta) \ll \delta^{-3}\frac{X}{\log\log X}.\]

Konyagin [Ko01] proved the strong upper bound \[N(X,\delta) \ll_\delta N^{1/2}.\]

See also [466] for lower bounds.

Additional thanks to: Stefan Steinerberger
SOLVED
Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is there some $\delta>0$ such that \[\lim_{x\to \infty}N(X,\delta)=\infty?\]

Graham proved this is true, and in fact \[N(X,1/10)> \frac{\log X}{10}.\] This was substantially improved by Sárközy [Sa76], who proved that for, all sufficiently small $\delta>0$, \[N(X,\delta)>X^{1/2-\delta^{1/7}}.\] See also [465] for upper bounds.
OPEN
Prove the following for all large $x$: there is a choice of congruence classes $a_p$ for all primes $p\leq x$ and a decomposition $\{p\leq x\}=A\sqcup B$ into two non-empty sets such that, for all $n<x$, there exist some $p\in A$ and $q\in B$ such that $n\equiv a_p\pmod{p}$ and $n\equiv a_q\pmod{q}$.
This is what I assume the intended problem is, although the presentation in [ErGr80] is missing some crucial quantifiers, so I may have misinterpreted it.
OPEN
For any $n$ let $D_n$ be the set of sums of the shape $d_1,d_1+d_2,d_1+d_2+d_3,\ldots$ where $1<d_1<d_2<\cdots$ are the divisors of $n$.

What is the size of $D_n\backslash \cup_{m<n}D_m$?

If $f(N)$ is the minimal $n$ such that $N\in D_n$ then is it true that $f(N)=o(N)$? Perhaps just for almost all $N$?

OPEN
Let $A$ be the set of all $n$ such that $n=d_1+\cdots+d_k$ with $d_i$ distinct proper divisors of $n$, but this is not true for any $m\mid n$ with $m<n$. Does \[\sum_{n\in A}\frac{1}{n}\] converge?
The same question can be asked for those $n$ which do not have distinct sums of sets of divisors, but any proper divisor of $n$ does.
Additional thanks to: Zachary Chase
OPEN
Call $n$ weird if $\sigma(n)\geq 2n$ and $n\neq d_1+\cdots+d_k$, where the $d_i$ are distinct proper divisors of $n$. Are there any odd weird numbers? Are there infinitely many primitive weird numbers, i.e. those such that no proper divisor of $n$ is weird?
Weird numbers were investigated by Benkoski and Erdős [BeEr74], who proved that the set of weird numbers has positive density.

Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on various well-known conjectures on the distribution of prime gaps. For example, it would suffice to show that $p_{n+1}-p_n <\frac{1}{10}p_n^{1/2}$ for sufficiently large $n$.

The sequence of weird numbers is A006037 in the OEIS. There are no odd weird numbers below $10^{17}$.

SOLVED
Given a finite set of primes $Q=Q_0$, define a sequence of sets $Q_i$ by letting $Q_{i+1}$ be $Q_i$ together with all primes formed by adding three distinct elements of $Q_i$. Is there some initial choice of $Q$ such that the $Q_i$ become arbitrarily large?
A problem of Ulam. In particular, what about $Q=\{3,5,7,11\}$?

Mrazović and Kovač, and independently Alon, have observed that the existence of some valid choice of $Q$ follows easily from Vinogradov's theorem that every large odd integer is the sum of three distinct primes. In particular, there exists some $N$ such that every prime $>N$ is the sum of three distinct (smaller) primes. We may then take $Q_0$ to be the set of all primes $\leq N$ (in which case all primes are eventually in some $Q_i$).

Additional thanks to: Noga Alon, Rudi Mrazovic, and Vjekoslav Kovac
OPEN
Given some initial finite sequence of primes $q_1<\cdots<q_m$ extend it so that $q_{n+1}$ is the smallest prime of the form $q_n+q_i-1$ for $n\geq m$. Is there an initial starting sequence so that the resulting sequence is infinite?
A problem due to Ulam. For example if we begin with $3,5$ then the sequence continues $3,5,7,11,13,17,\ldots$. It is possible that this sequence is infinite.
SOLVED
Is there a permutation $a_1,a_2,\ldots$ of the positive integers such that $a_k+a_{k+1}$ is always prime?
Asked by Segal. The answer is yes, as shown by Odlyzko.

Watts has suggested that perhaps the obvious greedy algorithm defines such a permutation - that is, let $a_1=1$ and let \[a_{n+1}=\min \{ x : a_n+x\textrm{ is prime and }x\neq a_i\textrm{ for }i\leq n\}.\] In other words, do all positive integers occur as some such $a_n$? Do all primes occur as a sum?

OPEN
Let $p$ be a prime. Given any finite set $A\subseteq \mathbb{F}_p\backslash \{0\}$, is there always a rearrangement $A=\{a_1,\ldots,a_t\}$ such that all partial sums $\sum_{1\leq k\leq m}a_{k}$ are distinct, for all $1\leq m\leq t$?
A problem of Graham, who proved it when $t=p-1$. A similar conjecture was made for arbitrary abelian groups by Alspach. Such an ordering is often called a valid ordering.

This has been proved for $t\leq 12$ (see Costa and Pellegrini [CoPe20] and the references therein) and for $p-3\leq t\leq p-1$ (see Hicks, Ollis, and Schmitt [HOS19] and the references therein). Kravitz [Kr24] has proved this for \[t \leq \frac{\log p}{\log\log p}.\] (This was independently earlier observed by Will Sawin in a MathOverflow post.)

Bedert and Kravitz [BeKr24] have now proved this conjecture for \[t \leq e^{(\log p)^{1/4}}.\]

Additional thanks to: Zachary Chase and Noah Kravitz
SOLVED
Let $A\subseteq \mathbb{F}_p$. Let \[A\hat{+}A = \{ a+b : a\neq b \in A\}.\] Is it true that \[\lvert A\hat{+}A\rvert \geq \min(2\lvert A\rvert-3,p)?\]
A question of Erdős and Heilbronn. Solved in the affirmative by da Silva and Hamidoune [dSHa94].
OPEN
Let $f:\mathbb{Z}\to \mathbb{Z}$ be a polynomial of degree at least $2$. Is there a set $A$ such that every $z\in \mathbb{Z}$ has exactly one representation as $z=a+f(n)$ for some $a\in A$ and $n\in \mathbb{Z}$?
Probably there is no such $A$ for any polynomial $f$.
OPEN
Let $p$ be a prime and \[A_p = \{ k! \pmod{p} : 1\leq k<p\}.\] Is it true that \[\lvert A_p\rvert \sim (1-\tfrac{1}{e})p?\]
Additional thanks to: Zachary Chase
OPEN
Is it true that, for all $k\neq 1$, there are infinitely many $n$ such that $2^n\equiv k\pmod{n}$?
A conjecture of Graham. It is easy to see that $2^n\not\equiv 1\mod{n}$ for all $n>1$, so the restriction $k\neq 1$ is necessary. Erdős and Graham report that Graham, Lehmer, and Lehmer have proved this for $k=2^i$ for $i\geq 1$, or if $k=-1$, but I cannot find such a paper.

As an indication of the difficulty, when $k=3$ the smallest $n$ such that $2^n\equiv 3\pmod{n}$ is $n=4700063497$.

The minimal such $n$ for each $k$ is A036236 in the OEIS.

SOLVED
Let $x_1,x_2,\ldots\in [0,1]$ be an infinite sequence. Is it true that there are infinitely many $m,n$ such that \[\lvert x_{m+n}-x_n\rvert \leq \frac{1}{\sqrt{5}n}?\]
A conjecture of Newman. This was proved Chung and Graham, who in fact show that for any $\epsilon>0$ there must exist some $n$ such that there are infinitely many $m$ for which \[\lvert x_{m+n}-x_m\rvert < \frac{1}{(c-\epsilon)n}\] where \[c=1+\sum_{k\geq 1}\frac{1}{F_{2k}}=2.535\cdots\] and $F_m$ is the $m$th Fibonacci number. This constant is best possible.
OPEN
Let $a_1,\ldots,a_r,b_1,\ldots,b_r\in \mathbb{N}$ such that $\sum_{i}\frac{1}{a_i}>1$. For any finite sequence of $n$ (not necessarily distinct) integers $A=(x_1,\ldots,x_n)$ let $T(A)$ denote the sequence of length $rn$ given by \[(a_ix_j+b_i)_{1\leq j\leq n, 1\leq i\leq r}.\] Prove that, if $A_1=(1)$ and $A_{i+1}=T(A_i)$, then there must be some $A_k$ with repeated elements.
Erdős and Graham write that 'it is surprising that [this problem] offers difficulty'.

The original formulation of this problem had an extra condition on the minimal element of the sequence $A_k$ being large, but Ryan Alweiss has pointed out that is trivially always satisfied since the minimal element of the sequence must grow by at least $1$ at each stage.

Additional thanks to: Ryan Alweiss, Zachary Chase
SOLVED
Define a sequence by $a_1=1$ and \[a_{n+1}=\lfloor\sqrt{2}(a_n+1/2)\rfloor\] for $n\geq 1$. The difference $a_{2n+1}-2a_{2n-1}$ is the $n$th digit in the binary expansion of $\sqrt{2}$.

Find similar results for $\theta=\sqrt{m}$, and other algebraic numbers.

The result for $\sqrt{2}$ was obtained by Graham and Pollak [GrPo70]. The problem statement is open-ended, but presumably Erdős and Graham would have been satisfied with the wide-ranging generalisations of Stoll ([St05] and [St06]).
SOLVED
Is there a covering system such that no two of the moduli divide each other?
Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7]). The answer is no, as proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].
OPEN
Let $M(n,k)=[n+1,\ldots,n+k]$ be the least common multiple of $\{n+1,\ldots,n+k\}$.

Is it true that for all $m\geq n+k$ \[M(n,k) \neq M(m,k)?\]

The Thue-Siegel theorem implies that, for fixed $k$, there are only finitely many $m,n$ such that $m\geq n+k$ and $M(n,k)=M(m,k)$.

In general, how many solutions does $M(n,k)=M(m,l)$ have when $m\geq n+k$ and $l>1$? Erdős expects very few (and none when $l\geq k$).

The only solutions Erdős knew were $M(4,3)=M(13,2)$ and $M(3,4)=M(19,2)$.

In [Er79d] Erdős conjectures the stronger fact that (aside from a finite number of exceptions) if $k>2$ and $m\geq n+k$ then $\prod_{i\leq k}(n+i)$ and $\prod_{i\leq k}(m+i)$ cannot have the same set of prime factors.

See also [678], [686], and [850].