Euclid-Mullin sequence: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→Embedded: Re-jigged to find the first 27 numbers in a reasonable time.) |
m (→{{header|Wren}}: Minor tidy) |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 46:
<pre>
2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471 52662739 23003
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68|but only showing the first 8 elements as Algol W integers are limited to 32-bit.}}
<syntaxhighlight lang="algolw">
begin % 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 %
integer product;
write( "2" );
product := 2;
for i := 2 until 8 do begin
integer nextV, p;
logical found;
nextV := product + 1;
% find the first prime factor of nextV %
p := 3;
found := false;
while p * p <= nextV and not found do begin
found := nextV rem p = 0;
if not found then p := p + 2
end while_p_squared_le_nextV_and_not_found ;
if found then nextV := p;
writeon( i_w := 1, s_w := 0, " ", nextV );
product := product * nextV
end for_i
end.
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
Line 76 ⟶ 107:
}
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
Alternative version.
{{Trans|ALGOL 68}}
<syntaxhighlight lang="awk">
# 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
BEGIN {
printf( "2" );
product = 2;
for( i = 2; i <= 8; i ++ )
{
nextV = product + 1;
# find the first prime factor of nextV
p = 3;
found = 0;
while( p * p <= nextV && ! ( found = nextV % p == 0 ) )
{
p += 2;
}
if( found )
{
nextV = p;
}
printf( " %d", nextV );
product *= nextV
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 143 ⟶ 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 212 ⟶ 299:
six = big.NewInt(6)
ten = big.NewInt(10)
)
Line 248 ⟶ 335:
}
func smallestPrimeFactorWheel(n, max *big.Int) *big.Int {
if n.ProbablyPrime(15) {
return n
Line 279 ⟶ 366:
func smallestPrimeFactor(n *big.Int) *big.Int {
s := smallestPrimeFactorWheel(n, k100)
if s != nil {
return s
Line 285 ⟶ 372:
c := big.NewInt(1)
s = new(big.Int).Set(n)
for
d := pollardRho(n, c)
if d.Cmp(zero) == 0 {
Line 293 ⟶ 380:
c.Add(c, one)
} else {
//
// check whether
s = smallestPrimeFactorWheel(n.Quo(n, d), factor)
if
} else
return factor
}
} else
return factor
}
}
}
}
Line 355 ⟶ 443:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 362 ⟶ 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 424 ⟶ 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 449 ⟶ 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 536 ⟶ 622:
<pre>{2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887}</pre>
Others may be found by adjusting the range of the Do loop but it will take a while.
=={{header|Lua}}==
{{Trans|ALGOL W}}
<syntaxhighlight lang="lua">
-- 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
do
io.write( "2" )
local product = 2
for i = 2, 8 do
local nextV = product + 1
-- find the first prime factor of nextV
local p = 3
local found = false
while p * p <= nextV and not found do
found = nextV % p == 0
if not found then p = p + 2 end
end
if found then nextV = p end
io.write( " ", nextV )
product = product * nextV
end
end
</syntaxhighlight>
{{out}}
<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>
=={{header|MiniScript}}==
{{Trans|Lua}}
<syntaxhighlight lang="miniscript">
// 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
seq = [2]
product = 2
for i in range( 2, 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 then p = p + 2
end while
if found then nextV = p
seq.push( nextV )
product = product * nextV
end for
print seq.join( " ")
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
=={{header|Nim}}==
Line 723 ⟶ 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 772 ⟶ 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 789 ⟶ 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 795 ⟶ 1,070:
var two = BigInt.two
var ten = BigInt.ten
var
var
if (n.isProbablePrime(5)) return n
if (n % 2 == zero) return BigInt.two
Line 838 ⟶ 1,089:
var smallestPrimeFactor = Fn.new { |n|
var s = smallestPrimeFactorWheel.call(n, k100)
if (s) return s
var c = one
var d = BigInt.pollardRho(n, 2, c)
if (d == 0) {
if (c == ten) Fiber.abort("Pollard Rho doesn't appear to be working.")
c = c + one
} else {
//
return s ? BigInt.min(s, factor) : factor
}
}
}
Line 867 ⟶ 1,117:
prod = prod * t
count = count + 1
}
{{out}}
Line 890 ⟶ 1,140:
</pre>
<br>
===Embedded===
{{libheader|Wren-gmp}}
Line 895 ⟶ 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
| |||