Smallest power of 6 whose decimal expansion contains n: Difference between revisions

Content added Content deleted
m (→‎{{header|Free Pascal}}: Commatize was a huge time factor)
m (→‎{{header|Free Pascal}}: saving used strings seperate.( 8 digits takes 2,8 GB ) ready for lunch...)
Line 913: Line 913:
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===
Doing long multiplikation like in primorial task.<BR>I used to check every numberstring one after the other on one 6^ n string.Gets really slow on high n<BR>After a closer look into [[Phix|Smallest_power_of_6_whose_decimal_expansion_contains_n#Phix]] I applied a slghtly modified version of Pete.
Doing long multiplikation like in primorial task.<BR>I used to check every numberstring one after the other on one 6^ n string.Gets really slow on high n<BR>After a closer look into [[Phix|Smallest_power_of_6_whose_decimal_expansion_contains_n#Phix]] I applied a slghtly modified version of Pete.
Removed Commatize in string assignment.Saves much time.But converting all afterwards consumes even more.
<syntaxhighlight lang="pascal">program PotOf6;
<syntaxhighlight lang="pascal">program PotOf6;
//First occurence of a numberstring with max decimal DIGTIS digits in 6^n
//First occurence of a numberstring with max decimal DIGTIS digits in 6^n
{$IFDEF FPC}
{$IFDEF FPC}
{$MODE DELPHI} {$Optimization ON,ALL} {$COPERATORS ON}
{$MODE DELPHI} {$Optimization ON,ALL} {$COPERATORS ON}{$CODEALIGN proc=16}
{$ENDIF}
{$ENDIF}
{$IFDEF WINDOWS}
{$IFDEF WINDOWS}
Line 928: Line 927:
//decimal places used by multiplication and for string conversion
//decimal places used by multiplication and for string conversion
calcDigits = 8;
calcDigits = 8;
PowerBase = 6; // don't use 10 ;-)
PowerBase = 6; // don't use 10^n ;-)

// for PowerBase = 2 maxvalues for POT_LIMIT and STRCOUNT
⚫
// DIGITS = 8;decLimit= 100*1000*1000;POT_LIMIT = 114715;STRCOUNT = 83789;
⚫
DIGITS = 7;decLimit= 10*1000*1000;POT_LIMIT = 32804;STRCOUNT = 24960;
⚫
// DIGITS = 6;decLimit= 1000*1000;POT_LIMIT = 9112;STRCOUNT = 7348;
⚫
// DIGITS = 5;decLimit= 100*1000;POT_LIMIT = 2750;STRCOUNT = 2148;
⚫
// DIGITS = 4;decLimit= 10*1000;POT_LIMIT = 809;STRCOUNT = 616;
⚫
// DIGITS = 3;decLimit= 1000;POT_LIMIT = 215;STRCOUNT = 175;
⚫
// DIGITS = 2;decLimit= 100;POT_LIMIT = 66;STRCOUNT = 45;


⚫
// DIGITS = 8;decLimit= 100*1000*1000;POT_LIMIT = 68479;
⚫
DIGITS = 7;decLimit= 10*1000*1000;POT_LIMIT = 21798;
⚫
// DIGITS = 6;decLimit= 1000*1000;POT_LIMIT = 6120;
⚫
// DIGITS = 5;decLimit= 100*1000;POT_LIMIT = 1736;
⚫
// DIGITS = 4;decLimit= 10*1000;POT_LIMIT = 444;
⚫
// DIGITS = 3;decLimit= 1000;POT_LIMIT = 147;
⚫
// DIGITS = 2;decLimit= 100;POT_LIMIT = 46;
type
type
tMulElem = Uint32;
tMulElem = Uint32;
Line 944: Line 945:


tFound = record
tFound = record
foundIndex: Uint32;
foundIndex,
foundStr :Ansistring;
foundStrIdx : Uint32;
end;
end;
var
var
{$ALIGN 32}
{$ALIGN 32}
PotArrN : tPotArrN;
PotArrN : tPotArrN;
{$ALIGN 32}
StrDec4Dgts : array[0..9999] of String[4];
StrDec4Dgts : array[0..9999] of String[4];
⚫
Str_Found : array of tFound;
{$ALIGN 32}
FoundString : array of AnsiString;
CheckedNum : array of boolean;
CheckedNum : array of boolean;
{$ALIGN 32}
⚫
Str_Found : array of tFound;
Pot_N_str : AnsiString;
Pot_N_str : AnsiString;
FirstMissing :NativeInt;
FirstMissing,
FoundIdx :NativeInt;
T0 : INt64;
T0 : INt64;


Line 1,020: Line 1,020:
procedure Init_Mul(number:NativeInt);
procedure Init_Mul(number:NativeInt);
var
var
dgtCount,
MaxMulIdx : NativeInt;
MaxMulIdx : NativeInt;
Begin
Begin
MaxMulIdx := trunc(POT_LIMIT*ln(number)/ln(10)/calcDigits+2);
dgtCount := trunc(POT_LIMIT*ln(number)/ln(10))+1;
MaxMulIdx := dgtCount DIV calcDigits +2;
setlength(PotArrN[0],MaxMulIdx);
setlength(PotArrN[0],MaxMulIdx);
setlength(PotArrN[1],MaxMulIdx);
setlength(PotArrN[1],MaxMulIdx);
PotArrN[0,0] := 1;
PotArrN[0,0] := 1;
setlength(Pot_N_str,dgtCount);
end;
end;


Line 1,086: Line 1,089:
pChecked : pBoolean;
pChecked : pBoolean;
i,k,lmt,num : NativeInt;
i,k,lmt,num : NativeInt;
oneFound : boolean;
begin
begin
pChecked := @CheckedNum[0];
pChecked := @CheckedNum[0];
result := 0;
result := 0;
oneFound := false;
lmt := length(s);
lmt := length(s);
For i := 1 to lmt do
For i := 1 to lmt do
Line 1,098: Line 1,103:
IF (num >= FirstMissing) AND Not(pChecked[num]) then
IF (num >= FirstMissing) AND Not(pChecked[num]) then
begin
begin
//memorize that string commatized
if NOT(oneFound) then
Begin
oneFound := true;
FoundString[FoundIDX] := Commatize(s);
FoundIDX += 1;
⚫
end;
pChecked[num]:= true;
pChecked[num]:= true;
str_Found[num].foundIndex:= pow+1;
with str_Found[num] do
str_Found[num].foundStr:= s;
Begin
foundIndex:= pow+1;
foundStrIdx:= FoundIDX-1;
end;
inc(result);
inc(result);
if num =FirstMissing then
if num =FirstMissing then
repeat
⚫
while str_Found[FirstMissing].foundIndex <> 0 do
inc(FirstMissing);
inc(FirstMissing)
⚫
until str_Found[FirstMissing].foundIndex =0;
end;
end;

inc(k)
inc(k)
until (k>lmt) or (k-i >DIGITS-1);
until (k>lmt) or (k-i >DIGITS-1);
Line 1,113: Line 1,128:


var
var
i,j,toggle,MaxMulIdx,found: Int32;
i,j,k,toggle,MaxMulIdx,found: Int32;
Begin
Begin
T0 := GetTickCount64;
T0 := GetTickCount64;
setlength(Str_Found,decLimit);
setlength(Str_Found,decLimit);
setlength(CheckedNum,decLimit);
setlength(CheckedNum,decLimit);
setlength(FoundString,STRCOUNT);
FirstMissing := 0;
FirstMissing := 0;
FoundIdx := 0;
Init_StrDec4Dgts;
Init_StrDec4Dgts;
Init_Mul(PowerBase);
Init_Mul(PowerBase);
Line 1,126: Line 1,143:
found := 0;
found := 0;
MaxMulIdx := 0;
MaxMulIdx := 0;
k := 0;
For j := 0 to POT_LIMIT do
For j := 0 to POT_LIMIT do
Begin
Begin
// if j MOD 20 = 0 then writeln;
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
inc(found,CheckOneString(Pot_N_str,j));
i := CheckOneString(Pot_N_str,j);
found += i;
if i <> 0 then
k += 1;
MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
toggle := 1-toggle;
toggle := 1-toggle;
Line 1,138: Line 1,160:
break;
break;
end;
end;
if (j and 1023) = 0 then
// if (j and 1023) = 0 then write(#13,j:10,found:10,FirstMissing:10);
write(#13,j:10,found:10,FirstMissing:10);
end;
end;
writeln(#13#10,'Found: ',found,' Time used ',(GetTickCount64-T0)/1000:8:3,' secs');
writeln(#13#10,'Found: ',found,' in ',k,' strings. Time used ',(GetTickCount64-T0)/1000:8:3,' secs');
For i := 0 to 22 do//decLimit-1 do
For i := 0 to 22 do//decLimit-1 do
with Str_Found[i] do
with Str_Found[i] do
writeln(i:10,' ',PowerBase,'^',foundIndex-1:5,' ',Commatize(foundStr):30);
writeln(i:10,' ',PowerBase,'^',foundIndex-1:5,' ',(FoundString[foundStrIdx]):30);
end.
end.</syntaxhighlight>
</syntaxhighlight>
{{out|@TIO.RUN}}
{{out|@TIO.RUN}}
<pre>
<pre>
⚫
Init in 0.062 secs
//only calc power til POT_LIMIT Found: 0 Time used 0.046 secs

//calc and convert String: 0.295 secs
//calc and convert String, generating num without check 1.607 secs
{ IF (num >= FirstMissing) AND Not(pChecked[num]) then
⚫
begin ... end; }
// total run
⚫
Init in 0.118 secs
// Power found first missing
0 1 0
1024 751817 10020
2048 2168981 100017
3072 3733971 100017
4096 5305316 100672
5120 6747391 104835
6144 7922626 575115
7168 8776137 1000007
8192 9336696 1000015
9216 9667898 1000020
10240 9846933 1000088
11264 9935108 1000135
12288 9974783 1000204
13312 9990953 1000204
14336 9997035 1000204
15360 9999102 1000204
16384 9999744 1029358
17408 9999934 1029358
18432 9999978 1029358
19456 9999997 8091358
20480 9999999 8091358
21504 9999999 8091358
Max power 21798 with 16963 digits
Max power 21798 with 16963 digits


Found: 10000000 Time used 8.519 secs
Found: 10000000 in 15889 strings. Time used 8.114 secs

0 6^ 9 10,077,696
0 6^ 9 10,077,696
1 6^ 0 1
1 6^ 0 1
Line 1,205: Line 1,200:
22 6^ 22 131,621,703,842,267,136
22 6^ 22 131,621,703,842,267,136


Real time: 9.091 s User time: 8.545 s Sys. time: 0.402 s CPU share: 98.41 %
Real time: 8.383 s User time: 8.133 s Sys. time: 0.185 s CPU share: 99.23 %
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Smallest_power_of_6_whose_decimal_expansion_contains_n"