Erdős–Woods numbers
- Description
A positive integer k is said to be an Erdős–Woods number if it has the following property: there exists a positive integer a such that in the sequence (a, a + 1, …, a + k) of consecutive integers, each of the elements has a non-trivial common factor with one of the endpoints. In other words, k is an Erdős–Woods number if there exists a positive integer a such that for each integer i between 0 and k, at least one of the greatest common divisors gcd(a, a + i) or gcd(a + i, a + k) is greater than 1.
It can be shown that there are infinitely many such numbers. Moreover, if k is an E-W number for some integer a, then one can find an infinite number of other a's using the formula a(jq + 1) where:
- q is the product of all odd prime factors of a + k; and
- j is any positive integer.
- Example
16 is an E-W number (and also the first) for which the smallest value of a is 2184. This is because in the sequence 2184 to 2200 inclusive, the prime factors of the endpoints are:
- 2³ x 3 x 7 x 13 = 2184
- 2³ x 5² x 11 = 2200
and, if you check all the numbers between them, you will find that they all have a prime factor in common with at least one of the endpoints (2189 is divisible by 11, 2191 by 7, 2197 by 13 and the rest by either 2, 3, or 5).
- Task
Compute and show here the first 20 E-W numbers together with their corresponding smallest value of a. If your language doesn't support arbitrary precision arithmetic, just compute and show as many as you can.
- Extra credit
Do the same for the next 20 E-W numbers.
- Note
Although all the E-W numbers relevant to this task are even, odd examples do exist the first one being k = 903.
- References
- OEIS sequence A059756: Erdős–Woods numbers.
- OEIS sequence A059757: Smallest values of a for a given E-W number k.
- Planet Math: Erdős–Woods numbers.
Julia
<lang julia>""" Returns the smallest value for `a` of the Erdős-Woods number n, or -1 if n is not in the sequence """ function erdős_woods(n)
primes = Int[] P = big"1" k = 1 while k < n P % k != 0 && push!(primes, k) P *= k * k k += 1 end divs = [evalpoly(big"2", [Int(a % p == 0) for p in primes]) for a in 0:n-1] np = length(primes) partitions = [(big"0", big"0", big"2"^np - 1)] ort(x) = trailing_zeros(divs[x + 1] | divs[n - x + 1]) for i in sort(collect(1:n-1), lt = (b, c) -> ort(b) > ort(c)) new_partitions = Tuple{BigInt, BigInt, BigInt}[] factors = divs[i + 1] other_factors = divs[n - i + 1] for p in partitions set_a, set_b, r_primes = p if (factors & set_a != 0) || (other_factors & set_b != 0) push!(new_partitions, p) continue end for (ix, v) in enumerate(digits(factors & r_primes, base=2)) if v == 1 w = 1 << (ix - 1) push!(new_partitions, (set_a ⊻ w, set_b, r_primes ⊻ w)) end end for (ix, v) in enumerate(digits(other_factors & r_primes, base=2)) if v == 1 w = 1 << (ix - 1) push!(new_partitions, (set_a, set_b ⊻ w, r_primes ⊻ w)) end end end partitions = new_partitions end result = big"-1" for (px, py, _) in partitions x, y = big"1", big"1" for p in primes isodd(px) && (x *= p) isodd(py) && (y *= p) px ÷= 2 py ÷= 2 end newresult = n * invmod(x, y) % y * x - n result = result == -1 ? newresult : min(result, newresult) end return result
end
function test_erdős_woods()
k, kcount = 16, 0 println("The first 20 Erdős–Woods numbers and their minimum interval start values are:") while kcount < 20 a = erdős_woods(k) if a != -1 println(lpad(k, 3), " -> $a") kcount += 1 end k += 1 end
end
test_erdős_woods()
</lang>
- Output:
Same as Wren example.
Python
Original author credit to the Stackexchange website user ovs, who in turn credits user xash. <lang python>""" modified from https://codegolf.stackexchange.com/questions/230509/find-the-erd%C5%91s-woods-origin/ """
def erdős_woods(n):
""" Returns the smallest value for `a` of the Erdős-Woods number n, or Inf if n is not in the sequence """ primes = [] P = k = 1 while k < n: if P % k: primes.append(k) P *= k * k k += 1 divs = [ int(.join(str((a%p==0) + 0) for p in primes)[::-1], 2) for a in range(n) ] np = len(primes) partitions = [(0, 0, 2**np-1)] for i in sorted( range(1,n), key = lambda x: bin(divs[x] | divs[n-x])[::-1].find('1'), reverse=True ): new_partitions = [] factors = divs[i] other_factors = divs[n-i] for p in partitions: set_a, set_b, r_primes = p if factors & set_a or other_factors & set_b: new_partitions += (p,) continue for ix, v in enumerate(bin(factors & r_primes)[2:][::-1]): if v=='1': w = 1 << ix new_partitions += ((set_a^w, set_b, r_primes^w),) for ix, v in enumerate(bin(other_factors & r_primes)[2:][::-1]): if v=='1': w = 1 << ix new_partitions += ((set_a, set_b^w, r_primes^w),) partitions = new_partitions result = float('inf') for px, py, _ in partitions: x = y = 1 for p in primes: if px % 2: x *= p if py % 2: y *= p px //= 2 py //= 2 result = min(result, n*pow(x,-1,y)%y*x-n) return result
K = 3
COUNT = 0
print('The first 20 Erdős–Woods numbers and their minimum interval start values are:')
while COUNT < 20:
a = erdős_woods(K) if a != float('inf'): print(f"{K: 3d} -> {a}") COUNT += 1 K += 1
</lang>
- Output:
Same as Wren example.
Wren
It's not easy to find a way of doing this in a reasonable time.
I ended up translating the Python 3.8 code (the more readable version) here, 6th post down, and found the first 20 E-W numbers in around 93 seconds. Much slower than Python which has arbitrary precision numerics built-in nowadays but acceptable for Wren. <lang ecmascript>import "./big" for BigInt import "./fmt" for Conv, Fmt import "./sort" for Sort import "./trait" for Indexed
var zero = BigInt.zero var one = BigInt.one var two = BigInt.two
var ew = Fn.new { |n|
var primes = [] var k = 1 var P = one while (k < n) { if ((P % k) != 0) primes.add(k) P = P * k * k k = k + 1 } var divs = [] var np = primes.count if (np > 0) { for (a in 0...n) { var A = BigInt.new(a) var s = primes.map { |p| Conv.btoi(A % p == 0).toString }.join()[-1..0] divs.add(BigInt.new(Conv.atoi(s, 2))) } } var partitions = [ [zero, zero, two.pow(np) - one] ] var key = Fn.new { |x| (divs[x] | divs[n-x]).toBaseString(2)[-1..0].indexOf("1") } var cmp = Fn.new { |i, j| (key.call(j) - key.call(i)).sign } for (i in Sort.merge((1...n).toList, cmp)) { var newPartitions = [] var factors = divs[i] var otherFactors = divs[n-i] for (p in partitions) { var setA = p[0] var setB = p[1] var rPrimes = p[2] if ((factors & setA) != zero || (otherFactors & setB) != zero) { newPartitions.add(p) continue } for (se in Indexed.new((factors & rPrimes).toBaseString(2)[-1..0])) { var ix = se.index var v = se.value if (v == "1") { var w = one << ix newPartitions.add([setA ^ w, setB, rPrimes ^ w]) } } for (se in Indexed.new((otherFactors & rPrimes).toBaseString(2)[-1..0])) { var ix = se.index var v = se.value if (v == "1") { var w = one << ix newPartitions.add([setA, setB ^ w, rPrimes ^ w]) } } } partitions = newPartitions } var result = null for (p in partitions) { var px = p[0] var py = p[1] var x = one var y = one for (p in primes) { if ((px % two) == one) x = x * p if ((py % two) == one) y = y * p px = px / two py = py / two } var N = BigInt.new(n) var temp = x.modInv(y) * N % y * x - N result = result ? BigInt.min(result, temp) : temp } return result
}
var k = 3 var count = 0 System.print("The first 20 Erdős–Woods numbers and their minimum interval start values are:") while (count < 20) {
var a = ew.call(k) if (a) { Fmt.print("$3d -> $i", k, a) count = count + 1 } k = k + 1
}</lang>
- Output:
The first 20 Erdős–Woods numbers and their minimum interval start values are: 16 -> 2184 22 -> 3521210 34 -> 47563752566 36 -> 12913165320 46 -> 21653939146794 56 -> 172481165966593120 64 -> 808852298577787631376 66 -> 91307018384081053554 70 -> 1172783000213391981960 76 -> 26214699169906862478864 78 -> 27070317575988954996883440 86 -> 92274830076590427944007586984 88 -> 3061406404565905778785058155412 92 -> 549490357654372954691289040 94 -> 38646299993451631575358983576 96 -> 50130345826827726114787486830 100 -> 35631233179526020414978681410 106 -> 200414275126007376521127533663324 112 -> 1022681262163316216977769066573892020 116 -> 199354011780827861571272685278371171794