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 |
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 |
<lang pascal>program MAXBaseStringIsPrimeInBase; |
||
//base 10 numeric string |
|||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
{$OPTIMIZATION ON,ALL} |
{$OPTIMIZATION ON,ALL} |
||
// {$R+,O+} |
|||
{$ELSE} |
{$ELSE} |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 559: | Line 558: | ||
const |
const |
||
MINBASE = 2; |
MINBASE = 2; |
||
MAXBASE = 36;// |
MAXBASE = 36;//62; |
||
MAXDIGITCOUNT = 6;// |
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 |
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: |
procedure Sieve(PrimeLimit:Uint64); |
||
var |
var |
||
myPrimes : pBoolean; |
myPrimes : pBoolean; |
||
Line 655: | Line 653: | ||
end; |
end; |
||
function |
function getDgtsInMAXBASEandMaxDigit(n:Uint64;var dgt:tDigits):uint32; |
||
var |
var |
||
pQ :pQWord; |
pQ :pQWord; |
||
q,r |
q,r: Uint64; |
||
i:Int64; |
|||
Begin |
Begin |
||
pQ := @dgt[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 |
q := n DIV MAXBASE; |
||
r := (n-q* |
r := (n-q*MAXBASE); |
||
n := q; |
|||
dgt[i] := r; |
dgt[i] := r; |
||
if result < r then result := r; |
|||
inc(i); |
inc(i); |
||
n := q; |
|||
result := r; |
|||
until n = 0; |
until n = 0; |
||
MaxDgtPos := i-1; |
|||
end; |
end; |
||
function CnvtoBase(const dgt:tDigits;base: |
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[ |
result := base*result+dgt[DgtCnt]; |
||
dec( |
dec(DgtCnt); |
||
until ( |
until (DgtCnt< 0); |
||
end; |
end; |
||
function CntPrimeInBases(n: |
function CntPrimeInBases(n:Uint64;max:Int32):Uint32; |
||
var |
var |
||
Digits :tdigits; |
Digits :tdigits; |
||
pr : Uint64; |
|||
base,dgtCnt: Uint32; |
|||
begin |
begin |
||
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 |
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: |
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, |
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 := |
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; |
||
lmt,minLmt : UInt32; |
|||
i : Uint32; |
|||
begin |
begin |
||
T0 := GetTickCount64; |
T0 := GetTickCount64; |
||
lmt := 0; |
lmt := 0; |
||
//maxvalue |
//maxvalue in Maxbase |
||
for i := 1 to MAXDIGITCOUNT do |
for i := 1 to MAXDIGITCOUNT do |
||
lmt := |
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, |
Out_Sol(GetMaxBaseCnt(minLmt,MAXBASE*minLmt-1)); |
||
minLmt *= |
minLmt *= MAXBASE; |
||
inc(i); |
inc(i); |
||
until |
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 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] |
|||
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] |
|||
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] |
|||
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] |
|||
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] |
|||
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] |
|||
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 |
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}}== |