Smallest power of 6 whose decimal expansion contains n: Difference between revisions
Smallest power of 6 whose decimal expansion contains n (view source)
Revision as of 10:56, 10 March 2023
, 1 year ago→{{header|Free Pascal}}: saving used strings seperate.( 8 digits takes 2,8 GB ) ready for lunch...
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:
==={{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.
<syntaxhighlight lang="pascal">program PotOf6;
//First occurence of a numberstring with max decimal DIGTIS digits in 6^n
{$IFDEF FPC}
{$MODE DELPHI} {$Optimization ON,ALL} {$COPERATORS ON}{$CODEALIGN proc=16}
{$ENDIF}
{$IFDEF WINDOWS}
Line 928 ⟶ 927:
//decimal places used by multiplication and for string conversion
calcDigits = 8;
PowerBase = 6; // don't use 10^n ;-)
// for PowerBase = 2 maxvalues for POT_LIMIT and STRCOUNT
▲// 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
tMulElem = Uint32;
Line 944 ⟶ 945:
tFound = record
foundIndex
end;
var
{$ALIGN 32}
PotArrN : tPotArrN;
StrDec4Dgts : array[0..9999] of String[4];
Str_Found : array of tFound;▼
FoundString : array of AnsiString;
CheckedNum : array of boolean;
▲ Str_Found : array of tFound;
Pot_N_str : AnsiString;
FirstMissing
FoundIdx :NativeInt;
T0 : INt64;
Line 1,020:
procedure Init_Mul(number:NativeInt);
var
dgtCount,
MaxMulIdx : NativeInt;
Begin
MaxMulIdx := dgtCount DIV calcDigits +2;
setlength(PotArrN[0],MaxMulIdx);
setlength(PotArrN[1],MaxMulIdx);
PotArrN[0,0] := 1;
setlength(Pot_N_str,dgtCount);
end;
Line 1,086 ⟶ 1,089:
pChecked : pBoolean;
i,k,lmt,num : NativeInt;
oneFound : boolean;
begin
pChecked := @CheckedNum[0];
result := 0;
oneFound := false;
lmt := length(s);
For i := 1 to lmt do
Line 1,098 ⟶ 1,103:
IF (num >= FirstMissing) AND Not(pChecked[num]) then
begin
//memorize that string commatized
if NOT(oneFound) then
Begin
oneFound := true;
FoundString[FoundIDX] := Commatize(s);
FoundIDX += 1;
pChecked[num]:= true;
with str_Found[num]
foundIndex:= pow+1;
foundStrIdx:= FoundIDX-1;
end;
inc(result);
if num =FirstMissing then
repeat
while str_Found[FirstMissing].foundIndex <> 0 do▼
inc(FirstMissing)
end;
inc(k)
until (k>lmt) or (k-i >DIGITS-1);
Line 1,113 ⟶ 1,128:
var
i,j,k,toggle,MaxMulIdx,found: Int32;
Begin
T0 := GetTickCount64;
setlength(Str_Found,decLimit);
setlength(CheckedNum,decLimit);
setlength(FoundString,STRCOUNT);
FirstMissing := 0;
FoundIdx := 0;
Init_StrDec4Dgts;
Init_Mul(PowerBase);
Line 1,126 ⟶ 1,143:
found := 0;
MaxMulIdx := 0;
k := 0;
For j := 0 to POT_LIMIT do
Begin
// if j MOD 20 = 0 then writeln;
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
found += i;
if i <> 0 then
k += 1;
MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
toggle := 1-toggle;
Line 1,138 ⟶ 1,160:
break;
end;
// if (j and 1023) = 0 then write(#13,j:10,found:10,FirstMissing:10);
end;
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
with Str_Found[i] do
writeln(i:10,' ',PowerBase,'^',foundIndex-1:5,' ',
end.
{{out|@TIO.RUN}}
<pre>
▲ begin ... end; }
▲Init in 0.118 secs
Max power 21798 with 16963 digits
Found: 10000000 in 15889 strings. Time used 8.
0 6^ 9 10,077,696
1 6^ 0 1
Line 1,205 ⟶ 1,200:
22 6^ 22 131,621,703,842,267,136
Real time:
</pre>
| |||