Erdős–Woods numbers: Difference between revisions

Content added Content deleted
(→‎{{header|Wren}}: Tidied but no quicker.)
Line 33: Line 33:
=={{header|Julia}}==
=={{header|Julia}}==
{{trans|Python}}
{{trans|Python}}
<lang julia>""" modified from https://codegolf.stackexchange.com/questions/230509/find-the-erd%C5%91s-woods-origin/ """
⚫
<lang julia>""" Returns the smallest value for `a` of the Erdős-Woods number n, or -1 if n is not in the sequence """

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)
function erdős_woods(n)
primes = Int[]
primes = Int[]
P = big"1"
P = BigInt(1)
k = 1
k = 1
while k < n
while k < n
Line 43: Line 49:
k += 1
k += 1
end
end
divs = [evalpoly(big"2", [Int(a % p == 0) for p in primes]) for a in 0:n-1]
divs = [evalpoly(2, [Int(a % p == 0) for p in primes]) for a in 0:n-1]
np = length(primes)
np = length(primes)
partitions = [(big"0", big"0", big"2"^np - 1)]
partitions = [(Int256(0), Int256(0), Int256(2)^np - 1)]
ort(x) = trailing_zeros(divs[x + 1] | divs[n - x + 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))
for i in sort(collect(1:n-1), lt = (b, c) -> ort(b) > ort(c))
new_partitions = Tuple{BigInt, BigInt, BigInt}[]
new_partitions = Tuple{Int256, Int256, Int256}[]
factors = divs[i + 1]
factors = divs[i + 1]
other_factors = divs[n - i + 1]
other_factors = divs[n - i + 1]
Line 57: Line 63:
continue
continue
end
end
for (ix, v) in enumerate(digits(factors & r_primes, base=2))
for (ix, v) in enumerate(reverse(string(factors & r_primes, base=2)))
if v == 1
if v == '1'
w = 1 << (ix - 1)
w = Int256(1) << (ix - 1)
push!(new_partitions, (set_a ⊻ w, set_b, r_primes ⊻ w))
push!(new_partitions, (set_a ⊻ w, set_b, r_primes ⊻ w))
end
end
end
end
for (ix, v) in enumerate(digits(other_factors & r_primes, base=2))
for (ix, v) in enumerate(reverse(string(other_factors & r_primes, base=2)))
if v == 1
if v == '1'
w = 1 << (ix - 1)
w = Int256(1) << (ix - 1)
push!(new_partitions, (set_a, set_b ⊻ w, r_primes ⊻ w))
push!(new_partitions, (set_a, set_b ⊻ w, r_primes ⊻ w))
end
end
Line 72: Line 78:
partitions = new_partitions
partitions = new_partitions
end
end
result = big"-1"
result = Int256(-1)
for (px, py, _) in partitions
for (px, py, _) in partitions
x, y = big"1", big"1"
x, y = Int256(1), Int256(1)
for p in primes
for p in primes
isodd(px) && (x *= p)
isodd(px) && (x *= p)
Line 81: Line 87:
py ÷= 2
py ÷= 2
end
end
newresult = n * invmod(x, y) % y * x - n
newresult = ((n * invmod(x, y)) % y) * x - n
result = result == -1 ? newresult : min(result, newresult)
result = result == -1 ? newresult : min(result, newresult)
end
end
Line 87: Line 93:
end
end


function test_erdős_woods()
function test_erdős_woods(startval=3, endval=116)
arr = fill((0, Int256(-1)), endval - startval + 1)
k, kcount = 16, 0
@Threads.threads for k in startval:endval
⚫
println("The first 20 Erdős–Woods numbers and their minimum interval start values are:")
⚫
arr[k - startval + 1] = (k, erdős_woods(k))
while kcount < 20
end
⚫
a = erdős_woods(k)
if a != -1
ewvalues = filter(x -> last(x) > 0, arr)
⚫
println("The first $(length(ewvalues)) Erdős–Woods numbers and their minimum interval start values are:")
println(lpad(k, 3), " -> $a")
kcount += 1
for (k, a) in ewvalues
end
println(lpad(k, 3), " -> $a")
k += 1
end
end
end
end
Retrieved from "https://rosettacode.org/wiki/Erdős–Woods_numbers"