number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, a

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

is said to be an Erdős–Woods number if it has the following property: there exists a positive integer such that in the

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

of consecutive integers, each of the elements has a non-trivial

common factor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...

with one of the endpoints. In other words, is an Erdős–Woods number if there exists a positive integer such that for each integer between and , at least one of the

greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...

s or is greater than .

Examples

16 is an Erdős–Woods number because the 15 numbers between 2184 and each share a

prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

with one of and These 15 numbers and their shared prime factor(s) are: The first Erdős–Woods numbers are Although all of these initial numbers are even, odd Erdős–Woods numbers also exist. They include

Prime partitions

The Erdős–Woods numbers can be characterized in terms of certain partitions of the

prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

s. A number is an Erdős–Woods number if and only if the prime numbers less than can be partitioned into two subsets and with the following property: for every pair of positive integers and with , either is divisible by a prime in , or is divisible by a prime in . For this reason, these numbers are also called ''prime-partitionable numbers''. For instance, 16 is prime-partitionable with and . The representations of 16 as and corresponding prime divisors in and are:

History

In a 1971 paper,

Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

and John Selfridge considered intervals of integers containing an element coprime to both endpoints. They observed that earlier results of S. S. Pillai and George Szekeres implied that such an element exists for every interval of at most 16 integers; thus, no Erdős–Woods number can be less than 16. In his 1981 thesis, Alan R. Woods independently conjectured that whenever , the interval always includes a number

coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...

to both endpoints. It was only later that he found the first counterexample, , with . The existence of this counterexample shows that 16 is an Erdős–Woods number. proved that there are infinitely many Erdős–Woods numbers, and showed that the

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

of Erdős–Woods numbers is

recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...

. Meanwhile, the prime-partitionable numbers had been defined by Holsztyński and Strube in 1978, following which Erdős and William T. Trotter proved in 1978 that they form an infinite sequence. Erdős and Trotter applied these results to generate pairs of

directed cycle Direct may refer to: Mathematics * Directed set, in order theory * Direct limit of (pre), sheaves * Direct sum of modules, a construction in abstract algebra which combines several vector spaces Computing * Direct access (disambiguation), a ...

s whose

Cartesian product of graphs In graph theory, the Cartesian product of graphs and is a graph such that: * the vertex set of is the Cartesian product ; and * two vertices and are adjacent in if and only if either ** and is adjacent to in , or ** and is adjace ...

does not contain a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, and they used a computer search to find several odd prime-partitionable numbers, including 15395 and 397197. In 2014, M. F. Hasler observed on the

On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...

that the prime-partitionable numbers appeared to be the same as the Erdős–Woods numbers, and this was proven in the same year by Christopher Hunt Gribble. The same equivalence was also shown by Hasler and Mathar in 2015, together with an equivalence between two definitions of the prime-partitionable numbers from the two earlier works on the subject.

References

External links

*
Erdős-Woods numbers

Numberphile ''Numberphile'' is an Educational entertainment, educational YouTube channel featuring videos that explore topics from a variety of fields of mathematics. In the early days of the channel, each video focused on a specific number, but the channe ...

, June 30, 2024 {{DEFAULTSORT:Erdos-Woods number Woods number Integer sequences