Prime numbers whose neighboring pairs are tetraprimes: Difference between revisions
Content added Content deleted
(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: | Line 900: | ||
Median gap between those 10551 primes: 660 |
Median gap between those 10551 primes: 660 |
||
Maximum gap between those 10551 primes: 10284</pre> |
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}}== |
=={{header|Phix}}== |