Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether some graph on n vertices has as many as two to the number of vertex pairs divided by n factorial distinct subgraphs occurring in exactly one way.
Asks whether, for every n and d, some run of consecutive primes starting after the n-th prime has sum divisible by d.
Asks for a set with positive relative density among the primes such that, for infinitely many n, subtracting each member from n always gives a prime.
Asks whether a sufficiently sparse set missing a residue class modulo every prime must have some shift all of whose members are prime; disproved by Weisenberg's 2024 arbitrarily sparse admissible sets with no prime shift.
Concerns the greedy decreasing sequence in which each term is the largest smaller integer above 1 whose prime factors all exceed n minus that term, and asks whether some term is composite for every large n.
Asks whether two infinite sets have a sumset that agrees with the set of primes apart from finitely many exceptions.
Determines how dense the sumset of two infinite sets of natural numbers can be when all its elements are pairwise coprime.
Asks whether the largest non-representable integer for the worst coprime k-element subset of the first n integers is asymptotically n squared over k minus one.
Determines which coprime k-element subset of the first n integers leaves the most integers unrepresentable as sums of its members, and whether it is the top k.
The largest integer not expressible as a nonnegative integer combination of the binomial coefficients C(n,1), ..., C(n,n-1), for n not a prime power.
Asks whether the limiting least start of m consecutive k-th power residues modulo p is finite for m equal to two, and for m equal to three with k odd.
Estimates how many of the partial products of an increasing sequence bounded by x can be perfect squares, and whether nearly x of them can be.
The largest subset of the first N integers whose pairwise sums include no perfect square.
Asks whether every finite coloring of the integers has two distinct integers of one color summing to a square, or to a k-th power; proved by Khalfalah and Szemerédi for every non-constant polynomial with an even value.
Whether the number of consecutive pairs of an infinite set with least common multiple at most x is O(x^{1/2}), and how large the liminf of that count over x^{1/2} can be; both answered by Erdős and Szemerédi in 1980.
The largest subset of one through N with all pairwise least common multiples at most N, asymptotically the square root of 9N/8 by Chen, and whether Erdős's construction attains it, which Chen and Dai refute infinitely often.
Whether a set whose reciprocal sum grows faster than log log x forces the normalized sum of reciprocals of pairwise least common multiples to blow up; disproved by Tao, whose construction also gives the optimal growth threshold.
How many values are shared by the two sets of products k times m minus k and l times n minus l for m different from n, and whether this count can be large or must be very small.
Asks whether, for every k, an infinite set of integers has some integer below x with more divisors from the set than any power of the set's reciprocal sum.
Asks whether, for any exponent above one half and any large prime, every interval of that length contains two numbers whose product is one modulo the prime.
The growth rate of the density of integers having a divisor strictly between n and twice n.
The largest family of subsets of one through n in which no set is the union of two other distinct members of the family.
Asks whether, for almost all n, the number of dyadic ranges containing a divisor of n is an arbitrarily small fraction of the total number of divisors.
Asks whether, for almost all n, the number of pairs of divisors within a factor of two of each other is an arbitrarily small fraction of the divisor count.
How long an interval must be so that at most a small fraction of its integers have a divisor strictly between n and twice n.