Erdős–Woods numbers: Difference between revisions
julia example
m (→{{header|Python}}: docs) |
(julia example) |
||
Line 30:
<br><br>
=={{header|Julia}}==
{{trans|Python}}
<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>{{out}} Same as Wren example.
=={{header|Python}}==
| |||