Erdős–Woods numbers: Difference between revisions
Add Scala implementation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Add Scala implementation) |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 116:
-- below which triggered an unexpected violation on desktop/Phix
-- (the fix/hoist for which meant a need to swap result and tmp)</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 182:
<span style="color: #008080;">if</span> <span style="color: #000000;">py</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_invert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
Line 345:
for (16..116) { if (my $ew = ew $_) > 0 { printf "%3d -> %d\n",$_,$ew } }</syntaxhighlight>
{{out}}Same as Wren example.
=={{header|Scala}}==
{{trans|Python}}
<syntaxhighlight lang="Scala">
object ErdosWoods {
def erdősWoods(n: Int): BigInt = {
var primes = List[Int]()
var P: BigInt = 1
var k = 1
while (k < n) {
if (P % k != 0) primes = primes :+ k
P *= k * k
k += 1
}
val divs = (0 until n).map { a =>
Integer.parseInt(primes.map(p => if (a % p == 0) "1" else "0").mkString.reverse, 2)
}
val np = primes.length
var partitions = List((0, 0, (1 << np) - 1))
for (i <- (1 until n).sortBy(x => Integer.toBinaryString(divs(x) | divs(n - x)).reverse.indexOf('1')).reverse) {
var newPartitions = List[(Int, Int, Int)]()
val factors = divs(i)
val otherFactors = divs(n - i)
for (p <- partitions) {
val (setA, setB, rPrimes) = p
if ((factors & setA) != 0 || (otherFactors & setB) != 0) {
newPartitions = newPartitions :+ p
} else {
for ((v, ix) <- Integer.toBinaryString(factors & rPrimes).reverse.zipWithIndex if v == '1') {
val w = 1 << ix
newPartitions = newPartitions :+ ((setA ^ w, setB, rPrimes ^ w))
}
for ((v, ix) <- Integer.toBinaryString(otherFactors & rPrimes).reverse.zipWithIndex if v == '1') {
val w = 1 << ix
newPartitions = newPartitions :+ ((setA, setB ^ w, rPrimes ^ w))
}
}
}
partitions = newPartitions
}
partitions.foldLeft(BigInt("1000000000000")) { (result, p) =>
val (px, py, _) = p
var x: BigInt = 1
var y: BigInt = 1
var pxVar = px
var pyVar = py
for (p <- primes) {
if (pxVar % 2 == 1) x *= p
if (pyVar % 2 == 1) y *= p
pxVar /= 2
pyVar /= 2
}
result.min(n * (x.modInverse(y)) % y * x - n)
}
}
def main(args: Array[String]): Unit = {
var K = 3
var count = 0
println("The first 20 Erdős–Woods numbers and their minimum interval start values are:")
while (count < 20) {
val a = erdősWoods(K)
if (a != BigInt("1000000000000")) {
println(f"$K%3d -> $a")
count += 1
}
K += 1
}
}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
Line 351 ⟶ 451:
{{libheader|Wren-fmt}}
{{libheader|Wren-sort}}
{{libheader|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) [https://codegolf.stackexchange.com/questions/230509/find-the-erd%C5%91s-woods-origin 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.
<syntaxhighlight lang="
import "./fmt" for Conv, Fmt
import "./sort" for Sort
import "./
var zero = BigInt.zero
Line 475 ⟶ 575:
{{libheader|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!
<syntaxhighlight lang="
import "./fmt" for Conv, Fmt
import "./sort" for Sort
import "./
var zero = Mpz.zero
| |||