Erdős-Woods number

An integer $k$ is an Erdős-Woods number if there is an integer $n$ such that each of the consecutive integers $n+i$ for shares at least one prime factor with either $n$ or $n+k$. In other words, if for a $k$ there is an $n$ such that each evaluation of $\gcd (n,n+i)>1$ or $\gcd (n+k,n+i)>1$ returns true, then $k$ is an Erdős-Woods number.

For example, one $n$ for $k=16$ is 2184. 2184 is $2^3\times 3\times 7\times 13$, while $2184+16=2200=2^3\times 5^2\times 11$. We then verify that

• 2185 is clearly divisible by 5 and thus shares that odd prime as a factor with 2200.

• 2186 is even and so shares 2 as a factor with both 2184 and 2200.

• 2187 is 3 more than 2184 and therefore must also be divisible by 3. In fact, it is $3^7$.

• 2188 is even and so shares 2 as a factor with both 2184 and 2200, suggesting we needn’t look at any other even numbers in this range.

• 2189 is 11 less than 2200 and therefore must be divisible by 11. In base 10 we can quickly verify that 2 + 8 = 10 and 1 + 9 is also 10.

• 2191 is 7 more than 2184 and thus must be divisible by 7.

• 2193 is 9 more than 2184 and thus divisible by 3.

• 2195 is obviously divisible by 5.

• 2197 is 13 more than 2184 and thus must be divisible by 13. In fact, it is ${13}^3$.

• 2199 is 15 more than 2184 and thus divisible by 3.

Knowing one $n$ for a given $k$ one can find other $n$ by multiplying the odd prime factors of $n+k$ (just once each, let’s call that product “$q$”) and then calculating $n(jq+1)$ with $j$ any positive integer of one’s choice. To give one example: with $n=2184$ and $j=17$, we get another $n$, namely 2044224. The range 2044224 to 2044240 displays the same patterns of factorization as described above, except that 2044227 and 2044237 are a semiprime and a sphenic number respectively, as opposed to 2187 and 2197 which are both prime powers.

Other Erdős-Woods numbers are 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92, 94, 96, 100, etc., listed in A059756 of Sloane’s OEIS (the smallest odd Erdős-Woods number is 903), while A059757 lists the smallest matching $n$ for each of those $k$.

Title	Erdős-Woods number
Canonical name	ErdHosWoodsNumber
Date of creation	2013-03-22 17:37:14
Last modified on	2013-03-22 17:37:14
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	4
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11A05
Synonym	Erdos-Woods number
Synonym	Erdös-Woods number