Wagstaff primes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(Julia implementation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (13 intermediate revisions by 10 users not shown) | |||
Line 81:
9: 31: 715827883
10: 43: 2932031007403
</pre>
=={{header|ALGOL W}}==
As Algol W integers are limited to 32 bits, 64 bit reals are used which can accurately represent integers up to 2^53.
<syntaxhighlight lang="algolw">
begin % find some Wagstaff primes: primes of the form ( 2^p + 1 ) / 3 %
% where p is an odd prime %
integer wCount;
% returns true if d exactly divides v, false otherwise %
logical procedure divides( long real value d, v ) ;
begin
long real q, p10;
q := v / d;
p10 := 1;
while p10 * 10 < q do begin
p10 := p10 * 10
end while_p10_lt_q ;
while p10 >= 1 do begin
while q >= p10 do q := q - p10;
p10 := p10 / 10
end while_p10_ge_1 ;
q = 0
end divides ;
% prints v as a 14 digit integer number %
procedure printI14( long real value v ) ;
begin
integer iv;
long real r;
r := abs( v );
if v < 0 then writeon( s_w := 0, "-" );
iv := truncate( r / 1000000 );
if iv < 1 then begin
writeon( i_w := 8, s_w := 0, " ", truncate( r ) )
end
else begin
string(6) sValue;
writeon( i_w := 8, s_w := 0, iv );
iv := truncate( abs( r ) - ( iv * 1000000.0 ) );
for sPos := 5 step -1 until 0 do begin
sValue( sPos // 1 ) := code( ( iv rem 10 ) + decode( "0" ) );
iv := iv div 10
end for_sPos;
writeon( s_w := 0, sValue )
end if_iv_lt_1__
end printI ;
wCount := 0;
% find the Wagstaff primes using long reals to hold the numbers, which %
% accurately represent integers up to 2^53, so only consider primes < 53 %
for p := 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 do begin
long real w, powerOfTwo;
logical isPrime;
powerOfTwo := 1;
for i := 1 until p do powerOfTwo := powerOfTwo * 2;
w := ( powerOfTwo + 1 ) / 3;
isPrime := not divides( 2, w );
if isPrime then begin
integer f, toNext;
long real f2;
f := 3;
f2 := 9;
toNext := 16;
while isPrime and f2 <= w do begin
isPrime := not divides( f, w );
f := f + 2;
f2 := f2 + toNext;
toNext := toNext + 8
end while_isPrime_and_f2_le_x
end if_isPrime ;
if isPrime then begin
wCount := wCount + 1;
write( i_w := 3, s_w := 0, wCount, ": ", p, " " );
if p >= 32 then printI14( w )
else begin
integer iw;
iw := truncate( w );
writeon( i_w := 14, s_w := 0, iw )
end of_p_ge_32__ ;
if wCount >= 10 then goto done % stop at 10 Wagstaff primes %
end if_isPrime
end for_p ;
done:
end.
</syntaxhighlight>
{{out}}
<pre>
1: 3 3
2: 5 11
3: 7 43
4: 11 683
5: 13 2731
6: 17 43691
7: 19 174763
8: 23 2796203
9: 31 715827883
10: 43 2932031007403
</pre>
Line 92 ⟶ 191:
n: ~"|n|"
s: size n
if s > 20 -> n: ((take n 10)++"...")++drop
n ++ ~" (|s| digits)"
]
Line 248 ⟶ 347:
using big_int = mpz_class;
std::string to_string(const big_int& num, size_t
std::string str = num.get_str();
size_t len = str.size();
if (len >
str += " (";
str += std::to_string(len);
Line 303 ⟶ 402:
24: 5807 - 401849623734300...466686663568043 (1748 digits)
</pre>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">'Craft Basic may only calculate up to 9
let n = 9
let p = 1
do
let p = p + 2
if prime(p) then
let w = (2 ^ p + 1) / 3
if prime(w) then
let c = c + 1
print tab, c, tab, p, tab, w
endif
endif
title p
wait
loop c < n</syntaxhighlight>
{{out}}
<pre>
1 3 3
2 5 11
3 7 43
4 11 683
5 13 2731
6 17 43691
7 19 174763
8 23 2796203
9 31 715827883
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Finds Wagstaff primes up to 2^64, the biggest integer 32-bit Delphi supports.
<syntaxhighlight lang="Delphi">
procedure WagstaffPrimes(Memo: TMemo);
{Finds Wagstaff primes up to 6^64}
var P,B,R: int64;
var Cnt: integer;
begin
{B is int64 to force 64-bit arithmetic}
P:=0; B:=1; Cnt:=0;
Memo.Lines.Add(' #: P (2^P + 1)/3');
while P<64 do
begin
R:=((B shl P) + 1) div 3;
if IsPrime(P) and IsPrime(R) then
begin
Inc(Cnt);
Memo.Lines.Add(Format('%2d: %2d %24.0n',[Cnt,P,R+0.0]));
end;
Inc(P);
end;
end;
</syntaxhighlight>
{{out}}
<pre>
#: P (2^P + 1)/3
1: 3 3
2: 5 11
3: 7 43
4: 11 683
5: 13 2,731
6: 17 43,691
7: 19 174,763
8: 23 2,796,203
9: 31 715,827,883
10: 43 2,932,031,007,403
11: 61 768,614,336,404,564,651
Elapsed Time: 29.504 Sec.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func prime n .
if n mod 2 = 0 and n > 2
return 0
.
i = 3
while i <= sqrt n
if n mod i = 0
return 0
.
i += 2
.
return 1
.
pri = 1
while nwag <> 10
pri += 2
if prime pri = 1
wag = (pow 2 pri + 1) / 3
if prime wag = 1
nwag += 1
print pri & " => " & wag
.
.
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 368 ⟶ 586:
9: 31 => 715,827,883
10: 43 => 2,932,031,007,403</pre>
=={{header|Gambas}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Use "isprime.bas"
Public Sub Main()
Wagstaff(10)
End
Sub Wagstaff(num As Long)
Dim pri As Long = 1
Dim wcount As Long = 0
Dim wag As Long
While wcount < num
pri = pri + 2
If isPrime(pri) Then
wag = (2 ^ pri + 1) / 3
If isPrime(wag) Then
wcount += 1
Print Format$(Str(wcount), "###"); ": "; Format$(Str(pri), "###"); " => "; Int(wag)
End If
End If
Wend
End Sub</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
=={{header|Go}}==
Line 606 ⟶ 855:
23 3539 73796098201..86486497963 1065 digits
24 5807 40184962373..86663568043 1748 digits
</pre>
=={{header|Nim}}==
{{libheader|Nim-Integers}}
<syntaxhighlight lang=Nim>import std/strformat
import integers
func compress(str: string; size: int): string =
if str.len <= 2 * size: str
else: &"{str[0..<size]}...{str[^size..^1]} ({str.len} digits)"
echo "First 24 Wagstaff primes:"
let One = newInteger(1)
var count = 0
var p = 3
while count < 24:
if p.isPrime:
let n = (One shl p + 1) div 3
if n.isPrime:
inc count
echo &"{p:4}: {compress($n, 15)}"
inc p, 2
</syntaxhighlight>
{{out}}
<pre>First 24 Wagstaff primes:
3: 3
5: 11
7: 43
11: 683
13: 2731
17: 43691
19: 174763
23: 2796203
31: 715827883
43: 2932031007403
61: 768614336404564651
79: 201487636602438195784363
101: 845100400152152934331135470251
127: 567137278201564...101238628035243 (38 digits)
167: 623574031927851...838653121833643 (50 digits)
191: 104618362256444...574077339085483 (58 digits)
199: 267823007376498...963798805883563 (60 digits)
313: 556246623937737...099018130434731 (94 digits)
347: 955624423329196...712921903606443 (104 digits)
701: 350675726769891...862167823854251 (211 digits)
1709: 961925272487010...857299070528171 (514 digits)
2617: 208150470990263...847933435947691 (788 digits)
3539: 737960982013072...304686486497963 (1065 digits)
5807: 401849623734300...466686663568043 (1748 digits)
</pre>
Line 886 ⟶ 1,186:
24: 5807 => [1748 digit number]
</pre>
=={{header|Quackery}}==
<code>from</code>, <code>index</code>, <code>incr</code>, and <code>end</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
<code>prime</code> is defined at [[Miller–Rabin primality test#Quackery]].
<syntaxhighlight lang="Quackery"> [ bit 1+ 3 / ] is wagstaff ( n --> n )
[] 3 from
[ 2 incr
index prime while
index wagstaff prime while
index join
dup size 24 = if end ]
10 split swap
witheach
[ dup say "p = " echo
wagstaff
say ", w(p) = " echo cr ]
witheach
[ say "p = " echo cr ]
</syntaxhighlight>
{{out}}
<pre>p = 3, w(p) = 3
p = 5, w(p) = 11
p = 7, w(p) = 43
p = 11, w(p) = 683
p = 13, w(p) = 2731
p = 17, w(p) = 43691
p = 19, w(p) = 174763
p = 23, w(p) = 2796203
p = 31, w(p) = 715827883
p = 43, w(p) = 2932031007403
p = 61
p = 79
p = 101
p = 127
p = 167
p = 191
p = 199
p = 313
p = 347
p = 701
p = 1709
p = 2617
p = 3539
p = 5807</pre>
=={{header|Raku}}==
Line 939 ⟶ 1,289:
29: 14479 (179.87)
^C</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ { } 2
'''WHILE''' OVER SIZE 10 < '''REPEAT'''
NEXTPRIME
2 OVER ^ 1 + 3 /
'''IF''' DUP ISPRIME? '''THEN'''
OVER →STR ":" + SWAP + ROT SWAP + SWAP
'''ELSE''' DROP '''END'''
'''END''' DROP
≫ '<span style="color:blue">WAGSTAFF</span>' STO
{{out}}
<pre>
1: { "3:3" "5:11" "7:43" "11:683" "13:2731" "17:43691" "19:174763" "23:2796203" "31:715827883" "43:2932031007403" }
</pre>
=={{header|Ruby}}==
Line 992 ⟶ 1,358:
Even so, as far as the stretch goal is concerned, takes around 25 seconds to find the next 14 Wagstaff primes but almost 10 minutes to find the next 19 on my machine (Core i7). I gave up after that.
<syntaxhighlight lang="
import "./gmp" for Mpz
import "./fmt" for Fmt
| |||