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.
Determines how small the gaps of an infinite sum-free set of naturals can be, and whether the nth gap can stay below n.
Estimates the number of maximal sum-free subsets of the integers up to n and whether it is o(2^(n/2)); yes, and the count is a residue-dependent constant times two to the power of n over 4.
Compares f(n), the sum over the primes p dividing n of the largest power of p not exceeding n, with F(n), the largest sum of distinct pairwise coprime integers from 2 to n built from those primes.
Estimates the largest sum of a set of pairwise coprime integers up to n, and asks whether the best such set must contain a number with at least k prime factors.
Asks whether the integers representable as sums of k or fewer distinct members of an additive basis of order k have bounded gaps.
Concerns additive bases of order k that are minimal, in the sense that removing any infinite subset destroys the basis property.
The size of the largest subset of one to n whose nonempty subset sums form a set in which no element divides another.
Asks whether a subset of one to n above the triangle threshold of the coprime graph forces all odd cycles up to n/3 + 1 and, for large n, complete (1, l, l) tripartite subgraphs; the second was settled by Sárközy in 1999.
Asks whether the sum of one over all differences of divisors of n is bounded by a constant times one plus the sum of one over consecutive divisor gaps.
Asks whether, for every k, there are k integers whose sets of differences of complementary factor pairs share at least k common values.
Asks whether, for each fixed positive epsilon, every large n has only boundedly many divisors just above the square root of n.
Asks whether there is an absolute bound on the number of divisors of a large n lying within a constant times the fourth root of n above its square root.
The size of the largest subset of one to n in which any four elements with square product must pair off so the outer product equals the inner product.
Concerns the number of prime factors of n plus k that exceed k, that is, those dividing none of the earlier terms of the interval.
Asks whether the summed count of large distinct prime factors over k consecutive integers is infinitely often at most k, and about its extreme growth rate.
Asks whether, for each k at least 2 and every large enough n, the interval of length p_1...p_k starting at n contains an integer with more than k distinct prime factors.
Asks for a necessary and sufficient condition on an increasing sequence for a primitive sequence, no term dividing another, to grow no faster than it.
Asks whether the ratio of the summed divisor counts of two to the power k minus one, over k up to twice n and up to n, tends to a limit.
Asks whether the integers can be finitely colored with no two of one color differing by a term of a given lacunary sequence; proved, with Peres and Schlag's bound of order (1/epsilon) log(1/epsilon) colors as the best known.
Asks whether every large triangle-free graph on one to n contains three pairwise nonadjacent numbers of the form a, b and a plus b.
Estimates, for subsets A and B of {1,...,N}, the largest possible number of integers with exactly one representation ab with a in A and b in B; the order of magnitude is N^2/((log N)^delta (log log N)^(3/2)).
Asks whether an additive function whose values on prime powers are unboundedly large compared with the logarithm must have consecutive differences unboundedly large compared with log n, or even unbounded ratios.
Asks whether the sum of distances from an interior point to a triangle's vertices is at least twice the sum of its distances to the three sides.
Asks whether every infinite set of density zero has difference set counts that are infinitely often arbitrarily larger than its own counting function.
Asks whether the uniform random graph with n vertices and cn edges, c above one half, almost surely has a path of length f(c)n with f tending to 0 at one half and to 1 at infinity; proved by Ajtai, Komlós and Szemerédi, 1981.