Erdős–Woods numbers: Difference between revisions
Add Scala implementation
(→{{header|Wren}}: Added an embedded version using Wren-gmp.) |
(Add Scala implementation) |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 33:
=={{header|Julia}}==
{{trans|Python}}
<
using BitIntegers
Line 106:
test_erdős_woods()
</
=={{header|Phix}}==
Line 112:
{{trans|Julia}}
Using flag arrays instead of bigint bitfields
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #000080;font-style:italic;">-- 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)</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 207:
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</
{{out}}Same as Wren example.
=={{header|Python}}==
Original author credit to the Stackexchange website user ovs, who in turn credits user xash.
<
def erdős_woods(n):
Line 274:
COUNT += 1
K += 1
</
=={{header|Raku}}==
{{trans|Wren}}
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20220308 Raku programming solution
sub invmod($n, $modulo) { # rosettacode.org/wiki/Modular_inverse#Raku
my ($c, $d, $uc, $vc, $ud, $vd, $q) = ($n % $modulo, $modulo, 1, 0, 0, 1);
while $c != 0 {
($q, $c, $d) = ($d div $c, $d % $c, $c);
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
}
return $ud % $modulo;
}
sub ew (\n) {
my @primes = (^n).race.grep: *.is-prime;
# rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Raku
my @divs = (^n).map: -> \p { ([o] map { p%%$_.Int + 2 * * }, @primes)(0) }
my @partitions = [ 0, 0, 2**@primes.elems - 1 ] , ;
sub ort(\x) { (@divs[x] +| @divs[n -x]).base(2).flip.index(1) }
for ((n^...1).sort: *.&ort).reverse {
my \newPartitions = @ = ();
my (\factors,\otherFactors) = @divs[$_, n-$_];
for @partitions -> \p {
my (\setA, \setB, \rPrimes) = p[0..2];
if (factors +& setA) or (otherFactors +& setB) {
newPartitions.push: p and next
}
for (factors +& rPrimes).base(2).flip.comb.kv -> \k,\v {
if (v == 1) {
my \w = 1 +< k;
newPartitions.push: [ setA +^ w, setB, rPrimes +^ w ]
}
}
for (otherFactors +& rPrimes).base(2).flip.comb.kv -> \k,\v {
if (v == 1) {
my \w = 1 +< k;
newPartitions.push: [ setA, setB +^ w, rPrimes +^ w ]
}
}
}
@partitions = newPartitions
}
my \result = $ = -1;
for @partitions -> \p {
my ($px,$py) = p[0,1];
my ($x ,$y ) = 1 xx *;
for @primes -> $p {
$px % 2 and $x *= $p;
$py % 2 and $y *= $p;
($px,$py) >>div=>> 2
}
my \newresult = ((n * invmod($x, $y)) % $y) * $x - n;
result = result == -1 ?? newresult !! min(result, newresult)
}
return result
}
say "The first 20 Erdős–Woods numbers and their minimum interval start values are:";
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 281 ⟶ 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.
<
import "./fmt" for Conv, Fmt
import "./sort" for Sort
import "./
var zero = BigInt.zero
Line 375 ⟶ 545:
}
k = k + 1
}</
{{out}}
Line 405 ⟶ 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!
<
import "./fmt" for Conv, Fmt
import "./sort" for Sort
import "./
var zero = Mpz.zero
Line 496 ⟶ 666:
}
k = k + 1
}</
{{out}}
| |||