Erdős Problem #196
Must every permutation of ℕ, contain a monotone 4-term arithmetic progression?
No claims yet Be the first →
Erdős problems (Erdos problems) you can work on with AI
Paul Erdős posed hundreds of problems, many with cash prizes. Thomas Bloom collects them at erdosproblems.com, and a community database (teorth/erdosproblems) tracks their status. Most of the open ones listed here have Lean statements in Formal Conjectures; each imported page shows the status from erdosproblems.com, the prize if there is one, and what kind of progress would count.
Source: erdosproblems.com (Thomas Bloom). Licence: Lean statements from Formal Conjectures (Apache 2.0); status data from the community database teorth/erdosproblems (Apache 2.0).
Erdős Problem #197
Can ℕ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
No claims yet Be the first →
Erdős Problem #200
Does the longest arithmetic progression of primes in 1,…,N have length o(log N)?
No claims yet Be the first →
Erdős Problem #203
Is there an integer m with (m, 6) = 1 such that none of 2^k · 3^ℓ · m + 1 are prime, for any k, ℓ ≥ 0?
No claims yet Be the first →
Erdős Problem #208
Let s_1 < s_2 < … be the sequence of squarefree numbers. Is it true that for any ε > 0 and large n, s_n+1 - s_n ≪_ε s_n^ε?
No claims yet Be the first →
Erdős Problem #212
Is there a dense subset of ℝ^2 such that all pairwise distances are rational?
No claims yet Be the first →
Erdős Problem #213
Let n ≥ 4. Are there n points in ℝ^2, no three on a line and no four on a circle, such that all pairwise distances are integers?
No claims yet Be the first →
Erdős Problem #23
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
No claims yet Be the first →
Erdős Problem #233
A conjecture by Heath-Brown: The sum of squares of the first N gaps between consecutive primes behaves like N * (log N)^2.
No claims yet Be the first →
Erdős Problem #234
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?
No claims yet Be the first →
Erdős Problem #236
Let f(n) count the number of solutions to n=p+2^k for prime p and k≥ 0. Show that f(n)=o(log n).
No claims yet Be the first →
Erdős Problem #238
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₂?
No claims yet Be the first →
Erdős Problem #241
Is it true that f(N)∼ N^1/3? Originally asked to Erdős by Bose. This is discussed in problem C11 of Guy's collection [Gu04].
No claims yet Be the first →
Erdős Problem #243
Let a_1 < a_2 < … be a sequence of integers such that lim_n→∞ a_n/a_n-1^2 = 1 and Σ 1/a_n ∈ ℚ. Then, for all sufficiently large n ≥ 1, a_n = a_n-1^2 - a_n-1 + 1.
No claims yet Be the first →
Erdős Problem #244
Let C > 1. Does the set of integers of the form p + ⌊ C^k ⌋, for some prime p and k≥ 0, have density >0?
No claims yet Be the first →
Erdős Problem #247
Let n_1 < n_2 < ⋯ be a sequence of integers such that limsup n_k/k = ∞. Is Σ_k=1^∞ 1/2^n_k transcendental?
No claims yet Be the first →
Erdős Problem #249
Is Σ_n φ(n)/2^n irrational? Here φ is the Euler totient function.
No claims yet Be the first →
Erdős Problem #25
Let n_1 < n_2 < … be an arbitrary sequence of integers, each with an associated residue class a_i pmodn_i. Let A be the set of integers n such that for every i either n < n_i or n not≡ a_i pmodn_i. Must the logarithmic density of A exist?
No claims yet Be the first →
Erdős Problem #251
Is Σ_n=1^∞ p_n/2^n irrational? Here p_n is the n-th prime (p_1=2, p_2=3, …).
No claims yet Be the first →
Erdős Problem #252
Erdős Problem 252: irrationality of the sum for a given k.
No claims yet Be the first →
Erdős Problem #257
Let A⊆ℕ be an infinite set. Is Σ_n∈ A 1/2^n - 1 irrational?
No claims yet Be the first →
Erdős Problem #261
Do all positive integers n have the required property?
No claims yet Be the first →
Erdős Problem #263
Is a_n = 2^2^n an irrationality sequence in the above sense?
No claims yet Be the first →
Erdős Problem #264
Is n! an example of an irrationality sequence?
No claims yet Be the first →
Erdős Problem #272
Let N≥ 1. What is the largest t such that there are A_1,…,A_t⊆ 1,…,N with A_i∩ A_j a non-empty arithmetic progression for all i≠ j?
No claims yet Be the first →
Erdős Problem #273
Is there a covering system all of whose moduli are of the form p-1 for some primes p ≥ 5?
No claims yet Be the first →
Erdős Problem #274
If G is a group, can there exist an exact covering of G by more than one coset of different sizes? (i.e. each element is contained in exactly one of the cosets.) The conjectured answer is no: in every such exact covering, two of the subgroups have the same cardinality.
No claims yet Be the first →
Erdős Problem #276
Is there an infinite Lucas sequence a_0, a_1, … where a_n+2 = a_n+1 + a_n for n ≥ 0 such that all a_k are composite, and yet no integer has a common factor with every term of the sequence?
No claims yet Be the first →
Erdős Problem #279
Let k≥ 3. Is there a choice of congruence classes a_ppmodp for every prime p such that all sufficiently large integers can be written as a_p+tp for some prime p and integer t≥ k?
No claims yet Be the first →
Erdős Problem #28
If A ⊆ ℕ is such that A + A contains all but finitely many integers then limsup 1_A ∗ 1_A(n) = ∞.
No claims yet Be the first →
Erdős Problem #282
Let A⊆ ℕ be an infinite set and consider the following greedy algorithm for a rational x∈ (0,1): choose the minimal n∈ A not used so far such that n≥ 1/x and repeat with x replaced by x-1/n.
No claims yet Be the first →
Erdős Problem #287
Let k≥2. Is it true that, for any distinct integers 1 < n_1 < ⋯ < n_k such that Σ_i=1^k 1/n_i = 1, we must have max(n_i+1 - n_i) ≥ 3?
No claims yet Be the first →
Erdős Problem #288
Is it true that there are only finitely many pairs of intervals I_1, I_2 such that Σ_n_1 ∈ I_1 1/n_1 + Σ_n_2 ∈ I_2 1/n_2 ∈ ℕ?
No claims yet Be the first →
Erdős Problem #289
Is it true that, for all sufficiently large k, there exist finite intervals I_1, dotsc, I_k ⊂ ℕ, distinct, not overlapping or adjacent, with |I_i| ≥ 2 for 1 ≤ i ≤ k such that 1 = Σ_i=1^k Σ_n ∈ I_i 1/n?
No claims yet Be the first →
Erdős Problem #291
Let n≥ 1 and define L_n to be the least common multiple of 1,…,n and a_n by Σ_1≤ k≤ n1/k=a_n/L_n. Is it true that (a_n,L_n)=1 occurs for infinitely many n?
No claims yet Be the first →
Erdős Problem #295
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 → ∞ k(N) - (e - 1)N = ∞?
No claims yet Be the first →
Erdős Problem #3
If A ⊂ ℕ has Σ_n ∈ Afrac 1 n = ∞, then must A contain arbitrarily long arithmetic progressions?
No claims yet Be the first →
Erdős Problem #30
Is it true that, for every ε > 0, h(N) = sqrt N + O_ε(N^ε)
No claims yet Be the first →
Erdős Problem #302
Let f(N) be the size of the largest A⊆ 1,…,N such that there are no solutions to 1/a= 1/b+1/c with distinct a,b,c∈ A? Estimate f(N). The colouring version of this is [303], which was solved by Brown and Rödl [BrRo91].
No claims yet Be the first →
Erdős Problem #304
Is it true that N(b) ≪ log log b?
No claims yet Be the first →
Erdős Problem #306
Let frac a b∈ ℚ_>0 with b squarefree. Are there integers 1 < n_1 < … < n_k, each the product of two distinct primes, such that a/b=1/n_1+⋯+1/n_k?
No claims yet Be the first →
Erdős Problem #307
Are there two finite set of primes P and Q such that 1 = ( Σ_p ∈ P 1/p ) ( Σ_q ∈ Q 1/q ) ? Asked by Barbeau [Ba76]. [Ba76] Barbeau, E. J., _Computer challenge corner: Problem 477: A brute force program._
No claims yet Be the first →
Erdős Problem #312
Does there exist a constant c > 0 such that, for any K > 1, whenever A is a sufficiently large finite multiset of integers with Σ_n ∈ A 1/n > K there exists some S ⊆ A such that 1 - exp(-(c*K)) < Σ_n ∈ S 1/n ≤ 1?
No claims yet Be the first →
Erdős Problem #313
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: Σ_p ∈ P 1/p = 1 - 1/m?
No claims yet Be the first →
Erdős Problem #317
Is there some constant c>0 such that for every n≥ 1 there exists some δ_k∈ -1,0,1 for 1≤ k≤ n with 0< lvert Σ_1≤ k≤ nδ_k/krvert < c/2^n?
No claims yet Be the first →
Erdős Problem #319
What is the size of the largest A⊆1, …, N such that there is a function δ : A → -1, 1 such that Σ_n∈ A δ n/n = 0 and Σ_n∈ A'δ n/n ≠ 0 for all non-empty A'subsetneq A.
No claims yet Be the first →
Erdős Problem #32
Does there exist a set A ⊆ ℕ such that |A ∩ 1, …, N| = o((log N)^2) and every sufficiently large integer can be written as p + a for some prime p and a ∈ A?
No claims yet Be the first →
Erdős Problem #322
Let k≥ 3 and A⊂ ℕ be the set of kth 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 kth powers? Does there exist some c>0 and infinitely many n such that 1_A^(k)(n) >n^c?
No claims yet Be the first →
Erdős Problem #323
Is it true that f_k,k(x) ≫_ε x^1-ε for all ε>0? This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'.
No claims yet Be the first →
Erdős Problem #324
Does there exist a polynomial f(x)∈ℤ[x] such that all the sums f(a)+f(b) with a < b nonnegative integers are distinct?
No claims yet Be the first →
Erdős Problem #325
Writing f_k, 3(x) for the number of integers ≤ x which are the sum of three kth powers, is it true that f_k, 3(x) ≫ x ^ (3 / k)?
No claims yet Be the first →
Erdős Problem #326
Does there exist A = a_1 < a_2 < ⋯ ⊂ ℕ 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 lim_k→∞ a_k/k^2 = c for some c ≠ 0? Erdős and Graham conjectured a negative answer to this question [ErGr80].
No claims yet Be the first →
Erdős Problem #329
Erdős Problem 329. Let A ⊆ ℕ be a Sidon set. How large can lim sup_N → ∞ |A ∩ 1,…,N| / N^1/2 be?
No claims yet Be the first →
Erdős Problem #33
Let A ⊆ ℕ be a set such that every integer can be written as n^2 + a for some a in A and n ≥ 0. What is the smallest possible value of lim sup n → ∞ |A ∩ 1, …, N| / N^(1/2)?
No claims yet Be the first →
Erdős Problem #332
Let A⊆ ℕ and D(A) be the set of those numbers which occur infinitely often as a_1 - a_2 with a_1, a_2∈ A. What conditions on A are sufficient to ensure D(A) has bounded gaps? This is formalised here using the answer(sorry) mechanism.
No claims yet Be the first →
Erdős Problem #340
Let A = 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, … 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 to a + b = c + d). What is the order of growth of A?
No claims yet Be the first →
Erdős Problem #342
Do infinitely many pairs (a, a+2) occur in Ulam's sequence?
No claims yet Be the first →
Erdős Problem #348
For what values of 0 ≤ m < n is there a complete sequence A = a_1 ≤ a_2 ≤ ⋯ of integers such that 1. A remains complete after removing any m elements, but 2. A is not complete after removing any n elements.
No claims yet Be the first →
Erdős Problem #349
For what values of t,α ∈ (0,∞) is the sequence ⌊ tα^n⌋ complete (that is, all sufficiently large integers are the sum of distinct integers of the form ⌊ tα^n⌋)?
No claims yet Be the first →
Erdős Problem #352
Is there some c > 0 such that every measurable A ⊆ ℝ^2 of measure ≥ c contains the vertices of a triangle of area 1?
No claims yet Be the first →
Erdős Problem #354
Let α,β∈ ℝ_>0 such that α/β is irrational. Is the multiset ⌊ α⌋,⌊ 2α⌋,⌊ 4α⌋,…∪ ⌊ β⌋,⌊ 2β⌋,⌊ 4β⌋,… complete?
No claims yet Be the first →
Erdős Problem #357
Let f(n) be the maximal k such that there exist integers 1 ≤ a_1 < dotsc < a_k ≤ n such that all sums of the shape Σ_u ≤ i ≤ v a_i are distinct. Is f(n)=o(n)?
No claims yet Be the first →
Erdős Problem #359
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_js. Show that a_k / k → ∞.
No claims yet Be the first →
Erdős Problem #361
Let c > 0 and n be some large integer. What is the size of the largest set A ⊆ 1, …, ⌊ c n ⌋ such that n is not a sum of a subset of A? Does this depend on n in an irregular way?
No claims yet Be the first →
Erdős Problem #364
There is no consecutive triple of powerful numbers.
No claims yet Be the first →
Erdős Problem #366
Are there any 2-full n such that n+1 is 3-full?
No claims yet Be the first →
Erdős Problem #367
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 ≥ 1, Π_n ≤ m < n+k B_2(m) ≪ n^2+o(1)?
No claims yet Be the first →
Erdős Problem #371
Let P(n) denote the largest prime factor of n. Show that the set of n with P(n+1) > P(n) has density 1/2.
No claims yet Be the first →
Erdős Problem #373
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.
No claims yet Be the first →
Erdős Problem #375
Is Erdos375Prop true?
No claims yet Be the first →
Erdős Problem #376
Are there infinitely many n such that 2nchoose n is coprime to 105?
No claims yet Be the first →
Erdős Problem #377
Is there some absolute constant C > 0 such that Σ_p ≤ n 1_pnmid 2n choose n1/p ≤ C for all n?
No claims yet Be the first →
Erdős Problem #383
Is it true that for every k there are infinitely many primes p such that the largest prime divisor of Π_i = 0^k (p ^ 2 + i) is p?
No claims yet Be the first →
Erdős Problem #385
Let F(n) := maxm + p(m) | textrmm < n composite where p(m) is the least prime divisor of m. Is it true that F(n)>n for all sufficiently large n?
No claims yet Be the first →
Erdős Problem #386
Let 2 ≤ k ≤ n - 2. Can C(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 works infinitely often.
No claims yet Be the first →
Erdős Problem #389
Is it true that for every n ≥ 1 there is a k such that n(n + 1) ⋯ (n + k - 1) | (n + k) ⋯ (n + 2k - 1)?
No claims yet Be the first →
Erdős Problem #39
Is there an infinite Sidon set A⊂ ℕ such that lvert A∩ 1…,Nrvert ≫_ε N^1/2-ε for all ε > 0?
No claims yet Be the first →
Erdős Problem #390
Does there exists a constant c such that f n - 2 n ~ c (n / log n)?
No claims yet Be the first →
Erdős Problem #396
Is it true that for every k there exists n such that Π_0≤ i≤ k(n-i) | C(2n, n)?
No claims yet Be the first →
Erdős Problem #398
Brocard's Problem Does n! + 1 = m^2 have integer solutions other than n = 4, 5, 7?
No claims yet Be the first →
Erdős Problem #40
For what functions g(N) → ∞ is it true that lvert A∩ 1,…,Nrvert ≫ N^1/2/g(N) implies limsup 1_Aast 1_A(n)=∞?
No claims yet Be the first →
Erdős Problem #400
Can one show that Σ_n≤ xg_k(n) ∼ c_k xlog x for some constant c_k?
No claims yet Be the first →
Erdős Problem #406
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?
No claims yet Be the first →
Erdős Problem #409
Erdős Problem #409
No claims yet Be the first →
Erdős Problem #41
Let A ⊂ ℕ be an infinite set such that the triple sums a+b+c are all distinct for a,b,c ∈ A (aside from the trivial coincidences). Is it true that liminf_N → ∞ fraclvert A ∩ 1,…,NrvertN^1/3=0?
No claims yet Be the first →
Erdős Problem #410
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 = ∞?
No claims yet Be the first →
Erdős Problem #412
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)?
No claims yet Be the first →
Erdős Problem #413
Are there infinitely many barriers for ω?
No claims yet Be the first →
Erdős Problem #414
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)?
No claims yet Be the first →
Erdős Problem #416
Let V(x) count the number of n≤x such that ϕ(m)=n is solvable. Does V(2x)/V(x)→2 ?
No claims yet Be the first →
Erdős Problem #417
LetV'(x)=\#φ(m) : 1≤ m≤ xandV(x)=\#φ(m) ≤ x : 1≤ m. Does lim V(x)/V'(x) exist?
No claims yet Be the first →
Erdős Problem #422
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?
No claims yet Be the first →
Erdős Problem #423
Erdős Problem 423 [Er77c, p.71; ErGr80, p.83]: Let a(1) = 1, a(2) = 2, and for k ≥ 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 asymptotic behaviour of this sequence? It seems likely that a_n = n + o(n).
No claims yet Be the first →
Erdős Problem #428
Is there a set A⊆ ℕ such that, for infinitely many n, all of n-a are prime for all a∈ A with 0 < a < n and liminflvert A∩ [1,x]rvert/π(x)>0?
No claims yet Be the first →
Erdős Problem #431
Are there two infinite sets A and B such that A+B agrees with the primes up to finitely many exceptions?
No claims yet Be the first →
Erdős Problem #44
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?
No claims yet Be the first →
Erdős Problem #445
Is it true that, for any c>1/2, if p is a sufficiently large prime then, for any n≥ 0, there exist a,b∈(n,n+p^c) such that ab≡ 1pmodp? This is discussed in this MathOverflow question [MathOverflow].
No claims yet Be the first →
Erdős Problem #450
How large must y=y(ε,n) be such that the number of integers in (x,x+y) with a divisor in (n,2n) is at most ε y? The bound is required for every x and every window length at least y, and y(ε,n) is the least such threshold (or ∞ if there is none).
No claims yet Be the first →
Erdős Problem #452
Determine the largest length of an interval in [x,2x] on which ω(n) > loglog n everywhere.
No claims yet Be the first →
Erdős Problem #454
Is it true that limsup (fun n => (f n - 2 * n.nth Prime : ℕ∞)) atTop = ⊤?
No claims yet Be the first →