Logo
All Random Solved Random Open
7 solved out of 17 shown (show only solved or open)
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
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
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 $s_1<s_2<\cdots$ be the sequence of squarefree numbers. Is it true that, for any $\alpha \geq 0$, \[\lim_{x\to \infty}\frac{1}{x}\sum_{s_n\leq x}(s_{n+1}-s_n)^\alpha\] exists?
Erdős [Er51] proved this for all $0\leq \alpha \leq 2$, and Hooley [Ho73] extended this to all $\alpha \leq 3$.

See also [208].

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 $s_1<s_2<\cdots$ be the sequence of squarefree numbers. Is it true that, for any $\epsilon>0$ and large $n$, \[s_{n+1}-s_n \ll_\epsilon s_n^{\epsilon}?\] Is it true that \[s_{n+1}-s_n \leq (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n}?\]
Erdős [Er51] showed that there are infinitely many $n$ such that \[s_{n+1}-s_n > (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n},\] so this bound would be the best possible.

In [Er79] Erdős says perhaps $s_{n+1}-s_n \ll \log s_n$, but he is 'very doubtful'.

Filaseta and Trifonov [FiTr92] proved an upper bound of $s_n^{1/5}$. Pandey [Pa24] has improved this exponent to $1/5-c$ for some constant $c>0$.

See also [489] and [145].

Additional thanks to: Zachary Chase
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
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
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 $\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].

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
OPEN
Let $\tau(n)$ count the number of divisors of $n$. Is there some $n>24$ such that \[\max_{m<n}(m+\tau(m))\leq n+2?\]
A problem of Erdős and Selfridge. This is true for $n=24$. The $n+2$ is best possible here since \[\max(\tau(n-1)+n-1,\tau(n-2)+n-2)\geq n+2.\]

In [Er79] Erdős says 'it is extremely doubtful' that there are infinitely many such $n$, and in fact suggets that \[\lim_{n\to \infty}\max_{m<n}(\tau(m)+m-n)=\infty.\]

In [Er79d] Erdős says it 'seems certain' that for every $k$ there are infinitely many $n$ for which \[\max_{n-k<m<n}(m+\tau(m))\leq n+2,\] but 'this is hopeless with our present methods', although it follows from Schinzel's Hypothesis H.

See also [413].

SOLVED
Are there any integer solutions to $x^xy^y=z^z$ with $x,y,z>1$?
Ko [Ko40] proved there are none if $(x,y)=1$, but there are in fact infinitely many solutions in general - for example, \[x=2^{12}3^6, y = 2^83^8,\textrm{ and } z = 2^{11}3^7.\] More generally, writing $a=2^{n+1}$ and $b=2^n-1$, \[x = 2^{a(b-n)}b^{2b}\cdot 2^{2n},\] \[y = 2^{a(b-n)}b^{2b}\cdot b^2,\] and \[z = 2^{a(b-n)}b^{2b}\cdot 2^{n+1}b.\] In [Er79] Erdős asks if the infinite families found by Ko are the only solutions.
OPEN
We say that $A\subset \mathbb{N}$ has the translation property if, for every $n$, there exists some integer $t_n\geq 1$ such that \[A\cap [1,n]=(A-t_n)\cap [1,n].\]
  • Does the set of the sums of two squares have the translation property?
  • If we partition all primes into $P\sqcup Q$, such that each set contains $\gg x/\log x$ many primes $\leq x$ for all large $x$, then can the set of integers only divisible by primes from $P$ have the translation property?
  • If $A$ is the set of squarefree numbers then how fast does the minimal such $t_n$ grow? Is it true that $t_n>\exp(n^c)$ for some constant $c>0$?
Elementary sieve theory implies that the set of squarefree numbers has the translation property.

More generally, Brun's sieve can be used to prove that if $B\subseteq \mathbb{N}$ is a set of pairwise coprime integers with $\sum_{b<x}\frac{1}{b}=o(\log\log x)$ then $A=\{ n: b\nmid n\textrm{ for all }b\in A\}$ has the translation property. Erdős did not know what happens if the condition on $\sum_{b<x}\frac{1}{b}$ is weakened or dropped altogether.

OPEN
Is every sufficiently large integer of the form \[ap^2+b\] for some prime $p$ and integer $a\geq 1$ and $0\leq b<p$?
The sieve of Eratosthenes implies that almost all integers are of this form, and the Brun-Selberg sieve implies the number of exceptions in $[1,x]$ is $\ll x/(\log x)^c$ for some constant $c>0$. Erdős [Er79] believed it is 'rather unlikely' that all large integers are of this form.

What if the condition that $p$ is prime is omitted? Selfridge and Wagstaff made a 'preliminary computer search' and suggested that there are infinitely many $n$ not of this form even without the condition that $p$ is prime. It should be true that the number of exceptions in $[1,x]$ is $<x^c$ for some constant $c<1$.

Most generally, given some infinite set $A\subseteq \mathbb{N}$ and function $f:A\to \mathbb{N}$ one can ask for sufficient conditions on $A$ and $f$ that guarantee every large number (or almost all numbers) can be written as \[am^2+b\] for some $m\in A$ and $a\geq 1$ and $0\leq b<f(m)$.

In another direction, one can ask what is the minimal $c_n$ such that $n$ can be written as $n=ap^2+b$ with $0\leq b<c_np$ for some $p\leq \sqrt{n}$. This problem asks whether $c_n\leq 1$ eventually, but in [Er79d] Erdős suggests that in fact $\limsup c_n=\infty$. Is it true that $c_n<n^{o(1)}$?

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].

SOLVED
Let $M(n,k)=[n+1,\ldots,n+k]$ be the least common multiple of $\{n+1,\ldots,n+k\}$.

Let $k\geq 3$. Are there infinitely many $m,n$ with $m\geq n+k$ such that \[M(n,k)>M(m,k+1)?\]

The referee of [Er79] found $M(96,7)>M(104,8)$ and $M(132,7)>M(139,8)$.

The answer is yes, as proved in a strong form by Cambie [Ca24].

It is easy to see that there are infinitely many solutions to $M(n,k)>M(m,k)$. If $n_k$ is the smallest $n$ with this property (for some $m$) then are there good bounds for $n_k$? Erdős writes that he could prove $n_k/k\to \infty$, but knew of no good upper bounds.

Erdős also asked the following: If $u_k$ is minimal such that $M(u_k,k)>M(u_k+1,k)$ and $t<\min(u_k,T)$ then is it true that $M(t,k)\leq M(T,k)$? Stijn Cambie and Wouter van Doorn have observed that there are many counterexamples to this with $t=u_k-1$ and $T=u_k+1$. For example, when $k=7$ we have $u_k=7$, yet $M(6,7)=M(7,7)>M(8,7)$.

See also [677].

Additional thanks to: Stijn Cambie and Wouter van Doorn