Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
If \(A\subseteq\{1, ..., N\}\) with \(|A| = n\) is such that the subset sums \(\sum_{a\in S}a\) are distinct for all \(S\subseteq A\) then \[ N \gg 2 ^ n. \] This conjecture is false. A machine-checked disproof constructs sum-distinct sets…
Can the smallest modulus of a covering system be arbitrarily large? This problem has a negative answer: there is a universal bound on the least modulus of any distinct covering system.
If \(A \subset \mathbb{N}\) has \(\sum_{n \in A}\frac 1 n = \infty\), then must \(A\) contain arbitrarily long arithmetic progressions? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.
Is it true that, for any \(C > 0\), there infinitely many \(n\) such that: \[ p_{n + 1} - p_n > C \frac{\log\log n\log\log\log\log n}{(\log\log\log n) ^ 2}\log n \]
Let \(C\geq 0\). Is there an infinite sequence of \(n_i\) such that \[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\] We formalise "an infinite sequence of \(n_i\)" as a strictly monotone sequence of indices n : ℕ → ℕ. Note that…
There are infinitely many \(n\) such that \(d_n < d_{n+1} < d_{n+2}\), where \(d\) denotes the prime gap function.
Is there a covering system all of whose moduli are odd (and greater than 1)?
Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?
Is there some \(k\) such that every large integer is the sum of a prime and at most \(k\) powers of \(2\)?
Is every large odd integer \(n\) the sum of a squarefree number and a power of 2?
Let \(A\) be an infinite set such that there are no distinct \(a,b,c \in A\) such that \(a \mid (b+c)\) and \(b,c > a\). Is there such an \(A\) with \(\liminf \frac{|A \cap \{1, \dotsc, N\}|}{N^{1/2}} > 0\) ? The DeepMind prover agent has…
If \(A \subseteq \{1, ..., N\}\) is a set with no \(a, b, c \in A\) such that \(a | (b+c)\) and \(a < \min(b,c)\), then \(|A| \le N/3 + O(1)\). This has been solved by Bedert [Be23]. [Be23] Bedert, B., _On a problem of Erdős and Sárközy…
Let \(A ⊆ \mathbb{N}\). Let \(B ⊆ \mathbb{N}\) be the set of integers which are representable in exactly one way as the sum of two elements from \(A\). Is it true that for all \(\epsilon > 0\) and large \(N\),…
Is it true that \(\sum_{n=1}^\infty(-1)^n\frac{n}{p_n}\) converges, where \(p_n\) is the sequence of primes? Note: In the problem statement, \(p_n\) is the \(n\)-th prime, indexed such that \(p_1=2, p_2=3, \ldots\). We 0-index here to…
Is the set of odd integers not of the form \(2^k+p\) the union of an infinite arithmetic progression and a set of density \(0\)? Erdős called this conjecture "rather silly". Chen [Ch23] has proved the answer is no. This was formalized in…
cluster primes
**Erdős Problem 17.** Are there infinitely many cluster primes?
practical numbers
**Conjecture 1.** Are there infinitely many practical numbers \(m\) such that \(h(m) < (\log \log m)^{O(1)}\)? More precisely: does there exist a constant \(C > 0\) such that for infinitely many practical numbers \(m\), we have…
Let \(n_1 < n_2 < \dots\) be an arbitrary sequence of integers, each with an associated residue class \(a_i \pmod{n_i}\). Let \(A\) be the set of integers \(n\) such that for every \(i\) either \(n < n_i\) or…
Let \(A\subset\mathbb{N}\) be infinite such that \(\sum_{a \in A} \frac{1}{a} = \infty\). Must there exist some \(k\geq 1\) such that almost all integers have a divisor of the form \(a+k\) for some \(a\in A\)? This was formalized in Lean…
If \(A ⊆ \mathbb{N}\) is such that \(A + A\) contains all but finitely many integers then \(\limsup 1_A ∗ 1_A(n) = \infty\).
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…
Is it true that, for every \(\varepsilon > 0\), \(h(N) = \sqrt N + O_{\varepsilon}(N^\varepsilon)\)
Given any infinite set \(A\subset \mathbb{N}\) there is a set \(B\) of density \(0\) such that \(A+B\) contains all except finitely many integers. Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].
Does there exist a set \(A \subseteq \mathbb{N}\) such that \(|A \cap \{1, \ldots, N\}| = o((\log N)^2)\) and every sufficiently large integer can be written as \(p + a\) for some prime \(p\) and \(a \in A\)?
Let A ⊆ ℕ be a set such that every integer can be written as n^2 + a for some a in A and n ≥ 0. -/ -- Formalisation note: Changed 'every large integer' to 'every integer' as for the statement these -- conditions are equivalent. Also, this…
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\)?…
Let \(B\subseteq\mathbb{N}\) be an additive basis of order \(k\) with \(0\in B\). Is it true that for every \(A\subseteq\mathbb{N}\) we have \[d_s(A+B)\geq \alpha+\frac{\alpha(1-\alpha)}{k},\] where \(\alpha=d_s(A)\) and \[d_s(A) = \inf…
minimum overlap problem
Find the value of the limit of MinOverlapQuotient!
Does there exist \(B \subset \mathbb{N}\) which is not an additive basis, but is such that for every set \(A \subseteq \mathbb{N}\) of Schnirelmann density \(\alpha\) and every \(N\) there exists \(b \in B\) such that \[ \lvert (A \cup…
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 \(\varepsilon > 0\)?
For what functions \(g(N) → \infty\) is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}\] implies \(\limsup 1_A\ast 1_A(n)=\infty\)?
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_{N \to \infty} \frac{\lvert A \cap…
**Erdős Problem 42**: Let M ≥ 1 and N be sufficiently large in terms of M. Is it true that for every maximal Sidon set A ⊆ {1,…,N} there is another Sidon set B ⊆ {1,…,N} of size M such that (A - A) ∩ (B - B) = {0}? This was proved for all…
If \(A\) and \(B\) are Sidon sets in \(\{1,\ldots,N\}\) with \((A-A)\cap(B-B)=\{0\}\), is it true that \[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?\] The answer is no; the Erdős Problems page notes that…
**Erdős Problem 44:** Let N ≥ 1 and A ⊆ {1,…,N} be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and B ⊆ {N+1,…,M} such that A ∪ B ⊆ {1,…,M} is a Sidon set of size at least (1−ε)M^{1/2}? This problem asks whether any…
Let \(k\geq 2\). Is there an integer \(n_k\) such that, if \(D=\{ 1<d<n_k : d\mid n_k\}\), then for any \(k\)-colouring of \(D\) there is a monochromatic subset \(D'\subseteq D\) such that \(\sum_{d\in D'}\frac{1}{d}=1\)? This follows from…
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] - indeed, there are infinitely many disjoint such…
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…
Are there infinitely many integers \(n, m\) such that \(ϕ(n) = σ(m)\)?
Let \(A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}\) be such that \(\phi(a_1)<\cdots<\phi(a_t)\). The primes are such an example. Are they the largest possible? Can one show that \(\lvert A\rvert<(1+o(1))\pi(N)\) or even…
Schoenberg [Sch38] proved that the asymptotic distribution function of \(\varphi(n)/n\) exists. That is, for any \(c \in [0, 1]\), the proportion of integers \(n \le N\) satisfying \(\varphi(n)/n < c\) approaches a limit as…
Is there an infinite set \(A \subset \mathbb{N}\) such that for every \(a \in A\), there is an integer n such that \(\phi(n)=a\), and yet if \(n_a\) is the smallest such integer, then \(\frac{n_a}{a} → \infty\) as \(a → ∞\)?
sum-product problem
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}?\)
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…
Suppose \(A \subseteq \{1,\dots,N\}\) is such that there are no \(k+1\) elements of \(A\) which are relatively prime. An example is the set of all multiples of the first \(k\) primes. Is this the largest such set? To avoid trivial…
Is there and \(A \subset \mathbb{N}\) is such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is \(\ne 0\)?
Is \[\sum_{n=2}^\infty \frac{1}{n!-1}\] irrational?
Let \(F_{k}(N)\) be the size of the largest \(A\subseteq \{1,\ldots,N\}\) such that the product of no \(k\) many distinct elements of \(A\) is a square. Is \(F_5(N)=(1-o(1))N\)? Conjectured by Erdős, Sós, and Sárközy [ESS95], who proved…
Let \(a, b, c\) be three integers which are pairwise coprime. Is every large integer the sum of distinct integers of the form \(a^k b^l c^m\) (\(k, l, m ≥ 0\)), none of which divide any other? Equivalently: is the set…
Let \(3 \le d_1 < d_2 < \dots < d_r\) be integers such that \[\sum_{1 \le i \le r}\frac 1{d_i - 1} \ge 1.\] Can all sufficiently large integers be written as a sum of the shape \(\sum_i c_ia_i\) where \(c_i \in \{0, 1\}\) and \(a_i\) has…
Let \(A\) be the set of integers which have only the digits \(0, 1\) when written base 3, -/ local notation "A" => { x : ℕ | (digits 3 x).toFinset ⊆ {0, 1} } /-- and \(B\) be the set of integers which have only the digits \(0, 1\) when…
Let \(f(n)\) be maximal such that if \(A\subseteq\mathbb{N}\) has \(|A| = n\) then \(\prod_{a\neq b\in A}(a + b)\) has at least \(f(n)\) distinct prime factors. Is it true that \(\frac{f(n)}{\log n} \to\infty\)? The answer is yes, and a…
Let \(F(N)\) be the maximal size of \(A \subseteq \{1, \dots, N\}\) such that no \(a \in A\) divides the sum of any distinct elements of \(A \setminus \{a\}\). Is it true that \(F(N) > N^{1/2 - o(1)}\)? The answer is no, by the bound of…
We say that \(N\) is powerful if whenever \(p\mid N\) we also have \(p^2\mid N\). Let \(k\geq 3\). Can the product of any \(k\) consecutive positive integers ever be powerful?
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?
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)\).
A set \(A\subset \mathbb{N}\) is primitive if no member of \(A\) divides another. Is the sum \[\sum_{n\in A}\frac{1}{n\log n}\] maximised over all primitive sets when \(A\) is the set of primes? Erdős [Er35] proved that this sum always…
Show that, for any \(n\geq 5\), the binomial coefficient \(\binom{2n}{n}\) is not squarefree.
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.) Barreto and Leeham,…
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…
Let \(s_1 < s_2 < \dots\) 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\)?
Green-Tao theorem
Are there arbitrarily long arithmetic progressions of primes? Solution: yes. Ref: Green, Ben and Tao, Terence, _The primes contain arbitrarily long arithmetic progressions_
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)}?\] A problem of Erdős [Er40, Er73, ErGr80], which is…
Is there a set \(A\subset\mathbb{N}\) such that, for all large \(N\), \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N\] and such that every large integer can be written as \(2^k+a\) for some \(k\geq 0\) and \(a\in A\)? Lorentz [Lo54]…
A conjecture by Heath-Brown: The sum of squares of the first \(N\) gaps between consecutive primes behaves like \(N * (log N)^2\).
Is it true that for all c ≥ 0, the density f c of integers for which (p (n + 1) - p n) / log n < c exists and is a continuous function of c?
Let \(N_k=2\cdot 3\cdots p_k\) and \(\{a_1<a_2<\cdots <a_{\phi(N_k)}\}\) be the integers \(<N_k\) which are relatively prime to \(N_k\). Then, for any \(c\geq 0\), the limit \[\frac{\#\{ a_i-a_{i-1}\leq c \frac{N_k}{\phi(N_k)} : 2\leq…
Let \(f(n)\) count the number of solutions to \(n=p+2^k\) for prime \(p\) and \(k\geq 0\). Show that \(f(n)=o(\log n)\).
Let \(A\subseteq \mathbb{N}\) be a set such that \(\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N\) for all large \(N\). Let \(f(n)\) count the number of solutions to \(n=p+a\) for \(p\) prime and \(a\in A\). Is it true that…
Let c₁, c₂ > 0. Is it true that for any sufficiently large x, there exists more than c₁ * log x many consecutive primes ≤ x such that the difference between any two is > c₂?
Let \(f:\mathbb{N}\to \{-1,1\}\) be a multiplicative function. Is it true that \[ \lim_{N\to \infty}\frac{1}{N}\sum_{n\leq N}f(n)\] always exists? The answer is yes, as proved by Wirsing [Wi67], and generalised by Halász [Ha68].
Erdős-Straus conjecture
For every \(n>2\) there exist distinct integers \(1 ≤ x < y < z\) such that \(\frac 4 n = \frac 1 x + \frac 1 y + \frac 1 z\).
Let \(a_1 < a_2 < \dots\) 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 \ge 1\), \(a_n = a_{n-1}^2 - a_{n-1} + 1\).
Let \(C > 1\). Does the set of integers of the form \(p + \lfloor C^k \rfloor\), for some prime \(p\) and \(k\geq 0\), have density \(>0\)?
Let \((a,b)=1\). The set \(\{a^kb^l: k,l\geq 0\}\) is complete - that is, every large integer is the sum of distinct integers of the form \(a^kb^l\) with \(k,l\geq 0\). We state the nontrivial case \(a,b\geq 2\), proved by Birch [Bi59].
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?
Are there infinitely many \(n\) such that \(\omega(n + k) \ll k\) for all \(k \geq 1\)? Here \(\omega(n)\) is the number of distinct prime divisors of \(n\).
Is \[\sum_{n} \frac{\phi(n)}{2^n}\] irrational? Here \(\phi\) is the Euler totient function.
Is \[ \sum_{n=1}^\infty \frac{\sigma(n)}{2^n} \] irrational? Here \(\sigma(n)\) is the sum of divisors function. The answer is yes, as shown by Nesterenko [Ne96]. [Ne96] Nesterenko, Yu V., _Modular functions and transcendence questions_,…
Is \(\sum_{n=1}^\infty \frac{p_n}{2^n}\) irrational? Here \(p_n\) is the \(n\)-th prime (\(p_1=2, p_2=3, \dots\)).
Erdős Problem 252: irrationality of the sum for a given \(k\).
Let \(a_1 < a_2 < \dotsc\) be an infinite sequence of positive integers such that \(\frac{a_{i+1}}{a_i} \to 1\). If every arithmetic progression contains infinitely many integers which are the sum of distinct \(a_i\) then every…
Let \(A\subseteq \mathbb{N}\) be such that \(\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert \to \infty\textrm{ as }x\to \infty\) and \(\sum_{n\in A} \{ \theta n\}=\infty\) for every \(\theta\in (0,1)\), where \(\{x\}\) is the distance…
Are there infinitely many positive integers \(n\) such that there exist some \(t \ge 2\) and distinct integers \(a_1, \ldots, a_t \ge 1\) satisfying \[\frac{n}{2^n} = \sum_{1 \le k \le t} \frac{a_k}{2^{a_k}}?\] In [Er88c], Erdős notes that…
Let X be the set of points in Fin d → ℝ of the shape fun i : Fin d => ∑' n : A, (1 : ℝ) / (n + i) for some infinite subset A ⊆ ℕ such that 1 / n is summable over A. X has nonempty interior. This is proved in [KoTa24]. -
Is there a covering system all of whose moduli are of the form \(p-1\) for some primes \(p \geq 5\)?
If a finite system of \(r\) congruences \(\{ a_i\pmod{n_i} : 1\leq i\leq r\}\) (the \(n_i\) are not necessarily distinct) covers \(2^r\) consecutive integers then it covers all integers. This is best possible as the system…
Is there an infinite Lucas sequence \(a_0, a_1, \ldots\) where \(a_{n+2} = a_{n+1} + a_n\) for \(n \ge 0\) such that all \(a_k\) are composite, and yet no integer has a common factor with every term of the sequence?
Is it true that, for every \(c\), there exists an \(n\) such that \(\sigma(n)>cn\) but there is no covering system whose moduli all divide \(n\)? This was answered affirmatively by Haight [Ha79].
Let \(k\geq 3\). Is there a choice of congruence classes \(a_p\pmod{p}\) for every prime \(p\) such that all sufficiently large integers can be written as \(a_p+tp\) for some prime \(p\) and integer \(t\geq k\)?
Let \(n_1<n_2<\cdots \) be an infinite sequence of integers with associated \(a_k\pmod{n_k}\), 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…
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…
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\) not used so far such that \(n\geq 1/x\) and repeat with \(x\) replaced by…
Let \(p\colon \mathbb{Z} \rightarrow \mathbb{Z}\) be a polynomial (with rational coefficients, taking integer values at all integers) whose leading coefficient is positive and such that there exists no \(d≥2\) with \(d ∣ p(n)\) for all…
Let \(f(k)\) be the minimal value of \(n_k\) such that there exist \(n_1 < n_2 < \dots < 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 ? \] Proved by Martin [Ma00].…
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].
Let \(k\geq2\). Is it true that, for any distinct integers \(1 < n_1 < \cdots < n_k\) such that \(\sum_{i=1}^k \frac{1}{n_i} = 1\), we must have \(\max(n_{i+1} - n_i) \geq 3\)?
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}? \]
Is it true that, for all sufficiently large \(k\), there exist finite intervals \(I_1, \dotsc, I_k \subset \mathbb{N}\), distinct, not overlapping or adjacent, with \(|I_i| \geq 2\) for \(1 \leq i \leq k\) such that \[ 1 = \sum_{i=1}^k…
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…
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\) occurs for infinitely many \(n\)?
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…
ambiguous statement
Let \(k(N)\) denote the smallest \(k\) such that there exists \(N ≤ n_1 < ⋯ < n_k\) with \(\frac 1 {n_1} + ... + \frac 1 {n_k} = 1\) Is it true that \(\lim_{N \to \infty} k(N) - (e - 1)N = \infty\)?
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)\)? Hunter…
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] (even if 'positive density' is interpreted as…
Is there an infinite sequence \(a_1 < a_2 < \dots\) 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…
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 [ErGr80] believe the answer is \(A(N)=(1+o(1))N\).…
Let \(f(N)\) be the size of the largest \(A\subseteq \{1,\ldots,N\}\) such that there are no solutions to \[\frac{1}{a}= \frac{1}{b}+\frac{1}{c}\] with distinct \(a,b,c\in A\)? Estimate \(f(N)\). The colouring version of this is [303],…
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\)? This is true, as proved by Brown and Rödl [BrRo91]. This was formalized in…
Is it true that \[N(b) \ll \log \log b\]? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
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…
Let \(\frac a b\in \mathbb{Q}_{>0}\) with \(b\) squarefree. Are there integers \(1 < n_1 < \dots < n_k\), each the product of two distinct primes, such that \(\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\)?
Are there two finite set of primes \(P\) and \(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]. [Ba76] Barbeau, E. J., _Computer challenge corner:…
Let \(N\geq 1\). What is the smallest integer not representable as the sum of distinct unit fractions with denominators from \(\{1,\ldots,N\}\)? This was essentially solved by Croot [Cr99] (see erdos_308.variants.croot); in particular, for…
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? If the number of such integers is \(N(n)\) then it is trivial that…
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…
Let \(\delta(N)\) be the minimal non-zero value of \(\lvert 1-\sum_{n\in A}\frac{1}{n}\rvert\) as \(A\) ranges over all subsets of \(\{1,\ldots,N\}\). Is it true that \[\delta(N)=e^{-(c+o(1))N}\] for some constant \(c\in (0,1)\)? The…
Does there exist a constant c > 0 such that, for any K > 1, whenever A is a sufficiently large finite multiset of integers with \(\sum_{n \in A} 1/n > K\) there exists some \(S \subseteq A\) such that…
Are there infinitely many pairs (m, P) where m ≥ 2 is an integer and P is a set of distinct primes such that the following equation holds: \(\sum_{p \in P} \frac{1}{p} = 1 - \frac{1}{m}\)?
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?\]…
Let \(u_1=1\) and \(u_{n+1}=u_n(u_n+1)\), so that \(\sum_{k\geq 1}\frac{1}{u_k+1}\) and \(u_k=\lfloor c_0^{2^k}+1\rfloor\) for \(k\geq 1\), where \[c_0=\lim u_n^{1/2^n}=1.264085\cdots.\] Let \(a_1<a_2<\cdots \) be any other sequence with…
Is it true that if \(A \subseteq \mathbb{N}\setminus\{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…
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}?\]
There exists a set A with positive density that does not have property P₁. #TODO: prove this lemma by assuming erdos_318.contain_single_even. The density sits in an existential, so HasPosDensity is the *stronger* reading here and weakening…
What is the size of the largest \(A\subseteq\{1, \dots, 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…
Let \(R(N)\) be the size of the largest \(A\subseteq\{1, ..., N\}\) such that all sums \(\sum_{n\in S} \frac{1}{n}\) are distinct for \(S\subseteq A\). What is \(R(N)\)?
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\)…
Is it true that \(f_{k,k}(x) \gg_\epsilon x^{1-\epsilon}\) for all \(\epsilon>0\)? This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'.
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?
Writing \(f_{k, 3}(x)\) for the number of integers \(\leq x\) which are the sum of three \(k\)th powers, is it true that \(f_{k, 3}(x) \gg x ^ (3 / k)\)?
Does there exist \(A = \{a_1 < a_2 < \cdots\} \subset \mathbb{N}\) which is a minimal basis of order \(2\) (i.e. every large integer is the sum of \(2\) elements from \(A\), and no proper subset of \(A\) has this property), such that…
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…
**Erdős Problem 329.** Let A ⊆ ℕ be a Sidon set. How large can lim sup_{N → ∞} |A ∩ {1,…,N}| / N^{1/2} be?
Does there exist a minimal basis \(A \subset \mathbb{N}\) with positive density such that, for any \(n \in A\), the (upper) density of integers which cannot be represented without using \(n\) is positive? Neither set is asked to have a…
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…
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? The sufficient…
Let \(A\subseteq \mathbb{N}\) be a set of density zero. Does there exist a \(B\) such that \(A\subseteq B+B\) and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large \(N\)? The answer is no. Erdős and Newman [ErNe77] have…
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…
The restricted order of a basis \(A\) 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? A…
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 (i.e. there are no non-trivial solutions…
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…
Do infinitely many pairs \((a, a+2)\) occur in Ulam's sequence?
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\}\]…
Is it true that for every lacunary, strongly complete sequence A that is not complete whenever infinitely many terms are removed from it, lim A (n + 1) / A n = (1 + √5) / 2? The answer is no. A counterexample recorded at…
The set of subset sums of a set A ⊆ ℕ. -/ local notation "𝓟" A => subsetSums A /-- 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…
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 1. \(A\) remains complete after removing any \(m\) elements, but 2. \(A\) is not complete after removing any \(n\)…
For what values of \(t,\alpha \in (0,\infty)\) is the sequence \(\lfloor t\alpha^n\rfloor\) complete (that is, all sufficiently large integers are the sum of distinct integers of the form \(\lfloor t\alpha^n\rfloor\))?
If A ⊂ ℕ is a finite set of integers all of whose subset sums are distinct then ∑ n ∈ A, 1/n < 2. Proved by Ryavec. This was proved by Ryavec, who did not appear to ever publish the proof. Ryavec's proof is reproduced in [BeEr74]. More…
Let \(p(x) \in \mathbb{Q}[x]\) be a non-constant rational polynomial with positive leading coefficient. 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\),…
Let \(\alpha,\beta\in \mathbb{R}_{>0}\) such that \(\alpha/\beta\) is irrational. Is the multiset \[\{ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots\}\cup \{ \lfloor \beta\rfloor,\lfloor 2\beta\rfloor,\lfloor…
Is there a lacunary sequence \(A\subseteq \mathbb{N}\) (so that \(A=\{a_1 < \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} :…
Let \(f(n)\) be the maximal \(k\) such that there exist integers \(1 \le a_1 < \dotsc < a_k \le n\) such that all sums of the shape \(\sum_{u \le i \le v} a_i\) are distinct. Is \(f(n)=o(n)\)?
Let \(A=\{a_1 < \cdots\}\) be an infinite sequence of integers. Let \(f(n)\) count the number of solutions to \[n=\sum_{u\leq i\leq v}a_i.\] Is there such an \(A\) for which \(f(n)\to \infty\) as \(n\to \infty\)? Tao [Ta26] constructed…
segmented numbers
Let \(a_1< a_2 < ⋯ \) be an infinite sequence of integers such that \(a_1=1\) and \(a_{i+1}\) is the least integer which is not a sum of consecutive earlier \(a_j\)s. Show that \(a_k / k \to \infty\).
Let \(c > 0\) and \(n\) be some large integer. What is the size of the largest set \(A \subseteq \{1, \ldots, \lfloor c n \rfloor\}\) such that \(n\) is not a sum of a subset of \(A\)? Does this depend on \(n\) in an irregular way?
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\)? Erdős and Moser [Er65] proved the first bound…
Is it true that, for each fixed \(n\) and fixed sizes \(k_1,\ldots,k_n \geq 4\), there are only finitely many collections of disjoint intervals \(I_1,\ldots,I_n\) of size \(\lvert I_i\rvert = k_i\) for \(1\leq i\leq n\) such…
There is no consecutive triple of powerful numbers.
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? The answer to the first question is no: Golomb [Go70] observed that both…
ambiguous statement
Are there any \(2\)-full \(n\) such that \(n+1\) is \(3\)-full?
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\),…
How large is the largest prime factor of \(n(n+1)\)? The truth is probably \(F(n)\gg (\log n)^2\) for all \(n\).
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? The problem is trivially true as written…
Are there infinitely many \(n\) such that the largest prime factor of \(n\) is \(< n^{\frac{1}{2}}\) and the largest prime factor of \(n + 1\) is \(< (n + 1)^{\frac{1}{2}}\). Steinerberger has pointed out this problem has a trivial…
Let \(P(n)\) denote the largest prime factor of \(n\). Show that the set of \(n\) with \(P(n+1) > P(n)\) has density \(\frac{1}{2}\). This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
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)\).
Show that the equation n!=a_1!a_2!···a_k!, with n−1 > a_1 ≥ a_2 ≥ ··· ≥ a_k, has only finitely many solutions.
Is Erdos375Prop true?
Are there infinitely many \(n\) such that \({2n\choose n}\) is coprime to \(105\)?
Is there some absolute constant \(C > 0\) such that \[ \sum_{p \leq n} 1_{p\nmid {2n \choose n}}\frac{1}{p} \leq C \] for all \(n\)?
Let \(S(n)\) denote the largest integer such that, for all \(1 ≤ k < n\), the binomial coefficient \(\binom{n}{k}\) is divisible by \(p^S(n)\) for some prime \(p\) (depending on \(k\)).Then \(\limsup S(n) = \infty\). This was formalized in…
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)}\)? We read this as: for every \(\epsilon > 0\), every such pair with \(v\)…
Is it true that for every \(k\) there are infinitely many primes \(p\) such that the largest prime divisor of \[ \prod_{i = 0}^k (p ^ 2 + i) \] is \(p\)?
If \(1<k<n-1\) then \(\binom{n}{k}\) is divisible by a prime \(p\leq n/2\) (except \(\binom{7}{3}=\binom{7}{4}=5\cdot 7\)). A conjecture of Erdős and Selfridge [ErGr80]. Proved by Ecklund [Ec69], who made the stronger conjecture that…
Let \(F(n) := \max\{m + p(m) \mid \textrm{\)m < n\( composite}\}\}\) where \(p(m)\) is the least prime divisor of \(m\). Is it true that \(F(n)>n\) for all sufficiently large \(n\)?
Let \(2 \le k \le n - 2\). Can \(\binom{n}{k}\) be the product of consecutive primes infinitely often? Here \(k\) may vary with \(n\): the question asks for infinitely many admissible binomial coefficients, not for a single \(k\) that…
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]\)? Bui, Naprienko, Pratt, and Zaharescu [BNPZ26] answered this negatively.
Are there only finitely many solutions of \[\prod_{1\leq i\leq k_1}(m_1+i)=\prod_{1\leq j\leq k_2}(m_2+j)\] with \(k_1,k_2>3\) and \(m_1+k_1\leq m_2\)? Here \(m_1, m_2 \geq 0\), so every factor is positive and the condition…
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)? \]
Does there exists a constant c such that f n - 2 * n ~ c * (n / log n)?
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}?\] It is easy to…
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\). Then \[ A(n) = \frac{n}{2} - \frac{n}{2\log n} + o\left(\frac{n}{\log n}\right). \]
Let \(f(n)\) denote the minimal \(m\geq 1\) such that \[n! = a_1\cdots a_t\] with \(a_1<\cdots <a_t=a_1+m\). What is the behaviour of \(f(n)\)? We formalise the question as: does \(f(n) \to \infty\)? A result of Luca [Lu02] implies a…
Is it true that \(\sum_{n\leq x}t_2(n)\ll \frac{x^2}{(\log x)^c}\) for some \(c>0\)?
Is it true that for every \(k\) there exists \(n\) such that \[\prod_{0\leq i\leq k}(n-i) \mid \binom{2n}{n}?\]
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? Somani, using ChatGPT, has given a negative answer. In fact, for any \(a\geq 2\), if \(c=8a^2+8a+1\),…
Brocard-Ramanujan conjecture
**Brocard's Problem** Does \(n! + 1 = m^2\) have integer solutions other than \(n = 4, 5, 7\)?
Is it true that there are no solutions to n! = x^k ± y^k with x,y,n ∈ ℕ, x*y > 1, and k > 2? The answer is no: Jonas Barfield found the counterexample 10! = 48^4 - 36^4 (equivalently, 10! + 36^4 = 48^4). This is discussed in problem D2 of…
Can one show that \(\sum_{n\leq x}g_k(n) \sim c_k x\log x\) for some constant \(c_k\)?
Is there some function \(f(r)\) such that \(f(r)\to \infty\) as \(r\to\infty\), such that, for infinitely many \(n\), there exist \(a_1,a_2\) with \[a_1+a_2> n+f(r)\log n\] such that \(a_1!a_2! \mid n!2^n3^n\cdots p_r^n\)? It is ambiguous…
Prove that, for any finite set \(A\subset\mathbb{N}\), there exist \(a, b\in A\) such that \[ \gcd(a, b)\leq a/|A|. \]
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…
Let \(p\) be an odd prime. Is it true that the equation \((p-1)!+a^{p-1}=p^k\) has only finitely many solutions? Originally proposed by Erdős and Graham [ErGr80]. Brindza and Erdős [BrEr91] proved that there are finitely many such…
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\)?
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…
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…
Let \(c(n)\) be the minimum number of iterations of \(n\mapsto\phi(n) + 1\) before a prime is reached. What is \(\Theta(c(n))\)?
Let \(σ_1(n) = σ(n)\), the sum of divisors function, and \(σ_k(n) = σ(σ_{k-1}(n))\). Is it true that \(\lim_{k → ∞} σ_k(n)^{\frac 1 k} = ∞\)? This is problem (iii) from Erdos, Granville, Pomerance, Spiro "On the normal behavior of the…
partial r=2 result
Let \(σ_1(n)=σ(n)\), the sum of divisors function, and \(σ_k(n) = σ(σ_{k-1}(n))\). Is it true that, for every \(m, n ≥ 2\), there exist some \(i, j\) such that \(σ_i(m) = σ_j(n)\)?
Are there infinitely many barriers for ω?
Let \(h_1(n) = h(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)\)?
Let V(x) count the number of n≤x such that ϕ(m)=n is solvable. Does V(2x)/V(x)→2 ? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof, which gives V(cx)/V(x)→c for every fixed c>0.
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?
Are there infinitely many integers not of the form \(n - \phi(n)\)? Asked by Erdős and Sierpiński. Numbers not of the form we call non-cototients. Browkin and Schinzel [BrSc95] provided an affirmative answer to this question, proving that…
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!)}? \] The limit points are exactly \(\{1\} \cup \{1+1/k : k \geq 1\}\).
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\)? "For large \(C\)" means for all…
There exists a sequence \(1 \le d_1 < d_2 < \dots\) with density 1 such that all products \(\prod_{u \le i \le v} d_i\) are distinct. This was solved affirmatively; see [Pratt26].
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?
Erdős Problem 423 [Er77c, p.71; ErGr80, p.83]: Let \(a(1) = 1\), \(a(2) = 2\), and for \(k \ge 3\) let \(a(k)\) be the least integer greater than \(a(k-1)\) that is a sum of at least two consecutive terms of the sequence. What is the…
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_i a_j - 1\) with \(i \neq j\). Is it true that the set of integers which eventually appear has positive density? As…
**Erdős Problem 427**: 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?
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?\]
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\in \mathbb{Z}\) such that \(n+a\) is prime for all \(a\in A\)? Weisenberg…
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…
inverse Goldbach problem
Are there two infinite sets \(A\) and \(B\) such that \(A+B\) agrees with the primes up to finitely many exceptions? This was disproved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
For every fixed \(k \geq 2\), Erdős and Graham conjectured that \[g(k,n) \sim \frac{n^2}{k-1}.\] The conjecture was proved by Dixmier [Di90].
Let \(k \le n\). What choice of \(A\subseteq\{1, \dots, n\}\) (with \(\text{gcd}(A) = 1\)) of size \(|A| = k\) maximises the number of integers not representable as the sum of finitely many elements from \(A\) (with repetitions allowed)?…
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? If \(n=\prod p_k^{a_k}\) then the largest…
If \(p\) is a prime and \(k, m \geq 2\), 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\), and let \(\Lambda(k, m) = \limsup_{p \to \infty} r(k, m, p)\). Is…
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? The answer is yes, which…
How large can \(A \subseteq \{1, \ldots, N\}\) be if \(A + A\) contains no square numbers? A problem of Erdős [Er80, Er80c, ErGr80]. Taking all integers \(\equiv 1 \pmod 3\) gives \(|A| \ge N/3\), and Massias observed that all integers…
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}\)? The answer is yes: Tao has given a simple proof,…
Let \(N\geq 1\). What is the size of the largest \(A\subset \{1,\ldots,N\}\) such that \([a,b]\leq N\) for all \(a,b\in A\), where \([a,b]\) is the least common multiple of \(a\) and \(b\)? Is it attained by choosing all integers in…
Let \(\operatorname{Log} x := \max\{\log x, 1\}\), \(\operatorname{Log}_2x = \operatorname{Log} (\operatorname{Log} x)\), and \(\operatorname{Log}_3x = \operatorname{Log}(\operatorname{Log}(\operatorname{Log} x)).\) Is it true that if…
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? This was solved independently by Hegyvári [He25] and Cambie (unpublished), who show that if \(m>n\) then the…
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}…
Is it true that, for any \(c>1/2\), if \(p\) is a sufficiently large prime then, for any \(n\geq 0\), there exist \(a,b\in(n,n+p^c)\) such that \(ab\equiv 1\pmod{p}\)? This is discussed in this MathOverflow question [MathOverflow].
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 \cdot \tau(n) \] for almost all…
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\)? The bound is required for every \(x\) and every window length at least \(y\), and…
Determine the largest length of an interval in \([x,2x]\) on which \(\omega(n) > \log\log n\) everywhere.
Is it true that, for all sufficiently large \(n\), there exists some \(i<n\) such that \[ p_n^2 < p_{n+i}p_{n-i}, \] where \(p_k\) is the \(k\)th prime? Pomerance proved that the answer is no.
Is it true that limsup (fun n => (f n - 2 * n.nth Prime : ℕ∞)) atTop = ⊤?
Let q : ℕ → ℕ be a strictly increasing sequence of primes such that q (n + 2) - q (n + 1) ≥ q (n + 1) - q n. Must lim q n / (n ^ 2) = ∞?
Is it true that \(m_n<p_n\) for almost all \(n\)?
Is there some \(\epsilon > 0\) such that there are infinitely many \(n\) where all primes \(p \le (2 + \epsilon) \log n\) divide \[ \prod_{1 \le i \le \log n} (n + i)? \] This was formalized in Lean by Baretto and van Doorn using Aristotle.
Let \(\operatorname{lcm}(1, \dots, n)\) denote the least common multiple of \(\{1, \dots, n\}\). Let \(p_k\) be the \(k\)-th prime. Is it true that for all \(k \geq 1\),…
Let \(f(u)\) be the largest \(v\) such that no \(m\in (u,v)\) is composed entirely of primes dividing \(uv\). Estimate \(f(u)\). The estimate \(u + 2 \le f(u) \le u^2\) holds for every \(u \ge 2\). The upper bound is attained when \(u\) is…
ambiguous statement
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…
Let \(p(n)\) denote the least prime factor of \(n\). Is there a constant \(C>0\) such that \[\sum_{x\leq n\leq x+C\sqrt{x}(\log x)^2}\frac{p(n)}{n}\gg 1\] for all sufficiently large \(x\)?
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\).
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…
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…
ambiguous statement
For every sufficiently large \(x\), choose a congruence class \(a_p\pmod p\) for each prime \(p\leq x\). Can the primes be decomposed into two nonempty sets \(A\) and \(B\) such that every \(n<x\) lies in a chosen class from \(A\) and in a…
Let \(A\) be the set of all \(n\) such that \(n = d_1 + ⋯ + d_k\) with \(d_i\) distinct proper divisors of \(n\), but this is not true for any \(m ∣ n\) with \(m < n\). Does: \[ \sum_{n ∈ A} \frac 1 n \] converge? Yes: the sum converges.…
Are there any odd weird numbers?
Given a finite sequence of primes \(q_1<\cdots<q_m\), extend it by taking \(q_{n+1}\) to be the smallest prime of the form \(q_n+q_i-1\) for \(n\geq m\). Is there an initial sequence for which this process continues forever?
Is there a permutation \(a_1, a_2, \ldots\) of the positive integers such that \(a_k + a_{k+1}\) is always prime? A question of Segal [ErGr80, p.94]. The answer is yes, as shown by Odlyzko. The linked formal proof (Codex and GPT-5.6 Sol)…
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)? \] This is the Erdős-Heilbronn inequality, proved by Dias da Silva and Hamidoune.
Is there a polynomial \(f:\mathbb{Z}\to \mathbb{Z}\) of degree at least \(2\) and a set \(A\subset \mathbb{Z}\) such that for any \(n\in \mathbb{Z}\) there is exactly one \(a\in A\) and \(b\in \{ f(k) : k\in\mathbb{Z}\}\) such that…
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?\]
Is it true that, for every integer \(k\neq 1\), there are infinitely many \(n\) such that \(2^n\equiv k\pmod{n}\)?
Let \(x_1,x_2,\ldots\in [0,1]\) be an infinite sequence. Is it true that \[\inf_n \liminf_{m\to \infty} n \lvert x_{m+n}-x_m\rvert\leq 5^{-1/2}\approx 0.447?\] A conjecture of Newman.
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…
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…
Let \(f(k)\) be the minimal \(N\) such that if \(\{1,\ldots,N\}\) is \(k\)-coloured then there is a monochromatic solution to \(a+b=c\). Estimate \(f(k)\). In particular, is it true that \(f(k) < c^k\) for some constant \(c>0\)? The…
Prove that there exists an absolute constant \(c>0\) such that, whenever \(\{1,\ldots,N\}\) is \(k\)-coloured (and \(N\) is large enough depending on \(k\)) then there are at least \(cN\) many integers in \(\{1,\ldots,N\}\) which are…
Let \(A \subseteq \mathbb{N}\), and for each \(n \in A\) choose some \(X_n \subseteq \mathbb{Z}/n\mathbb{Z}\). Let \(B = \{m \in \mathbb{N} : m \not\in X_n \pmod{n} \text{ for all } n \in A \text{ with } m > n\}\). Must \(B\) have a…
Let \(A\subseteq \mathbb{N}\) have positive density. Must there exist distinct \(a,b,c\in A\) such that \([a,b]=c\) (where \([a,b]\) is the least common multiple of \(a\) and \(b\))? This is true, a consequence of the positive solution to…
Let \(A\) be a finite set and \[B=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}.\] Is it true that, for every \(m>n\geq \max(A)\), \[\frac{\lvert B\cap [1,m]\rvert }{m}< 2\frac{\lvert B\cap [1,n]\rvert}{n}?\]
Let \(A\subseteq \mathbb{N}\) be a set such that \(\lvert A\cap [1,x]\rvert=o(x^{1/2})\). Let \(B=\{ n\geq 1 : a\nmid n\textrm{ for all }a\in A\}\). If \(B=\{b_1 < b_2 < \cdots\}\) then is it true that \[\lim_{x \to \infty}…
Let \(A,B\subseteq \{1,\ldots,N\}\) be such that all the products \(ab\) with \(a\in A\) and \(b\in B\) are distinct. Is it true that \[\lvert A\rvert \lvert B\rvert \ll \frac{N^2}{\log N}?\] This would be best possible, for example…
Let \(f : \mathbb{N} \to \mathbb{R}\) be an additive function (so that \(f(ab) = f(a) + f(b)\) whenever \((a, b) = 1\)). If \(|f(n+1) - f(n)| < c\) for some constant \(c\) and all \(n\), then must there exist some \(c'\) such that…
Does there exist a \(k\) such that every sufficiently large integer can be written in the form \[\prod_{i=1}^k a_i - \sum_{i=1}^k a_i\] for some integers \(a_i\geq 2\)? Erdős attributes this question to Schinzel. Eli Seamans has observed…
Littlewood conjecture
Let \(\alpha,\beta \in \mathbb{R}\). Is it true that\[\liminf_{n\to \infty} n \| n\alpha \| \| n\beta\| =0\]? This is also known as the Littlewood conjecture.
Prime entries are random variables. -/ measurable_of_prime p : p.Prime → Measurable (f p) /-- Prime entries are independent. -/ iIndepFun_primes : iIndepFun (fun p : Primes ↦ f p) ℙ /-- Primes entries are uniformly distributed on {-1, 1}.…
If \(\mathbb{N}\) is 2-coloured then is there some infinite set \(A\subseteq \mathbb{N}\) such that all finite subset sums\[ \sum_{n\in S}n\](as \(S\) ranges over all non-empty finite subsets of \(A\)) are monochromatic? Asked by Graham…
What is the largest possible subset \(A\subseteq\{1,\ldots,N\}\) which contains \(N\) such that \(\mathrm{gcd}(a,b)>1\) for all \(a\neq b\in A\)? Erdős conjectured that if \(N=q_1^{k_1}\cdots q_r^{k_r}\) (where \(q_1<\cdots <q_r\) are…
Let \(r \geq 3\), and let \(f_r(N)\) denote the size of the largest subset of \(\{1,\ldots,N\}\) such that no subset of size \(r\) has the same pairwise greatest common divisor between all elements. Erdős [Er64] proved that…
Let \(\epsilon>0\) and \(N\) be sufficiently large. Is it true that if \(A\subseteq \{1,\ldots,N\}\) has size at least \(\epsilon N\) then there must be distinct \(a,b,c\in A\) such that \[[a, b]=[b, c]=[a, c],\] where \([\cdot, \cdot]\)…
Let \(\epsilon>0\) and \(N\) be sufficiently large. If \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert \geq \epsilon N\) then must there exist \(a_1,a_2,a_3\in A\) and distinct primes \(p_1,p_2,p_3\) such that \[a_1p_1=a_2p_2=a_3p_3?\]…
Let \(r\geq 2\) and suppose that \(A\subseteq\{1,\ldots,N\}\) is such that, for any \(m\), there are at most \(r\) solutions to \(m=pa\) where \(p\) is prime and \(a\in A\). Give the best possible upper bound for…
Let \(h(n)\) be maximal such that, for any set \(A\subseteq \mathbb{N}\) of size \(n\), the set\[\left\{ \frac{a}{(a,b)}: a,b\in A\right\}\]has size at least \(h(n)\). Estimate \(h(n)\).
Is it true that if \(A\subseteq \mathbb{Z}/N\mathbb{Z}\) has size \(\gg N^{1/2}\) then there exists some non-empty \(S\subseteq A\) such that \(\sum_{n\in S}n\equiv 0\pmod{N}\)? Szemerédi proved the answer is yes, in fact for arbitrary…
Let \(a_1, \dots, a_p\) be (not necessarily distinct) residues modulo a prime \(p\), such that there exists some \(r\) so that if \(S \subseteq [p]\) is non-empty and \[\sum_{i \in S} a_i \equiv 0 \pmod{p}\] then \(|S| = r\). Must there be…
Is it true that if \(A\subseteq\{1,\ldots,n\}\) is a set such that \([a,b]>n\) for all \(a\neq b\), where \([a,b]\) is the least common multiple, then \[\sum_{a\in A}\frac{1}{a}\leq \frac{31}{30}?\] The answer is yes, proved by Schinzel…
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](https://www.erdosproblems.com/7)). The answer is no, as proved by Balister, Bollobás,…
If ℕ is \(2\)-coloured then there must exist a monochromatic three-term arithmetic progression \(x,x+d,x+2d\) such that \(d>x\). This was first proved by Brown and Landman [BrLa99], who in fact show that this is always possible with…
Let \(p_1,\ldots,p_k\) be distinct primes. Are there infinitely many \(n\) such that \(n!\) is divisible by an even power of each of the \(p_i\)? The answer is yes, proved by Berend [Be97], who further proved that the sequence of such…
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? \]
Let \(g(n)\) denote the largest \(t\) such that there exist integers \(2\leq a_1<a_2<\cdots <a_t <n\) such that \[P(a_1)>P(a_2)>\cdots >P(a_t)\] where \(P(m)\) is the greatest prime factor of \(m\). Estimate \(g(n)\). Stijn Cambie has…
Let \(P(m)\) denote the greatest prime factor of \(m\). Is it true that, for any two primes \(p,q\), there exists some integer \(n\) such that \(P(n)=p\) and \(P(n+1)=q\)? In fact, the answer to this question as written is easily seen to…
Let \(f(m)\) be such that if \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert=m\) then every interval in \([1,\infty)\) of length \(2N\) contains \(\geq f(m)\) many distinct integers \(b_1,\ldots,b_r\) where each \(b_i\) is divisible by…
Let \(k \geq 2\), and let \(q(n,k)\) denote the least prime which does not divide \(\prod_{1 \leq i \leq k}(n+i)\). Is it true that, if \(k\) is fixed and \(n\) is sufficiently large, then \(q(n,k) < (1+o(1))\log n\)?
Can the product of an arithmetic progression of positive integers \(n, n + d, ..., n + (k - 1)d\) of length \(k ≥ 4\), with \((n, d) = 1\), be a perfect power? Erdős believed not, i.e. that Erdos672With k l holds for all \(k ≥ 4\) and…
Let \(1=d_1<\cdots <d_{\tau(n)}=n\) be the divisors of \(n\) and \[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\] Is it true that \(G(n)\to \infty\) for almost all \(n\)? The answer is yes: Tao observed that…
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\), and…
Is every sufficiently large integer of the form \(ap^2+b\) for some prime \(p\) and integers \(a \geq 1\) and \(0 \leq b < p\)?
Denote by \(M(n, k)\) the least common multiple of the finite set \(\{n+1, \dotsc, n+k\}\). Is it true that for all \(m \geq n + k\), we get \(M(m, k) \neq M(n, k)\)?
Write \(M(n, k)\) be the least common multiple of \(\{n+1, \dotsc, n+k\}\). Let \(k\) be sufficiently large. Are there infinitely many \(m, n\) with \(m \geq n + k\) such that \[ M(n, k) > M(m, k + 1) \]? The answer is yes, as proved in a…
Let \(\epsilon>0\) and \(\omega(n)\) count the number of distinct prime factors of \(n\). Are there infinitely many values of \(n\) such that \[\omega(n-k) < (1+\epsilon)\frac{\log k}{\log\log k}\] for all \(k<n\) which are sufficiently…
Is it true that, for all sufficiently large \(n\), there exists some \(k\) such that \[ p(n+k)>k^2+1, \] where \(p(m)\) denotes the least prime factor of \(m\)?
**Erdős problem 681.** Is it true that for all large \(n\) there exists \(k\) such that \(n + k\) is composite and \(p(n+k) > k^2\), where \(p(m)\) is the least prime factor of \(m\) ?
Is it true that for almost all \(n\) there exists some \(m\in (p_n,p_{n+1})\) such that \[p(m) \geq p_{n+1}-p_n,\] where \(p(m)\) denotes the least prime factor of \(m\)? This was solved in the affirmative by Gafni and Tao [GaTa25]. This…
Let \(P(n, k)\) be the largest prime factor of \(\binom{n}{k}\). There exists \(c > 0\) such that \(P(n, k) \ge \min(n - k + 1, k^{1 + c})\) for all \(0 < k \le n/2\). Erdős stated this for \(1 \le k \le n\) with the bound…
Let \(f(n)\) be the smallest \(0 \leq k \leq n\) for which the factor of \(\binom{n}{k}\) supported on primes at most \(k\) exceeds \(n^2\). Give bounds for \(f(n)\). An internal OpenAI model [APSSV26] has given an elementary argument…
Let \(\epsilon > 0\) and let \(n\) be large depending on \(\epsilon\). Is it true that for all \(n^{\epsilon} < k \leq n^{1-\epsilon}\) the number of distinct prime divisors of \(\binom{n}{k}\) is \[(1+o(1))\, k \sum_{k < p < n}…
Can every integer \(N≥2\) be written as \[N=\frac{\prod_{1\leq i\leq k}(m+i)}{\prod_{1\leq i\leq k}(n+i)}\] for some \(k≥2\) and \(m≥n+k\)?
Let \(Y(x)\) be the maximal \(y\) such that there exists a choice of congruence classes \(a_p\) for all primes \(p\leq x\) such that every integer in \([1,y]\) is congruent to at least one of the \(a_p\pmod{p}\). Give good estimates for…
Estimate \(\epsilon_n\).
Let n be sufficiently large. Is there some choice of congruence class a_p for all primes 2 ≤ p ≤ n such that every integer in [1,n] satisfies at least two of the congruences ≡ a_p (mod p)? Yes: this follows from the greedy-matching…
Let \(d_k(p)\) be the density of those integers whose \(k\)th smallest prime factor is \(p\) (i.e. if \(p_1<p_2<\cdots\) are the primes dividing \(n\) then \(p_k=p\)). For fixed \(k\geq 1\) is \(d_k(p)\) unimodular in \(p\)? That is, it…
Given \(A \subseteq \mathbb{N}\), let \(M_A = \{n \geq 1 : a \mid n \text{ for some } a \in A\}\). Find a necessary and sufficient condition on \(A\) for \(M_A\) to have density \(1\).
Let \(\delta_1(n,m)\) be the density of the set of integers with exactly one divisor in \((n,m)\). Is \(\delta_1(n,m)\) unimodular for \(m>n+1\) (i.e. increases until some \(m\) then decreases thereafter)? Cambie has calculated that…
Let \(f_\max(n)\) be the largest \(m\) such that \(\phi(m) = n\), and \(f_\min(n)\) be the smallest such \(m\), where \(\phi\) is Euler's totient function. Investigate \[ \max_{n\leq x}\frac{f_\max(n)}{f_\min(n)}. \] GPT-5.5 Pro (prompted…
Let \(q_1 < q_2 < \cdots\) be a sequence of primes such that \(q_{i + 1} \equiv 1 \pmod{q_i}\). Is it true that \[ \lim_{k \to \infty} q_k^{1/k} = \infty? \]
Is it true that \(H(n)/h(n)\to \infty\) for almost all \(n\)? Formalised as: for every threshold \(M\), the set of \(n\) with \(h(n) > 0\) and \(H(n)/h(n) > M\) has natural density \(1\). This is false: in fact, \(H(n)/h(n) = 2 + o(1)\)…
For each \(m\) and \(\alpha\), the density of the set of integers which are divisible by some \(d \equiv 1 \pmod{m}\) with \(1 < d < \exp (m ^ \alpha)\) exists.
Is there some \(h(n)\to \infty\) such that for all \(2\leq i<j\leq n/2\) \[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq h(n)?\] This was resolved by Bergman [Be11], who proved that for any \(2\leq i<j\leq n/2\)…
Sylvester and Schur: for \(1 \le i \le n/2\) there is a prime \(p > i\) dividing n.choose i.
Let \(f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})\) and let \(P(n)\) be the largest prime dividing \(n\). **(a)** Characterise those composite \(n\) such that \(f(n) = n/P(n)\). Erdős–Szekeres [ErSz78] note that \(f(n) = n/P(n)\)…
Let \(f(n)\) be minimal such that, for any \(A=\{a_1,\ldots,a_n\}\subseteq [2,\infty)\cap\mathbb{N}\) of size \(n\), in any interval \(I\) of \(f(n)\max(A)\) consecutive integers there exist distinct \(x_1,\ldots,x_n\in I\) such that…
Let \(f(n)\) be minimal such that in \((n,n+f(n))\) there exist distinct integers \(a_1,\ldots,a_n\) such that \(k\mid a_k\) for all \(1\leq k\leq n\). Obtain an asymptotic formula for \(f(n)\).
Let \(f(n,m)\) be minimal such that \((m,m+f(n,m))\) contains distinct integers \(a_1,\ldots,a_n\) with \(k \mid a_k\) for \(1 \leq k \leq n\). Prove that \(\max_m f(n,m) \leq n^{1+o(1)}\).
As \(n\to \infty\) ranges over integers \(\sum_{p\leq n}1_{n\in (p/2,p)\pmod{p}}\frac{1}{p}\sim \frac{\log\log n}{2}\)? A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. By \(n\in (p/2,p)\pmod{p}\) we mean \(n\equiv r\pmod{p}\)…
Let \(k ≥ 2\). Does \(((n+k)!)^2∣(2n)!\) hold for infinitely many \(n\)?
Let \(\varepsilon\) be sufficiently small and \(C, C' > 0\). Are there integers \(a, b, n\) such that \[a, b > \varepsilon n\quad a!\, b! \mid n!\, (a + b - n)!, \] and \[C \log n < a + b - n < C' \log n ?\] Note that the website currently…
Let \(C>0\) be a constant. Are there infinitely many integers \(a,b,n\) with \(a+b> n+C\log n\) such that the denominator of \[\frac{n!}{a!b!}\]contains only primes \(\ll_C 1\)? Erdős [Er68c] proved that if \(a!b!\mid n!\) then…
Are there infinitely many pairs of integers \(n < m\) such that \(\binom{2n}{n}\) and \(\binom{2m}{m}\) have the same set of prime divisors? Yes: there are infinitely many consecutive pairs \((n, n+1)\). The formal proof registered as…
Find some reasonable function \(f(n)\) such that, for almost all integers \(n\), the least integer \(m\) such that \(m\nmid \binom{2n}{n}\) satisfies \[m\sim f(n).\] Here "almost all" means natural density \(1\), and \(m \sim f(n)\) means…
Cameron-Erdős conjecture
Let \(f(n)\) count the number of sum-free \(A\subseteq \{1,\ldots,n\}\), i.e. \(A\) contains no solutions to \(a=b+c\) with \(a,b,c\in A\). Is it true that \[f(n)=2^{(1+o(1))\frac{n}{2}}?\] The Cameron–Erdős conjecture. This is true, and…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A(n) = cN+O(1)?\] A conjecture of Erdős and Turán. Erdős and Fuchs [ErFu56] proved that the answer is no in a strong form: in fact…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+O(1)?\] The case of \(1_A\ast 1_A(n)\) is the subject of [763](https://www.erdosproblems.com/763). The answer is…
Let \(c(n)\) be minimal such that if \(k\geq c(n)\) then the \(n\)-dimensional unit cube can be decomposed into \(k\) homothetic \(n\)-dimensional cubes. Give good bounds for \(c(n)\) — in particular, is it true that \(c(n)\gg n^n\)? The…
For every prime p, does the density of integers with h n = p exist?
Let \(k\geq 1\) and \(H_k(n)\) be the maximal \(r\) such that if \(A\subset\mathbb{N}\) has \(\lvert A\rvert=n\) and \(\| 1_A\ast 1_A\|_\infty \leq k\) then \(A\) contains a Sidon set of size at least \(r\). Is it true that…
What is the size of the largest Sidon subset \(A\subseteq\{1,2^2,\ldots,N^2\}\)? Is it \(N^{1-o(1)}\)?
Is every proportionately dissociated (infinite) set the union of a finite number of dissociated sets?
Let \(\epsilon > 0\). Is there some set \(A\subset\mathbb{N}\) of density \(> 1 - \epsilon\) such that \(a_1\cdots a_r = b_1\cdots b_s\) with \(a_i, b_j\in A\) can only hold when \(r = s\)?
Let \(F(n)\) be the maximum possible size of a subset \(A \subseteq \{1, \ldots, n\}\) such that \(a \nmid bc\) whenever \(a, b, c \in A\) with \(a \neq b\) and \(a \neq c\). Is there a constant \(c\) such that \[F(n) = \pi(n) + (c + o(1))…
Let \(k\geq 2\) and let \(g_k(n)\) be the largest possible size of \(A\subseteq \{1,\ldots,n\}\) such that every \(m\) has \(<k\) solutions to \(m=a_1a_2\) with \(a_1<a_2\in A\). Is it true that \[g_3(n)=\frac{\log\log n}{\log…
Let \(H(n)\) be the smallest integer \(l\) such that there exists \(k < l\) with \((k^n-1, l^n-1) = 1\). Is it true that \(H(n) = 3\) infinitely often? That is, is \((2^n-1, 3^n-1) = 1\) for infinitely many \(n\) (see…
Is it true that, for every \(\epsilon>0\), there exist infinitely many \(n\) such that \(g(n) > n^{1-\epsilon}\)?
Does the set of integers of the form \(n + \varphi(n)\) have positive (lower) density? [GIL24] proved this was true.
Let \(h(x)\) count the number of integers \(1\leq a<b<x\) such that \((a,b)=1\) and \(\sigma(a)=\sigma(b)\), where \(\sigma\) is the sum of divisors function. Is it true that \(h(x)>x^{2-o(1)}\)? That is, is it true that for every…
Is there an absolute constant \(C > 0\) such that every integer \(n\) with \(\sigma(n) > Cn\) is the distinct sum of proper divisors of \(n\)? This has been solved in the affirmative by Larsen - in fact, for any \(\epsilon>0\) there exists…
Are there infinitely many \(n\) such that, for all \(k\geq 1\) \[ \tau(n + k) \ll k? \]
Is it true that, for any \(a \in \mathbb{Z}\), there are infinitely many \(n\) such that \[\phi(n) | n + a\]?
**Erdős Problem 829 (open).** Let \(A \subseteq \mathbb{N}\) be the set of perfect cubes. Is it true that \((1_A \ast 1_A)(n) \ll (\log n)^{O(1)}\)? That is, does there exist a natural number \(C\) such that the number of representations…
**Erdos Problem 830, Part 1** We say that \(a,b\in \mathbb{N}\) are an amicable pair if \(\sigma(a)=\sigma(b)=a+b\). Are there infinitely many amicable pairs?
Erdős Problem 839 (Part 1) [Er78f][Er92c]: Let \(1 \leq a_1 < a_2 < \cdots\) be a strictly increasing sequence of positive integers such that no \(a_i\) is the sum of consecutive \(a_j\) for \(j < i\). Is it true that…
Let \(t_n\) be minimal such that \(\{n+1,\ldots,n+t_n\}\) contains a subset whose product with \(n\) is a square number (and let \(t_n=0\) if \(n\) is itself square). Estimate \(t_n\). A problem of Erdős, Graham, and Selfridge. For…
Let \(A\subseteq \{1,\ldots,N\}\) be such that, for all \(a,b\in A\), the product \(ab\) is not squarefree. Is the maximum size of such an \(A\) achieved by taking \(A\) to be the set of even numbers and odd non-squarefree numbers? A…
Let \(C > 0\). Is it true that the set of integers of the form \(n = b_1 + \cdots + b_t\), with \(b_1 < \cdots < b_t\), where \(b_i = 2^{k_i}3^{l_i}\) for \(1 \leq i\leq t\) and \(b_t \leq Cb_1\) has density \(0\)? van Doorn and Everts…
Is the maximum size of a set \(A ⊆ \{1, \dots, N\}\) such that \(ab + 1\) is never squarefree (for all \(a, b ∈ A\)) achieved by taking those \(n ≡ 7 \pmod{25}\)? This asks whether Erdos848 N holds for all \(N\) (formulated using A ⊆…
Singmaster's conjecture
Is it true that, for every integer \(t\geq1\), there is some integer \(a\) such that \({n \choose k} = a\) with \(1\leq k \le \frac{n}{2}\) has exactly \(t\) solutions?
Erdős-Woods conjecture
Can there exist two distinct integers \(x\) and \(y\) such that \(x,y\) have the same prime factors, \(x+1,y+1\) have the same prime factors, and \(x+2,y+2\) also have the same prime factors?
Let \(\epsilon > 0\). Is there some \(r \ll_\epsilon 1\) such that the density of integers of the form \(2^k+n\), where \(k \geq 0\) and \(n\) has at most \(r\) prime divisors, is at least \(1-\epsilon\)? This was proved affirmatively by…
Let \(d_n = p_{n+1} - p_n\), where \(p_n\) is the \(n\)th prime. Let \(h(x)\) be maximal such that for some \(n < x\) the numbers \(d_n, d_{n+1}, \ldots, d_{n+h(x)-1}\) are all distinct [Er85c]. Estimate \(h(x)\). In particular, is it true…
Let \(d_n = p_{n+1} - p_n\), where \(p_n\) is the \(n\)th prime. Let \(r(x)\) be the smallest even integer \(t\) such that \(d_n = t\) has no solutions for \(n \le x\). Is it true that \(r(x) \to \infty\)?
second Hardy-Littlewood conjecture
Erdős Problem 855 (Segal's conjecture): \(\pi(x + y) \le \pi(x) + \pi(y)\) for all sufficiently large \(x, y\), i.e. for all \(x, y \ge N\) for some \(N\).
Let \(A\subseteq \{1,\ldots,N\}\) be such that there is no solution to \(at=b\) with \(a,b\in A\) and the smallest prime factor of \(t\) is \(>a\). Estimate the maximum of \[\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}.\] This has been solved…
The density of the divisor sum set is asymptotically equivalent to \(c_1 / \log(t)^{c_2}\).
Let \(h(n)\) be such that, for any \(m\geq 1\), in the interval \((m,m+h(n))\) there exist distinct integers \(a_i\) for \(1\leq i\leq \pi(n)\) such that \(p_i\mid a_i\), where \(p_i\) denotes the \(i\)th prime. Estimate \(h(n)\).
Let \(A_1(N)\) be the number of maximal Sidon subsets of \(\{1,\ldots,N\}\). Is it true that \[A_1(N) < 2^{o(N^{1/2})}?\] A problem of Cameron and Erdős. This is resolved as a consequence of results of Saxton and Thomason [SaTh15] - they…
Let \(A\subseteq \{1,\ldots,N\}\) be a set such that there exists at most one \(n\) with more than one solution to \(n=a+b\) (with \(a\leq b\in A\)). Estimate the maximal possible size of \(|A|\). In particular, is it true that \[|A| \leq…
There exists a constant \(C>0\) such that, for all large \(N\), if \(A\subseteq \{1,\ldots,N\}\) has size at least \(\frac{5}{8}N+C\) then there are distinct \(a,b,c\in A\) such that \(a+b,a+c,b+c\in A\). A problem of Erdős and Sós (also…
Let \(A\) be an additive basis of order \(2\), let \(f(n)\) denote the number of ways in which \(n\) can be written as the sum of two elements from \(A\). If \(f(n) \to \infty\) as \(n \to \infty\), then must \(A\) contain a minimal…
If \(A_1, A_2\) are disjoint additive bases of order \(2\) (i.e. \(A_i + A_i\) contains all large integers) then must \(A = A_1 \cup A_2\) contain a minimal additive basis of order \(2\) (one such that deleting any element creates…
Let \(A\) be an additive basis of order \(2\), and suppose \(1_A\ast 1_A(n)\to \infty\) as \(n\to \infty\). Can \(A\) be partitioned into two disjoint additive bases of order \(2\)? A question of Erdős and Nathanson [ErNa88], who proved…
Erdős Problem 872, part (i) (weak form): there exists a constant \(\epsilon > 0\) such that the game length is at least \(\epsilon \cdot n\) for all sufficiently large \(n\).
Let \(A = \{a_1 < a_2 < \dots\} \subseteq \mathbb{N}\) and let \(F(A,X,k)\) count the number of \(i\) such that \([a_i,a_{i+1}, \dots ,a_{i+k−1}] < X\), where the left-hand side is the least common multiple. Is it true that, for every…
Is it true that, for almost all \(n\), \(f(n)=o(n\log\log n)\) and \(F(n)\gg n\log\log n\)? The answer is yes; a Lean proof is given in [Ki26].
Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A \ B is not a basis of order k. Must there exist an infinite B ⊂ A such that A \ B is an additive basis of order k + 1?
What is the size of the largest \(A\subseteq \{1,\ldots,n\}\) such that in the set \[\left\{ \sum_{a\in S} a : \emptyset\neq S\subseteq A\right\}\] no two distinct elements divide each other? A problem of Erdős and Sárközy. The answer is…
For \(A\subseteq \{1,\ldots,n\}\) let \(G(A)\) be the graph with vertex set \(A\), where two integers are joined by an edge if they are coprime. Is it true that if \[|A| > \lfloor n/2 \rfloor + \lfloor n/3 \rfloor - \lfloor n/6 \rfloor\]…
For a natural number n, let \(1 = d_1 < \dotsc < d_{\tau(n)} = n\) denote the divisors of \(n\) in increasing order. Does it hold that…
Is it true that, for every \(k \geq 1\), there exist integers \(N_1 < \dots < N_k\) such that \(|\cap_i D(N_i)| \geq k\)?
Let \(\epsilon>0\). Is it true that, for all large \(n\), the number of divisors of \(n\) in \((n^{1/2},n^{1/2}+n^{1/2-\epsilon})\) is \(O_\epsilon(1)\)? Erdős attributes this conjecture to Ruzsa.
Is there an absolute constant \(K\) such that, for every \(C > 0\), if \(n\) is sufficiently large then \(n\) has at most \(K\) divisors in \((n^{\frac{1}{2}}, n^{\frac{1}{2}} + C n^{\frac{1}{4}})\).
What is the size of the largest \(A\subseteq \{1,\ldots,n\}\) such that if \(a\leq b\leq c\leq d\in A\) are such that \(abcd\) is a square then \(ad=bc\)? This was proved by GPT-5.5 Pro (prompted by Chojecki).
Let \(v(n,k)\) count the prime factors of \(n+k\) which do not divide \(n+i\) for \(0\leq i < k\). Is it true that \(v_0(n)=\max_{k\geq 0}v(n,k)\to \infty\) as \(n\to \infty\)?
If \(\omega_k(n)\) counts the number of distinct prime factors of \(n\) which are \(>k\), then is it true that, for every \(k\geq 1\), \[\liminf_{n\to \infty}\sum_{0\leq i < k}\omega_k(n+i)\leq k?\]
Let \(2=p_1 < p_2 < \cdots\) be the primes and \(k\geq 2\). Is it true that, for all sufficiently large \(n\), there must exist an integer in \([n,n+p_1\cdots p_k)\) with \(>k\) many prime factors?
Does the limit \(\lim_{n\to\infty} \frac{f(2n)}{f(n)}\) tend to infinity? (Other finite limits have been ruled out by [KoLu25], see below)
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\)). Is it true that there must exist a finite colouring of \(\mathbb{N}\) with no…
Let \(f(n)\) be an additive function (so that \(f(ab)=f(a)+f(b)\) if \((a,b)=1\) such that \(\limsup_{p,k} f(p^k) / \log(p^k) = ∞\). Is it true that \(\limsup_n (f(n+1)−f(n))/ \log n = ∞\)? The answer is no; this follows from a…
Prove that there exists some \(c>0\) such that \[h(n) \sim c \left(\frac{n}{\log n}\right)^{1/2}\] as \(n\to \infty\).
Are there infinitely many \(n\) such that if \[ n(n + 1) = \prod_i p_i^{k_i} \] is the factorisation into distinct primes then all exponents \(k_i\) are distinct?
Is it true that, for every \(r\), there is a \(k\) such that if \(I_1,\ldots,I_r\) are disjoint intervals of consecutive integers, all of length at least \(k\), then \[ \prod_{1\leq i\leq r}\prod_{m\in I_i}m \] is not a perfect power?
Let \(k_1 \geq k_2 \geq 3\). Are there only finitely many \(n_2\geq n_1 + k_1\) such that \[ \prod_{1\leq i\leq k_1}(n_1 + i)\ \text{and}\ \prod_{1\leq j\leq k_2} (n_2 + j) \] have the same prime factors?
Let \(p_k\) denote the \(k\)th prime. For infinitely many \(r\) there are at least two integers \(p_r < n < p_{r+1}\) all of whose prime factors are \(< p_{r + 1} - p_r\).
If \(n(n+1)=2^k3^lm\), where \((m,6)=1\), then is it true that \(\limsup_{n\to \infty} \frac{2^k3^l}{n\log n}=\infty\)?
Are there infinitely many four-term arithmetic progressions of coprime powerful numbers? (A number \(n\) is *powerful* if \(p \mid n \to p^2 \mid n\); Nat.Powerful.) Erdős [Er76d] asked this; the answer is **yes**: Bajpai, Bennett and Chan…
Let \(A=\{n_1 < n_2 < \cdots\}\) be the sequence of powerful numbers (if \(p\mid n\) then \(p^2\mid n\)). Are there only finitely many three-term progressions of consecutive terms \(n_k,n_{k+1},n_{k+2}\)?
If \(r≥4\) then can the sum of \(r-2\) coprime \(r\)-powerful numbers ever be itself \(r\)-powerful?
Let \(r \ge 3\). Is it true that the set of integers which are the sum of at most \(r\) \(r\)-powerful numbers has density \(0\)?
Is there some constant \(c > 0\) such that \(h(n) < (\log n)^{c + o(1)}\) and, for infinitely many \(n\), \(h(n) > (\log n)^{c - o(1)}\).
Let \(A\) be the set of powerful numbers. Is is true that \(1_A\ast 1_A(n)=n^{o(1)}\) for every \(n\)?
Is it true that \(F(x) \leq (\log x)^{O(1)}\)?
There are infinitely many \(n\) such that \(τ(n) = τ(n+1)\). Proved in [He84]. Here τ is the divisor counting function, which is σ 0 in mathlib.
There is no exact covering system - that is, a finite collection of congruence classes \(a_i\pmod{n_i}\) with distinct \(n_i\) such that every integer satisfies exactly one of these congruence classes. This is true, and was proved…
Is there a function \(f(n)\) and a \(k\) such that in any \(k\)-colouring of the integers there exists a sequence \(a_1 < a_2 < \cdots\) such that \(a_n < f(n)\) for infinitely many \(n\) and the set \[\left\{ \sum_{i \in S} a_i :…
Is it true that \(\liminf f(n)=1\)?
If 1 < a 0 < ... has property Erdos951Prop, is it true that #{a i ≤ x} ≤ π x?
Gaussian moat problem
Is there an infinite sequence of distinct Gaussian primes \(x_1,x_2,\ldots\) such that \(\lvert x_{n+1}-x_n\rvert \ll 1\)? No. This was disproved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
If \(A\subset \mathbb{N}\) has density \(0\) then \(s^{-1}(A)\) must also have density \(0\). A conjecture of Erdős, Granville, Pomerance, and Spiro [EGPS90].
Sylvester and Schur [Er34] proved that every set of \(k\) consecutive integers greater than \(k\) contains an integer divisible by a prime greater than \(k\), i.e. not \((k+1)\)-smooth.
Main conjecture: \(\log k(n) \le (\log n)^{(1/2 + o(1))}\)
Let \(k,r\geq 2\). Does there exist a set \(A\subseteq \mathbb{N}\) that contains no non-trivial arithmetic progression of length \(k+1\), yet in any \(r\)-colouring of \(A\) there must exist a monochromatic non-trivial arithmetic…
Let \(1<a_1<\cdots\) be a sequence of integers such that \(\sum\frac{1}{a_i}<\infty\). Is it true that, for every \(t\in \mathbb{R}\), \[1+\sum_{k}\frac{1}{a_k^{1+it}}\neq 0?\] Yip [Yi25] has proved that this is not always true - in fact,…
Does the set {n | u n < u (n+1)} have positive lower density? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
Jacobsthal's function
Let \(h(k)\) be Jacobsthal's function, defined to as the minimal \(m\) such that, if \(n\) has at most \(k\) prime factors, then in any set of \(m\) consecutive integers there exists an integer coprime to \(n\). Determine the order of…
Let p(a, d) be the least prime congruent to a (mod d). Does there exist a constant c > 0 such that for all large d, p(a, d) > (1 + c) * φ(d) * log d for ≫ φ(d) many values of a?
**Erdős problem 972.** Let \(\alpha > 1\) be irrational. Are there infinitely many primes \(p\) such that \(\lfloor p\alpha \rfloor\) is also prime?
For an irreducible polynomial \(f \in \mathbb{Z}[x]\) with \(f(n) \ge 1\) for sufficiently large \(n\), does there exists a constant \(c = c(f) > 0\) such that \(\sum_{n \le x} \tau(f(n)) \approx c \cdot x \log x\)? Note that it is unclear…
If \(P(m)\) is the greatest prime divisor of \(m\), then is it true that \[\frac{P(2^n-1)}{n}\to \infty\] as \(n\to \infty\)? Schinzel [Sc62] proved that \(P(2^n-1)>2n\) for \(n>12\). In [Er65b] Erdős also asks about \(P(n!+1)\). Stewart…
Let f ∈ ℤ[X] be an irreducible polynomial with positive leading coefficient. Suppose that the degree k of f is larger than 2, is not equal to a power of 2, and f n has no fixed (k - 1)-th power divisors other than 1. Then the set of n such…
Let \(k ≥ 2\), and let \(f_k(n)\) count the number of solutions to \(n = p_1^k + \dots + p_k^k\), where the \(p_i\) are prime numbers. Is it true that \(\limsup f_k(n) = \infty\)?
Let \(\epsilon > 0\) and \(f_\epsilon(p)\) be the smallest integer \(m\) such that \(\sum_{n\leq N} \left(\frac{n}{p}\right)<\epsilon N\) for all \(N\geq m\). Prove that \[\sum_{p<x}f_\epsilon(p)\sim c_\epsilon \frac{x}{\log x}\] for some…
Is it true that, for every prime \(p\), there is a prime \(q \leq p\) which is a primitive root modulo \(p\)?
Duffin-Schaeffer conjecture
For any function \(f:\mathbb{N}\to \mathbb{R}_{\geq 0}\) the property that, for almost all \(\alpha\) \[\left\lvert \alpha-\frac{p}{q}\right\rvert < \frac{f(q)}{q}\] has infinitely many solutions with \((p,q)=1\), is equivalent to…
Let \(A=\{n_1<n_2<\cdots\}\) be an infinite sequence of positive integers, and let \(\phi_A(k)\) count the number of \(1\leq m\leq n_k\) such that the fraction \(\frac{m}{n_k}\) cannot be written as \(\frac{b}{n_j}\) for any integer \(b\)…
Are there infinitely many solutions to \(\phi(n) = \phi(n+1)\), where \(\phi\) is the Euler totient function?
For any fixed c > 0, if x is sufficiently large then there exists n ≤ x such that the values of φ(n+k) are all distinct for 1 ≤ k ≤ (log x)^c. This is an open problem.
Let \(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \ldots\) be the Farey fractions of order \(n \geq 4\). Let \(f(n)\) be the largest integer such that if \(1 \leq k < l \leq k + f(n)\) then \(\frac{a_k}{b_k}\) and \(\frac{a_l}{b_l}\) are similarly…
unitary perfect numbers
Are there only finitely many unitary perfect numbers?
multiply perfect numbers
Let \(f(n)\) be the minimal integer \(m\) such that \(n\) is the sum of the \(k\) smallest divisors of \(m\) for some \(k\geq 1\). Is it true that \(f(n)=o(n)\)? The strong claim that \(f(n)=o(n)\) was disproved by Tao in the comments to…
A prime \(p\) is in class \(1\) if the only prime divisors of \(p+1\) are \(2\) or \(3\). In general, a prime \(p\) is in class \(r\) if every prime factor of \(p+1\) is in some class \(\leq r-1\), with equality for at least one prime…
Let \(k ≥ 2\). Does there exist a prime \(p\) and consecutive intervals \(I_0,\dots,I_k\) such that \(\prod\limits_{n{\in}I_i}n \equiv 1 \mod n\) for all \(1 \le i \le k\)?
Carmichael numbers
Is it true that \(C(x)=x^{1-o(1)}\)? This is discussed in problem A13 of Guy's collection [Gu04].
Let \(2=p_1<p_2<\cdots\) be the sequence of prime numbers. Are there only finitely many \(n\) such that \(n\in [p_{k-1},p_k)\) and the only primes dividing \(n!+1\) are \(p_{k}\) and \(p_{k+1}\)? A conjecture of Erdős and Stewart, as…
Are there infinitely many primes \(p\) such that \(p - k!\) is composite for each \(k\) such that \(1 ≤ k! < p\)?
The conjecture is about the function \(f(n)\) which counts the number of solutions to \(k\sigma(k)=n\), where \(\sigma(k)\) is the sum of divisors of \(k\). The first bound is that \(f(n)\) grows slower than any power of…
How many (ordered) solutions are there to σ(a) + σ(b) = σ(a + b) with a + b ≤ x? Is it true that this number is asymptotic to c * x for some constant c > 0?
Erdős asked whether the limiting density f n / n exists and, if so, whether it is irrational.
Estimate \(n_k\) by finding a better upper bound than Cambie's \(n_k \leq k \cdot \operatorname{lcm}(1, \dotsc, k-1)\). The comparator takes its least common multiple in ℕ and casts the result. Writing the ascription as ((… ).lcm (fun n :…
Let \(ϕ(n)\) be the Euler's totient function, then the \(n\) satisfies \(ϕ(n)>ϕ(n - ϕ(n))\) have asymptotic density 1. Reference: [LuPo02] Luca, Florian and Pomerance, Carl, On some problems of {M}\polhk akowski-{S}chinzel and {E}rd\H os…
Are there infinitely many primes \(p\) such that \(p = 2^k * q + 1\) for some prime \(q\) and \(k ≥ 0\)? This is mentioned as B46 in [Unsolved Problems in Number Theory](https://doi.org/10.1007/978-0-387-26677-0) by *Richard K. Guy*
Is it true that there are infinitely many \(p\) for which \(f(p) = p − 1\)?
Is it true that \(A(x) \le x^{o(1)}\)?
Let \(S\) be the set of all \(m\geq 1\) such that there exists a prime \(p\not\equiv 1\pmod{m}\) such that \(m! + 1 \equiv 0\pmod{p}\). Does \[ \lim\frac{|S\cap[1, x]|}{x} \] exist?
Are there infinitely many binomial coefficients with deficiency 1?
For all \(n\ge 2k\) the least prime factor of \(\binom{n}{k}\) is \(\le\max(n/k,k)\), with only finitely many exceptions.
Let \(1<q<1+\epsilon\) and consider the set of numbers of the shape \(\sum_{i\in S}q^i\) (for all finite \(S\)), ordered by size as \(0=x_1<x_2<\cdots\). Is it true that, provided \(\epsilon>0\) is sufficiently small,…
The main conjecture: for any finite set of integers \(A\) with \(|A| = n\), the number of distinct common differences in three-term arithmetic progressions is \(O(n^{3/2})\). This conjecture was resolved negatively by showing that the…
Let \(1=d_1<\cdots<d_{\tau(n)}=n\) be the divisors of \(n\), and for \(\alpha>1\) let \[h_\alpha(n) = \sum_i \left( \frac{d_{i+1}}{d_i}-1\right)^\alpha.\] Is it true that \[\liminf_{n\to \infty}h_\alpha(n) \ll_\alpha 1?\] Erdős [Er81h]…
1. There is NO good sequence with polynomial growth.
If A = {a₁ < a₂ < …} has property P, then A has natural density 0. Equivalently, (a_j / j) → ∞ as j → ∞. -
Let \(p(n)\) be the partition number of \(n\) and \(F(n)\) be the number of distinct prime factors of \(\prod_{i= 1} ^ {n} p(n)\), then \(F(n)\) tends to infinity when \(n\) tends to infinity. The answer is yes: Schinzel and Wirsing…
Let \(r \ge 2\). Is every large integer the sum of at most \(r + 1\) many \(r\)-powerful numbers?
For each \(k \geq 2\), does the set \(A = \left\{ \sum_{n\in S}n! : S\subset \mathbb{N}_{\geq 1}\text{ finite}\right\}\) of all finite sums of distinct factorials contain only finitely many \(k\)-th powers?
Let \(f(N)\) be the size of the largest subset \(A\subseteq \{1,\ldots,N\}\) such that every \(n\in A+A\) is squarefree. Estimate \(f(N)\). In particular, is it true that \(f(N)\leq N^{o(1)}\), or even \(f(N) \leq (\log N)^{O(1)}\)? This…
Let \(p>q\geq 2\) be two coprime integers. We call \(n\) representable if it is the sum of integers of the form \(p^kq^l\), none of which divide each other. If \(\{p,q\}\neq \{2,3\}\) then what can be said about the density of…
Sierpinski numbers
**Erdős Problem 1113.** Do there exist Sierpiński numbers that possess no finite covering set of primes? Erdős and Graham [ErGr80] conjectured that the answer is yes. A negative answer would imply that there are infinitely many Fermat…
Let \(f:\mathbb{N}\to \mathbb{R}\) be an additive function (i.e. \(f(ab)=f(a)+f(b)\) whenever \((a,b)=1\)). Let \[A=\{ n \geq 1: f(n+1)< f(n)\}.\] If \(\lvert A\cap [1,X]\rvert =o(X)\) then must \(f(n)=c\log n\) for some…
Let \(A\subseteq \mathbb{N}\) be the smallest set which contains \(1\) and is closed under the operations \[x\mapsto 2x+1,\quad x\mapsto 3x+1,\quad x\mapsto 6x+1.\] Does \(A\) have positive lower density? Lagarias [La16] reports that Erdős…
Collatz conjecture
The Collatz conjecture states that for any positive integer \(n\), there exists a natural number \(m\) such that the \(m\)-th term of the sequence is 1.
Does there exist \(A\subset \mathbb{N}\) with lower density \(>1/3\) such that \(a+b\neq 2^k\) for any \(a,b\in A\) and \(k\geq 0\)? Müller [Mu11] settled this question in the affirmative: in fact one can take \(A\) to be the set of all…
Let \(d_n=p_{n+1}-p_n\), where \(p_n\) denotes the \(n\)th prime. Is it true that \[\frac{\max_{n < x}d_{n}d_{n-1}}{(\max_{n < x}d_n)^2}\to 0\] as \(x\to \infty\)?
**Erdős Problem 1138.** Let \(x/2 < y < x\) and \(C > 1\). If \(d = \max_{p_n < x}(p_{n+1} - p_n)\), where \(p_n\) denotes the \(n\)-th prime, then is it true that \[\pi(y + Cd) - \pi(y) \sim \frac{Cd}{\log y}\]?
Let \(1\leq u_1 < u_2 < \cdots\) be the sequence of integers with at most \(2\) prime factors. Is it true that \[\limsup_{k \to \infty} \frac{u_{k+1}-u_k}{\log k}=\infty?\]
Are there infinitely many \(n\) such that \(n-k^2\) is prime for all \(k\) with \((n,k)=1\) and \(k^2 < n\)? In [Va99] it is asked whether \(968\) is the largest integer with this property, but this is an error, since for example…
Are there infinitely many \(n > 2\) such that \(n - 2^k\) is prime for all \(k \geq 1\) with \(2^k < n\)? The only known such \(n\) are \(4, 7, 15, 21, 45, 75, 105\) (OEIS [A039669](https://oeis.org/A039669)).
Is \(B=\{2^m3^n : m,n\geq 0\}\) an essential component? In [Ru99] Ruzsa states "The simplest set with a chance to be an essential component is the collection of numbers in the form \(2^m3^n\) and Erdős often asked whether it is an…
Can every large integer \(n\) be written as \(n=x^2+y^2-z^2\) with \(\max(x^2,y^2,z^2)\leq n\)? This was proved affirmatively by Chojecki [Ch26], using a Duke-type equidistribution theorem. A Lean formalisation of the reduction…
Let \(\alpha>0\) be a real number, not an integer. The density of integers \(n\geq 1\) for which \((n,\lfloor n^\alpha\rfloor)=1\) is \(6/\pi^2\). This is true, and was proved by Bergelson and Richter [BeRi17].
Let \(\epsilon>0\). Does there exist a constant \(C_\epsilon\) such that, for all primes \(p\), every residue modulo \(p\) is the sum of at most \(C_\epsilon\) many elements of \[\{ n^{-1} : 1\leq n\leq p^\epsilon\}\] where \(n^{-1}\)…
Let \(k\geq 3\). Is it true that, in any finite colouring of the integers, there are monochromatic arithmetic progressions of primes of length \(k\)? It follows from the theorem of Green and Tao [GrTa08] (that any set of primes with…
Call a set of distinct integers \(1<n_1<\cdots<n_k\) with associated congruence classes \(a_i\pmod{n_i}\) a distinct covering system if every integer satisfies at least one of these congruences. A minimal distinct covering system is one…
Let \[\epsilon_m=\max \sum \frac{1}{n_i}\] where the maximum is taken over all finite sequences \(m<n_1<\cdots<n_k\) for which there exist congruences \(a_i\pmod{n_i}\) such that no integer satisfies two such congruences. Estimate…
Is it true that, for any \(x\), if \(A\subset [x,\infty)\) is a primitive set of integers (so that no distinct elements of \(A\) divide each other) then\[\sum_{a\in A}\frac{1}{a\log a}< 1+o(1),\]where the \(o(1)\) term \(\to 0\) as…
Is it true that for every \(\epsilon,\eta>0\) there exists a \(k\) such that the density of \(n\) for which \(P(n(n+1)\cdots(n+k))>n^{1-\epsilon}\) is at least \(1-\eta\) (where \(P(m)\) is the greatest prime divisor of \(m\))?
Let \(\epsilon > 0\). Does there exist \(k\) such that, for every \(n\), any primes \(p_1 < \cdots < p_k < n^{1-\epsilon}\) and any sets \(A_i\) of \(\frac{p_i - 1}{2}\) residue classes modulo \(p_i\), the number of \(m \le n\) that avoid…
Prove that \(F(n)\to \infty\) as \(n\to \infty\).
Does \(\{1,2^3,\ldots,N^3\}\) contain a Sidon set of size \(\gg N\)?
Let \(A=\{a_1<a_2<\cdots\}\) be a sequence of integers which tends to infinity sufficiently fast. If there is an \(n\) such that all \(n+a_k\) are primes then must there exist infinitely many such \(n\)? Erdős [Er80] wrote 'unless I…
Let \(A\subseteq [1,n)\) be a set of integers such that \((a,b)=1\) for all distinct \(a,b\in A\). Is it true that \(\sum_{a\in A}\frac{1}{n-a}\leq \sum_{p < n}\frac{1}{p}+O(1)\)?
Let \(G\) be the graph with vertex set those pairs \((x,y)\in \mathbb{N}^2\) with \(\mathrm{gcd}(x,y)=1\), in which we join two vertices if the differ in only one coordinate, and there by \(\pm 1\). Is there a path going to infinity on…
Let \(x,y\geq 1\) be integers such that, for all \(n\geq 1\), the set of primes dividing \(x^{n}-1\) is equal to the set of primes dividing \(y^n-1\). Must \(x=y\)? Erdős asked this at a 1988 number theory conference in Banff. A positive…