Euclid-Mullin sequence: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added Miniscript) |
m (→{{header|Wren}}: Minor tidy) |
||
| (7 intermediate revisions by 6 users not shown) | |||
Line 208:
loop
next i</syntaxhighlight>
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight>
limit = 8
arr[] = [ 2 ]
write 2 & " "
for i = 2 to limit
k = 3
repeat
em = 1
for j = 1 to i - 1
em = em * arr[j] mod k
.
em = (em + 1) mod k
until em = 0
k += 2
.
arr[] &= k
write k & " "
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 421 ⟶ 443:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 428 ⟶ 449:
import java.util.concurrent.ThreadLocalRandom;
public final class
public static void main(String[] aArgs) {
primes = listPrimesUpTo(1_000_000);
System.out.println("The first 27 terms of the
System.out.print(2 + " ");
for ( int i = 1; i < 27; i++ ) {
System.out.print(String.format("%s%s",
}
}
private static BigInteger
BigInteger smallestPrime = smallestPrimeFactor(product.add(BigInteger.ONE));
product = product.multiply(smallestPrime);
Line 490 ⟶ 511:
sieve.set(2, aLimit + 1);
for ( int i = 2; i * i <= aLimit; i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aLimit; j = j + i ) {
sieve.clear(j);
Line 515 ⟶ 535:
{{ out }}
<pre>
The first 27 terms of the
2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471 52662739
23003 30693651606209 37 1741 1313797957 887 71 7127 109 23 97 159227
Line 630 ⟶ 650:
<pre>
2 3 7 43 13 53 5 6221671
</pre>
Alternative using Pollard's Rho algorithm. Uses the iterative gcd function from the [[Greatest common divisor]] task.<br>
{{Trans|Ruby|for the Pollard's Rho algorithm}}.
Note that, as discussed on the Talk page, Pollard's Rho algorithm won't necessarily find the lowest factor, however it does for the first 16 elements.<br>
As with the other Lua sample, only 8 elements are found due to the size of some of the subsequent ones.
<syntaxhighlight lang="lua">
function gcd(a,b)
while b~=0 do
a,b=b,a%b
end
return math.abs(a)
end
function pollard_rho(n)
local x, y, d = 2, 2, 1
local g = function(x) return (x*x+1) % n end
while d == 1 do
x = g(x)
y = g(g(y))
d = gcd(math.abs(x-y),n)
end
if d == n then return d end
return math.min(d, math.floor( n/d ) )
end
local ar, product = {2}, 2
repeat
ar[ #ar + 1 ] = pollard_rho( product + 1 )
product = product * ar[ #ar ]
until #ar >= 8
print( table.concat(ar, " ") )
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
euclid_mullin(n):=if n=1 then 2 else ifactors(1+product(euclid_mullin(i),i,1,n-1))[1][1]$
/* Test case */
makelist(euclid_mullin(k),k,16);
</syntaxhighlight>
{{out}}
<pre>
[2,3,7,43,13,53,5,6221671,38709183810571,139,2801,11,17,5471,52662739,23003]
</pre>
Line 846 ⟶ 913:
{{out}}
<pre>First sixteen: 2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471 52662739 23003</pre>
=={{header|Ring}}==
{{Trans|Lua}}
<syntaxhighlight lang="ring">
// find elements of the Euclid-Mullin sequence: starting from 2,
// the next element is the smallest prime factor of 1 + the product
// of the previous elements
see "2"
product = 2
for i = 2 to 8
nextV = product + 1
// find the first prime factor of nextV
p = 3
found = false
while p * p <= nextV and not found
found = ( nextV % p ) = 0
if not found p = p + 2 ok
end
if found nextV = p ok
see " " + nextV
product = product * nextV
next
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
=={{header|RPL}}==
Line 895 ⟶ 989:
1: { # 2d # 3d # 7d # 43d # 13d # 53d # 5d # 6221671d }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def pollard_rho(n)
x, y, d = 2, 2, 1
g = proc{|x|(x*x+1) % n}
while d == 1 do
x = g[x]
y = g[g[y]]
d = (x-y).abs.gcd(n)
end
return d if d == n
[d, n/d].compact.min
end
ar = [2]
ar << pollard_rho(ar.inject(&:*)+1) until ar.size >= 16
puts ar.join(", ")
</syntaxhighlight>
{{out}}
<pre>2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program euclid_mullin;
print(2);
product := 2;
loop for i in [2..16] do
next := smallest_factor(product + 1);
product *:= next;
print(next);
end loop;
op smallest_factor(n);
if even n then return 2; end if;
d := 3;
loop while d*d <= n do
if n mod d=0 then return d; end if;
d +:= 2;
end loop;
return n;
end op;
end program;</syntaxhighlight>
{{out}}
<pre>2
3
7
43
13
53
5
6221671
38709183810571
139
2801
11
17
5471
52662739
23003</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func f(n) is cached {
Line 912 ⟶ 1,064:
===Wren-cli===
This uses the [https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm Pollard Rho algorithm] to try and speed up the factorization of the 15th element but overall time still slow at around 32 seconds.
<syntaxhighlight lang="
var zero = BigInt.zero
Line 994 ⟶ 1,146:
If we could assume that Pollard's Rho will always find the smallest prime factor (or a multiple thereof) first, then this would bring the runtime down to 44 seconds and still produce the correct answers for this particular task. However, in general it is not safe to assume that - see discussion in Talk Page.
<syntaxhighlight lang="
import "./gmp" for Mpz
| |||