Multi-base primes: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: added base 62 output)
(→‎{{header|Pascal}}: extended like raku and phix to base 62)
Line 543: Line 543:


=={{header|Pascal}}==
=={{header|Pascal}}==
First counting the bases that convert a decimal string of n into a prime number.<BR>
First counting the bases that convert a MAXBASE string of n into a prime number.<BR>
Afterwards only checking the maxcount for the used bases.<BR>
Afterwards only checking the maxcount for the used bases.<BR>
Most time consuming is sieving for the primes.
Most time consuming is sieving for the primes.
<lang pascal>program DecStringIsPrimeInBase;
<lang pascal>program MAXBaseStringIsPrimeInBase;
//base 10 numeric string
{$IFDEF FPC}
{$IFDEF FPC}
{$MODE DELPHI}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$OPTIMIZATION ON,ALL}
//{$R+,O+}
// {$R+,O+}
{$ELSE}
{$ELSE}
{$APPTYPE CONSOLE}
{$APPTYPE CONSOLE}
Line 559: Line 558:
const
const
MINBASE = 2;
MINBASE = 2;
MAXBASE = 36;//10;//10 is minimum
MAXBASE = 36;//62;
MAXDIGITCOUNT = 6;//9;//
MAXDIGITCOUNT = 6;//5;
MAXFAC = 10*10*10*10*10*10;//10*10*10*10*10*10*10*10*10;//
type
type
tdigits = array [0..15] of byte;//must be 0..15
tdigits = array [0..15] of byte;//must be 0..15
tSol = array of Uint32;
tSol = array of Uint64;
//sieve primes see http://rosettacode.org/wiki/Sieve_of_Eratosthenes#alternative_using_wheel
var
var
BoolPrimes: array of boolean;
BoolPrimes: array of boolean;
//memorize the highest used digit

MaxDgtPos : UInt32;
function BuildWheel(primeLimit:Int32):NativeUint;
function BuildWheel(primeLimit:Int64):NativeUint;
var
var
myPrimes : pBoolean;
myPrimes : pBoolean;
Line 616: Line 614:
end;
end;
until WheelSize >= PrimeLimit;
until WheelSize >= PrimeLimit;

while wpno > 0 do
while wpno > 0 do
begin
begin
Line 626: Line 624:
BuildWheel := pr+1;
BuildWheel := pr+1;
end;
end;

procedure Sieve(PrimeLimit:Int32);
procedure Sieve(PrimeLimit:Uint64);
var
var
myPrimes : pBoolean;
myPrimes : pBoolean;
Line 655: Line 653:
end;
end;


function getDecDigitsAndMaxDgt(n:Uint32;var dgt:tDigits):uint32;
function getDgtsInMAXBASEandMaxDigit(n:Uint64;var dgt:tDigits):uint32;
var
var
pQ :pQWord;
pQ :pQWord;
q,r,i: Uint32;
q,r: Uint64;
i:Int64;
Begin
Begin
pQ := @dgt[0];pQ[0] := 0;pQ[1] := 0;
pQ := @dgt[0];
pQ[0] := 0;pQ[1] := 0;
//aka fillChar(dgt[0],SizeOf(dgt),#0);
//aka fillChar(dgt[0],SizeOf(dgt),#0);

i := 0;
i := 0;
result := 0;
result := 0;
repeat
repeat
q := n DIV 10;
q := n DIV MAXBASE;
r := (n-q*10);
r := (n-q*MAXBASE);
n := q;
dgt[i] := r;
dgt[i] := r;
if result < r then result := r;
inc(i);
inc(i);
if result < r then
n := q;
result := r;
until n = 0;
until n = 0;
MaxDgtPos := i-1;
end;
end;


function CnvtoBase(const dgt:tDigits;base:Uint32):Uint32;
function CnvtoBase(const dgt:tDigits;base:NativeUint;DgtCnt:NativeInt):Uint64;
var
i: Int32;
Begin
Begin
i := MAXDIGITCOUNT;
while (dgt[i] = 0) AND (i>0) do
dec(i);

result := 0;
result := 0;
repeat
repeat
result := base*result+dgt[i];
result := base*result+dgt[DgtCnt];
dec(i);
dec(DgtCnt);
until (i< 0);
until (DgtCnt< 0);
end;
end;


function CntPrimeInBases(n:Uint32):Uint32;
function CntPrimeInBases(n:Uint64;max:Int32):Uint32;
var
var
Digits :tdigits;
Digits :tdigits;
base: Uint32;
pr : Uint64;
base,dgtCnt: Uint32;
begin
begin
//base 10
result := 0;
Base := getDgtsInMAXBASEandMaxDigit(n,Digits)+1;
result := Ord(boolprimes[n]);
IF Digits[0] = 0 then
//minimalBase <= max. digit +1
EXIT;
//this takes 0.012s out of 0.155s
base := getDecDigitsAndMaxDgt(n,Digits)+1;
if base < MinBase then
if base < MinBase then
base := MinBase;
base := MinBase;
// if (MAXBASE - Base) <= (max-result) then BREAK;

max := (max+Base-MAXBASE);
for base := base TO 9 do
if (max>=0) then
inc(result,Ord(boolprimes[CnvtoBase(Digits,base)]));
EXIT;
for base := 11 TO MAXBASE do
dgtCnt := MAXDIGITCOUNT-1;
inc(result,Ord(boolprimes[CnvtoBase(Digits,base)]));
while (dgtCnt>0) AND (Digits[dgtCnt]= 0) do
dec(dgtCnt);
result := Ord(boolprimes[n]);
for base := base TO MAXBASE-1 do
begin
pr := CnvtoBase(Digits,base,MaxDgtPos);
inc(result,Ord(boolprimes[pr]));
//no chance to reach max then exit
if result<=max then
break;
inc(max);
end;
end;
end;


function GetMaxBaseCnt(MinLmt,MaxLmt:Uint32):tSol;
function GetMaxBaseCnt(MinLmt,MaxLmt:Uint32):tSol;
var
var
i,baseCnt,max,Idx: Int32;
i : Uint32;
baseCnt,max,Idx: Int32;
Begin
Begin
setlength(result,0);
setlength(result,0);
Line 718: Line 726:
For i := MinLmt to MaxLmt do
For i := MinLmt to MaxLmt do
Begin
Begin
baseCnt := CntPrimeInBases(i);
baseCnt := CntPrimeInBases(i,max);
if baseCnt = 0 then
if baseCnt = 0 then
continue;
continue;
Line 741: Line 749:
end;
end;


function Out_String(n:Uint32;var s: AnsiString):Uint32;
function Out_String(n:Uint64;var s: AnsiString):Uint32;
//out-sourced for debugging purpose
//out-sourced for debugging purpose
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
var
var
dgt:tDigits;
dgt:tDigits;
sl : string[8];
sl : string[8];
base,minimalbase: Uint32;
base,i: Int32;
Begin
Begin
result := 0;
result := 0;
base:= getDgtsInMAXBASEandMaxDigit(n,dgt)+1;
str(n:7,sl);
sl := '';
i := MaxDgtPos;
while (i>=0)do
Begin
sl += CharOfBase[dgt[i]+1];
dec(i);
end;
s := sl+' -> [';
s := sl+' -> [';

minimalbase:= getDecDigitsAndMaxDgt(n,dgt)+1;
For base := minimalbase to MAXBASE do
For base := base to MAXBASE do
if boolprimes[CnvtoBase(dgt,base)] then
if boolprimes[CnvtoBase(dgt,base,MaxDgtPos)] then
begin
begin
inc(result);
inc(result);
Line 782: Line 799:
var
var
T0 : Int64;
T0 : Int64;
i,lmt,minLmt : Uint32;
lmt,minLmt : UInt32;
i : Uint32;
begin
begin
T0 := GetTickCount64;
T0 := GetTickCount64;
lmt := 0;
lmt := 0;
//maxvalue of "99...99" in Maxbase
//maxvalue in Maxbase
for i := 1 to MAXDIGITCOUNT do
for i := 1 to MAXDIGITCOUNT do
lmt := (lmt*MAXBASE+9);
lmt :=lmt*MAXBASE+MAXBASE-1;
writeln('max prime limit ',lmt);
writeln('max prime limit ',lmt);
Sieve(lmt);
Sieve(lmt);
Line 797: Line 815:
repeat
repeat
write(i:2,' character strings which are prime in count bases = ');
write(i:2,' character strings which are prime in count bases = ');
Out_Sol(GetMaxBaseCnt(minLmt,10*minLmt-1));
Out_Sol(GetMaxBaseCnt(minLmt,MAXBASE*minLmt-1));
minLmt *= 10;
minLmt *= MAXBASE;
inc(i);
inc(i);
until minLmt >= MAXFAC;
until i>MAXDIGITCOUNT;
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
{$IFDEF WINDOWS} readln; {$ENDIF}
{$IFDEF WINDOWS} readln; {$ENDIF}
Line 806: Line 824:
{{out}}
{{out}}
<pre>
<pre>
//at home 2200G 16GB Linux
TIO.RUN// extreme volatile timings for sieving primes:today up to 15.6s
//base = 36 maxcharacters = 6
max prime limit 559744029
max prime limit 2176782335
Prime sieving 2.168 s
Prime sieving 5.003 s
1 character strings which are prime in count bases = 34
1 character strings which are prime in count bases = 34
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]


2 character strings which are prime in count bases = 18
2 character strings which are prime in count bases = 18
21 -> [3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36]
21 -> [3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36]


3 character strings which are prime in count bases = 18
3 character strings which are prime in count bases = 18
131 -> [4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34]
131 -> [4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34]
551 -> [6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36]
551 -> [6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36]
737 -> [8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36]
737 -> [8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36]


4 character strings which are prime in count bases = 19
4 character strings which are prime in count bases = 19
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36]
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36]
5347 -> [8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36]
5347 -> [8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36]


5 character strings which are prime in count bases = 18
5 character strings which are prime in count bases = 18
30271 -> [8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36]
30271 -> [8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36]


6 character strings which are prime in count bases = 18
6 character strings which are prime in count bases = 18
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33]
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33]

Converting 24.313 s
real 0m29,389s
######################
TIO.RUN// extreme volatile timings for sieving primes
Maxbase = 62 maxcharacters = 5
max prime limit 916132831
Prime sieving 14.576 s
1 character strings which are prime in count bases = 60
2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62]

2 character strings which are prime in count bases = 31
65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59]

3 character strings which are prime in count bases = 33
1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62]
B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62]

4 character strings which are prime in count bases = 32
1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61]
417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62]

5 character strings which are prime in count bases = 30
50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62]


Converting 0.333 s
Converting 19.044 s
Real time: 33.929 s User time: 24.091 s Sys. time: 9.093 s CPU share: 97.80 %
//at home
//at home real 0m12,614s user 0m12,336s sys 0m0,238s
//Prime sieving 1.071 s Converting 0.171 s</pre>
</pre>


=={{header|Phix}}==
=={{header|Phix}}==
Retrieved from "https://rosettacode.org/wiki/Multi-base_primes"