I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Erdős–Woods numbers

Erdős–Woods numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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).

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

## Julia

Translation of: Python
`""" modified from https://codegolf.stackexchange.com/questions/230509/find-the-erd%C5%91s-woods-origin/ """ using BitIntegers """Returns the smallest value for `a` of Erdős-Woods number n, -1 if n is not in sequence"""function erdős_woods(n)    primes = Int[]    P = BigInt(1)    k = 1    while k < n        P % k != 0 && push!(primes, k)        P *= k * k        k += 1    end    divs = [evalpoly(2, [Int(a % p == 0) for p in primes]) for a in 0:n-1]    np = length(primes)    partitions = [(Int256(0), Int256(0), Int256(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{Int256, Int256, Int256}[]        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(reverse(string(factors & r_primes, base=2)))                if v == '1'                    w = Int256(1) << (ix - 1)                    push!(new_partitions, (set_a ⊻ w, set_b, r_primes ⊻ w))                end            end            for (ix, v) in enumerate(reverse(string(other_factors & r_primes, base=2)))                if v == '1'                    w = Int256(1) << (ix - 1)                    push!(new_partitions, (set_a, set_b ⊻ w, r_primes ⊻ w))                end            end        end        partitions = new_partitions    end    result = Int256(-1)    for (px, py, _) in partitions        x, y = Int256(1), Int256(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 resultend function test_erdős_woods(startval=3, endval=116)    arr = fill((0, Int256(-1)), endval - startval + 1)    @Threads.threads for k in startval:endval        arr[k - startval + 1] = (k, erdős_woods(k))    end    ewvalues = filter(x -> last(x) > 0, arr)    println("The first \$(length(ewvalues)) Erdős–Woods numbers and their minimum interval start values are:")    for (k, a) in ewvalues        println(lpad(k, 3), " -> \$a")    endend test_erdős_woods() `
Output:
Same as Wren example.

## Phix

Translation of: Wren
Translation of: Julia

Using flag arrays instead of bigint bitfields

```with javascript_semantics -- takes about 47s (of blank screen) though, also note the line
-- below which triggered an unexpected violation on desktop/Phix
-- (the fix/hoist for which meant a need to swap result and tmp)
requires("1.0.1") -- mpz_invert()
include mpfr.e

function coppy(sequence p, integer ab, j)
p = deep_copy(p)
p[ab][j] = 1
p[j] = 0
return p
end function

function erdos_woods(integer n)
integer n1 = n-1
sequence primes = get_primes_le(n1),
divs = repeat(0,n),
trailing_zeros = repeat(0,n1)
integer np = length(primes)
for a=1 to n do
sequence d = {}
for i=np to 1 by -1 do
d &= (remainder(a-1,primes[i])=0)
end for
divs[a] = d
end for
for i=1 to n1 do
trailing_zeros[i] = rfind(1,sq_or(divs[i+1],divs[n-i+1]))
end for
sequence smc = custom_sort(trailing_zeros,tagset(n1)),
partitions = {{repeat(0,np),repeat(0,np),repeat(1,np)}}
for s=1 to length(smc) do
integer i = smc[s]
sequence new_partitions = {},
facts = divs[i+1],
other = divs[n-i+1]
for p=1 to length(partitions) do
sequence partp = partitions[p],
{setA,setB,rPrimes} = partp,
fsa = sq_and(facts,setA),
fob = sq_and(other,setB)
if find(1,fsa) or find(1,fob) then
new_partitions = append(new_partitions,partp)
else
for j=1 to np do
if facts[j] and rPrimes[j] then
new_partitions = append(new_partitions,coppy(partp,1,j))
end if
if other[j] and rPrimes[j] then
new_partitions = append(new_partitions,coppy(partp,2,j))
end if
end for
end if
end for
partitions = new_partitions
end for
mpz result = null
mpz {x,y,tmp} = mpz_inits(3,1)
for p=1 to length(partitions) do
sequence {px,py} = partitions[p]
-- triggers "p2js violation: JavaScript does not support string subscript destructuring"...
--      mpz {x,y,tmp} = mpz_inits(3,1)
mpz_set_si(x,1)
mpz_set_si(y,1)
for i=1 to np do
integer pi = primes[np-i+1]
if px[i] then mpz_mul_si(x,x,pi) end if
if py[i] then mpz_mul_si(y,y,pi) end if
end for
mpz_invert(tmp,x,y)
mpz_mul_si(tmp,tmp,n)
mpz_mod(tmp,tmp,y)
mpz_mul(tmp,tmp,x)
mpz_sub_si(tmp,tmp,n)
if result=null then
result = tmp
tmp = mpz_init()
elsif mpz_cmp(tmp,result)=-1 then
{result,tmp} = {tmp,result}
end if
end for
return result
end function

integer k = 3, count = 0
printf(1,"The first 20 Erdos–Woods numbers and their minimum interval start values are:\n")
while count<20 do
mpz a = erdos_woods(k)
if a then
printf(1,"%3d -> %s\n", {k, mpz_get_str(a)})
count += 1
end if
k += 1
end while
```
Output:
Same as Wren example.

## Python

Original author credit to the Stackexchange website user ovs, who in turn credits user xash.

`""" 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 = 3COUNT = 0print('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 `
Output:
Same as Wren example.

## Wren

### Wren-cli

Library: Wren-big
Library: Wren-fmt
Library: Wren-sort
Library: Wren-trait

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.

`import "./big" for BigIntimport "./fmt" for Conv, Fmtimport "./sort" for Sortimport "./trait" for Indexed var zero = BigInt.zerovar one  = BigInt.onevar 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            var setB = p            var rPrimes = p            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        var py = p        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 = 3var count = 0System.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}`
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
```

### Embedded

Library: Wren-gmp

Takes about 15.4 seconds which is significantly faster than Wren-cli, but still nowhere near as fast as the Python version - a majestic 1.2 seconds!

`import "./gmp" for Mpzimport "./fmt" for Conv, Fmtimport "./sort" for Sortimport "./trait" for Indexed var zero = Mpz.zerovar one  = Mpz.onevar two  = Mpz.two var ew = Fn.new { |n|    var primes = []    var k = 1    var P = Mpz.one    while (k < n) {        if (!P.isDivisibleUi(k)) primes.add(k)        P.mul(k * k)        k = k + 1    }    var divs = []    var np = primes.count    if (np > 0) {        for (a in 0...n) {            var A = Mpz.from(a)            var s = primes.map { |p| Conv.btoi(A % p == 0).toString }.join()[-1..0]            divs.add(Mpz.from(Conv.atoi(s, 2)))        }    }    var partitions = [ [Mpz.zero, Mpz.zero, Mpz.two.pow(np) - one] ]    var key = Fn.new { |x| (divs[x] | divs[n-x]).toString(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            var setB = p            var rPrimes = p            if ((factors & setA) != zero || (otherFactors & setB) != zero) {                newPartitions.add(p)                continue            }            for (se in Indexed.new((factors & rPrimes).toString(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).toString(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.copy()        var py = p.copy()        var x = Mpz.one        var y = Mpz.one        for (p in primes) {            if (px.isOdd) x.mul(p)            if (py.isOdd) y.mul(p)            px.div(2)            py.div(2)        }        var N = Mpz.from(n)        var x2 = x.copy()        var temp = x.modInv(y).mul(N).rem(y).mul(x2).sub(N)        result = result ? Mpz.min(result, temp) : temp    }    return result} var k = 3var count = 0System.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}`
Output:
```Same as Wren-cli version.
```