Prime numbers whose neighboring pairs are tetraprimes: Difference between revisions
Prime numbers whose neighboring pairs are tetraprimes (view source)
Revision as of 16:43, 26 June 2023
, 11 months ago→{{header|Nim}}: added =={{header|Pascal}}== generating tetraprimes to speed up.Limit 1E9. space for time
(Moved the Nim entry at the right place.) |
(→{{header|Nim}}: added =={{header|Pascal}}== generating tetraprimes to speed up.Limit 1E9. space for time) |
||
Line 900:
Median gap between those 10551 primes: 660
Maximum gap between those 10551 primes: 10284</pre>
=={{header|Pascal}}==
==={{header|Pascal}}===
uses [[Extensible_prime_generator#Pascal|Extensible_prime_generator]]<br>
Generating and bitmarking all tetraprimes up to limit.So no time consuming check has to be done.
<syntaxhighlight lang="pascal">
program TetraPrimes;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$CodeAlign proc=1,loop=1} // for Ryzen 5xxx
{$ENDIF}
{$IFDEF Windows}{$APPTYPE CONSOLE}{$ENDIF}
uses
sysutils,primsieve;
const
cLimit =1000*1000*1000;
MinTriple = 2*3*5;
MInQuad = MinTriple*7;
cBits2pow = 6; // 2^ 6 = 64-Bit
cMask = 1 shl cBits2pow-1;
type
tIdx = 0..1 shl cBits2pow-1;
tSetBits = set of tIdx;
tMyResult = record
mr_Limit,
mr_cnt,
mr_cnt7,
mr_min,
mr_median,
mr_gapsum,
mr_max : Uint32;
mr_dir : boolean;
end;
var
MarkTetraPrimes : array of tSetBits;
MyPrimes : array of Uint32;
GapCnt: array[0..14660 shr 2] of Uint32;
SmallTetraPrimes : array[0..49] of Uint32;
MyResult : tMyResult;
MaxPrime,HighMyPrimes,count : Uint32;
procedure GenerateTetraPrimes(Factor:NativeUint;MinIdx,CountOfFactors:Uint32);
var
fp,
p : NativeUint;
begin
dec(CountOfFactors);
If (CountOfFactors = 0) then
begin
For MinIdx := MinIdx to HighMyPrimes do
begin
fp := Factor * MyPrimes[MinIdx];
if fp > cLimit then
BREAK;
inc(count);
include(MarkTetraPrimes[fp SHR cBits2pow],fp AND cMask);
end;
end
else
For MinIdx := MinIdx to HighMyPrimes-CountOfFactors do
begin
p := MyPrimes[MinIdx];
fp :=p*Factor;
case CountOfFactors of
2 : p *= p;
3 : p *= p*p;
else
end;
if fp*p < cLimit then
GenerateTetraPrimes(fp,MinIdx+1,CountOfFactors);
end;
end;
procedure GetTetraPrimes(Limit:Uint32);
var
l,
p,i : Uint32;
Begin
setlength(MarkTetraPrimes, Limit shr cBits2pow);
//estimate count of primes
if limit < 10 then
setlength(MyPrimes,4)
else
setlength(MyPrimes,round(Limit/(ln(limit)-1.5)));
InitPrime;
L :=Limit DIV MinTriple;
i := 0;
repeat
p := NextPrime;
MyPrimes[i] := p;
inc(i);
until p > l;
HighMyPrimes := i;
repeat
p := NextPrime;
MyPrimes[i] := p;
inc(i);
until p > limit;
setlength(MyPrimes,i-1);
MaxPrime := MyPrimes[HighMyPrimes];
GenerateTetraPrimes(1,0,4);
end;
function TwoInRow(p : NativeUint;dirUp:Boolean = false):boolean;
var
delta : NativeUint;
begin
if (p < minquad) then
EXIT(false);
delta := ORD(DirUp)*2-1;//= +1,-1
if 2*delta+p >cLimit then
EXIT(false);
p += delta;
if (p AND cMask) in MarkTetraPrimes[p SHR cBits2pow] then
begin
p += delta;
if (p AND cMask) in MarkTetraPrimes[p SHR cBits2pow] then
EXIT(true);
end;
EXIT(false);
end;
procedure CheckLimitDirUp(var Res:tMyResult;Limit:NativeUint;dirUp:boolean);
var
p,Last,GapSum,cnt,cnt7 : UInt32;
i,d : Int32;
Begin
FillChar(GapCnt,SizeOf(GapCnt),#0);
Last := 0;
cnt := 0;
cnt7 := 0;
GapSum := 0;
if dirUp then
d := 1
else
d := -1;
for i := 0 to High(myPrimes) do
begin
p := MyPrimes[i];
If p > Limit then
BREAK;
if TwoInRow(p,dirUp) then
Begin
If Last <> 0 then
Begin
Last := (p-Last) shr 2;
GapSum+=Last;
Inc(GapCnt[Last]);
end;
Last := p;
if limit <= 100*1000 then
SmallTetraPrimes[cnt] := p;
inc(cnt);
p += d;
if p MOD 7 = 0 then
inc(cnt7)
else
if (p+d) MOD 7 = 0 then
inc(cnt7);
end;
end;
with res do
begin
mr_limit:= Limit;
mr_cnt := cnt;
mr_cnt7 := cnt7;
mr_dir := dirUp;
end;
If cnt > 1 then
Begin
For i := 0 to High(GapCnt) do
IF GapCnt[i] <> 0 then
begin
res.mr_min := i shl 2;
BREAK;
end;
For i := High(GapCnt) downto 0 do
IF GapCnt[i] <> 0 then
begin
res.mr_max := i shl 2;
BREAK;
end;
//median;
Limit := cnt DIV 2;
p := 0;
For i := 0 to res.mr_max do
Begin
inc(p,GapCnt[i]);
IF p >= Limit then
begin
res.mr_median := i*4;
BREAK;
end;
end;
res.mr_GapSum := GapSum*4;
end;
if limit <= 100*1000 then
writeln;
end;
procedure Out_Res(const res:tMyResult);
const
Direction : array[Boolean]of string =(' preceded ',' followed ');
var
i : integer;
begin
with res do
Begin
writeln('Primes below ',mr_limit,Direction[mr_dir],' by a tetraprime pair:');
if mr_cnt < 50 then
begin
For i := 0 to mr_cnt-1 do
Begin
write(SmallTetraPrimes[i]:7);
if (i+1) MOD 10 = 0 then
writeln;
end;
writeln;
end;
writeln(#9,'Found ',mr_cnt,' such primes of which ',mr_cnt7,' have 7 as a factor of one of the pair');
writeln(#9#9'GapCnt between the primes: min: ',mr_min,
', average: ',mr_GapSum/(mr_cnt-1):0:1,
', median: ',mr_median,
', max: ',mr_max);
end;
end;
procedure CheckLimit(Limit:NativeUint);
const
preceded = false;
followed = true;
var
myResult :TMyResult;
begin
CheckLimitDirUp(myResult,Limit,preceded);
Out_Res(myResult);
CheckLimitDirUp(myResult,Limit,followed);
Out_Res(myResult);
writeln;
end;
var
i : Uint32;
Begin
GetTetraPrimes(cLimit);
GenerateTetraPrimes(1,0,4);
i := 100000;
repeat
CheckLimit(i);
i *= 10
until i >= cLimit;
CheckLimit(cLimit);
end.
</syntaxhighlight>
{{out|@home}}
<pre>Primes below 100000 preceded by a tetraprime pair:
8647 15107 20407 20771 21491 23003 23531 24767 24971 27967
29147 33287 34847 36779 42187 42407 42667 43331 43991 46807
46867 51431 52691 52747 53891 54167 58567 63247 63367 69379
71711 73607 73867 74167 76507 76631 76847 80447 83591 84247
86243 87187 87803 89387 93887 97547 97847 98347 99431
Found 49 such primes of which 31 have 7 as a factor of one of the pair
GapCnt between the primes: min: 56, average: 1891.3, median: 1180, max: 6460
Primes below 100000 followed by a tetraprime pair:
8293 16553 17389 18289 22153 26893 29209 33409 35509 36293
39233 39829 40493 41809 45589 48109 58393 59629 59753 59981
60493 60913 64013 64921 65713 66169 69221 71329 74093 75577
75853 77689 77933 79393 79609 82913 84533 85853 87589 87701
88681 91153 93889 96017 97381 98453
Found 46 such primes of which 36 have 7 as a factor of one of the pair
GapCnt between the primes: min: 112, average: 2003.6, median: 1460, max: 10284
Primes below 1000000 preceded by a tetraprime pair:
Found 885 such primes of which 503 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 1119.5, median: 756, max: 7712
Primes below 1000000 followed by a tetraprime pair:
Found 866 such primes of which 492 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 1146.0, median: 832, max: 10284
Primes below 10000000 preceded by a tetraprime pair:
Found 10815 such primes of which 5176 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 923.9, median: 648, max: 9352
Primes below 10000000 followed by a tetraprime pair:
Found 10551 such primes of which 5069 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 947.0, median: 660, max: 10284
Primes below 100000000 preceded by a tetraprime pair:
Found 110865 such primes of which 47197 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 901.9, median: 632, max: 11892
Primes below 100000000 followed by a tetraprime pair:
Found 110192 such primes of which 47308 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 907.4, median: 640, max: 11000
Primes below 1000000000 preceded by a tetraprime pair:
Found 1081567 such primes of which 423195 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 924.6, median: 648, max: 14660
Primes below 1000000000 followed by a tetraprime pair:
Found 1081501 such primes of which 423572 have 7 as a factor of one of the pair
GapCnt between the primes: min: 4, average: 924.6, median: 648, max: 12100
real 0m10,578s
</pre>
=={{header|Phix}}==
| |||