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

Content added Content deleted
m (→‎{{header|Haskell}}: (preferred find))
m (→‎{{header|Free Pascal}}: using a seperate array for used numbers increases speed. 14 -> 9.1 secs)
Line 914: Line 914:
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, to get down < 10 secs on my 2200G for DIGITS = 7.TIO.RUN is slower.
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, to get down < 10 secs on my 2200G for DIGITS = 7.TIO.RUN is slower.
<syntaxhighlight lang="pascal">program PotOf6;
<syntaxhighlight lang="pascal">program PotOf6;
//First occurence of a numberstring with max 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}
Line 927: 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 ;-)


// DIGITS = 8;POT_LIMIT = 68479;
// DIGITS = 8;decLimit= 100*1000*1000;POT_LIMIT = 68479;
DIGITS = 7;POT_LIMIT = 21798;
DIGITS = 7;decLimit= 10*1000*1000;POT_LIMIT = 21798;
// DIGITS = 6;POT_LIMIT = 6120;
// DIGITS = 6;decLimit= 1000*1000;POT_LIMIT = 6120;
// DIGITS = 5;POT_LIMIT = 1736;
// DIGITS = 5;decLimit= 100*1000;POT_LIMIT = 1736;
// DIGITS = 4;POT_LIMIT = 444;
// DIGITS = 4;decLimit= 10*1000;POT_LIMIT = 444;
// DIGITS = 3;POT_LIMIT = 147;
// DIGITS = 3;decLimit= 1000;POT_LIMIT = 147;
// DIGITS = 2;POT_LIMIT = 46;
// DIGITS = 2;decLimit= 100;POT_LIMIT = 46;
type
type
tMulElem = Uint32;
tMulElem = Uint32;
Line 950: Line 951:
{$ALIGN 32}
{$ALIGN 32}
StrDec4Dgts : array[0..9999] of String[4];
StrDec4Dgts : array[0..9999] of String[4];
{$ALIGN 32}
CheckedNum : array of boolean;
{$ALIGN 32}
{$ALIGN 32}
Str_Found : array of tFound;
Str_Found : array of tFound;
Line 1,024: Line 1,027:
end;
end;


function Mul_6(var Mul1,Mul2:tMul;limit:Uint32):NativeInt;
function Mul_PowerBase(var Mul1,Mul2:tMul;limit:Uint32):NativeInt;
//Mul2 = n*Mul1. n must be < LongWordDec !
//Mul2 = n*Mul1. n must be < LongWordDec !
const
const
Line 1,037: Line 1,040:
result :=0;
result :=0;
repeat
repeat
prod := 6*pM1[result]+Carry;
prod := PowerBase*pM1[result]+Carry;
Carry := prod Div LongWordDec;
Carry := prod Div LongWordDec;
pM2[result] := Prod - Carry*LongWordDec;
pM2[result] := Prod - Carry*LongWordDec;
Line 1,050: Line 1,053:
procedure ConvToStr(var s:Ansistring;const Mul:tMul;i:NativeInt);
procedure ConvToStr(var s:Ansistring;const Mul:tMul;i:NativeInt);
var
var
s8: string[8];
s8: string[calcDigits];
pS : pChar;
pS : pChar;
j,k,d,m : NativeInt;
j,k,d,m : NativeInt;
Line 1,080: Line 1,083:
//if it is still missing in the list
//if it is still missing in the list
var
var
pChecked : pBoolean;
i,k,lmt,num : NativeInt;
i,k,lmt,num : NativeInt;
cs : Ansistring;
begin
begin
pChecked := @CheckedNum[0];
result := 0;
result := 0;
cs := '';
lmt := length(s);
lmt := length(s);
For i := 1 to lmt do
For i := 1 to lmt do
Line 1,092: Line 1,095:
repeat
repeat
num := num*10+ Ord(s[k])-Ord('0');
num := num*10+ Ord(s[k])-Ord('0');
IF (num >= FirstMissing) AND (str_Found[num].foundIndex = 0) then
IF (num >= FirstMissing) AND Not(pChecked[num]) then
begin
begin
⚫
pChecked[num]:= true;
str_Found[num].foundIndex:= pow+1;
str_Found[num].foundIndex:= pow+1;
str_Found[num].foundStr:= s;
// commatize only once. reference counted string
if cs ='' then
cs := Commatize(s);
⚫
str_Found[num].foundStr:= cs;
inc(result);
inc(result);
if num =FirstMissing then
if num =FirstMissing then
Line 1,104: Line 1,105:
inc(FirstMissing);
inc(FirstMissing);
end;
end;

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


var
var
i,j,number,toggle,MaxMulIdx,found,decLimit: Int32;
i,j,toggle,MaxMulIdx,found: Int32;
Begin
Begin
T0 := GetTickCount64;
T0 := GetTickCount64;
number := 6;
decLimit := 1;
For i := 1 to digits do
decLimit *= 10;
setlength(Str_Found,decLimit);
setlength(Str_Found,decLimit);
setlength(CheckedNum,decLimit);
FirstMissing := 0;
FirstMissing := 0;
Init_StrDec4Dgts;
Init_StrDec4Dgts;
Init_Mul(number);
Init_Mul(PowerBase);
writeln('Init in ',(GetTickCount64-T0)/1000:8:3,' secs');

T0 := GetTickCount64;
toggle := 0;
toggle := 0;
found := 0;
found := 0;
Line 1,129: Line 1,129:
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
inc(found,CheckOneString(Pot_N_str,j));
inc(found,CheckOneString(Pot_N_str,j));
MaxMulIdx := Mul_6(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
toggle := 1-toggle;
toggle := 1-toggle;

if FirstMissing = decLimit then
if FirstMissing = decLimit then
Begin
Begin
writeln(#10,'Max power ',j);
writeln(#10,'Max power ',j,' with ',length(Pot_N_str),' digits');
break;
break;
end;
end;
// show me, that the program still runs
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,' 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,' ',number,'^',foundIndex-1:5,' ',foundStr);
writeln(i:10,' ',PowerBase,'^',foundIndex-1:5,' ',Commatize(foundStr):30);
end.</syntaxhighlight>
end.</syntaxhighlight>
{{out}}
{{out|@TIO.RUN}}
<pre>
<pre>
//only calc power til POT_LIMIT Found: 0 Time used 0.046 secs
TIO.RUN output
//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
// Power found first missing
0 1 0
0 1 0
Line 1,172: Line 1,177:
20480 9999999 8091358
20480 9999999 8091358
21504 9999999 8091358
21504 9999999 8091358
Max power 21798
Max power 21798 with 16963 digits


Found: 10000000 Time used 13.717 secs
Found: 10000000 Time used 8.519 secs
0 6^ 9 10,077,696
0 6^ 9 10,077,696
1 6^ 0 1
1 6^ 0 1
2 6^ 3 216
2 6^ 3 216
3 6^ 2 36
3 6^ 2 36
4 6^ 6 46,656
4 6^ 6 46,656
5 6^ 6 46,656
5 6^ 6 46,656
6 6^ 1 6
6 6^ 1 6
7 6^ 5 7,776
7 6^ 5 7,776
8 6^ 12 2,176,782,336
8 6^ 12 2,176,782,336
9 6^ 4 1,296
9 6^ 4 1,296
10 6^ 9 10,077,696
10 6^ 9 10,077,696
11 6^ 16 2,821,109,907,456
11 6^ 16 2,821,109,907,456
12 6^ 4 1,296
12 6^ 4 1,296
13 6^ 13 13,060,694,016
13 6^ 13 13,060,694,016
14 6^ 28 6,140,942,214,464,815,497,216
14 6^ 28 6,140,942,214,464,815,497,216
15 6^ 18 101,559,956,668,416
15 6^ 18 101,559,956,668,416
16 6^ 3 216
16 6^ 3 216
17 6^ 10 60,466,176
17 6^ 10 60,466,176
18 6^ 15 470,184,984,576
18 6^ 15 470,184,984,576
19 6^ 21 21,936,950,640,377,856
19 6^ 21 21,936,950,640,377,856
20 6^ 26 170,581,728,179,578,208,256
20 6^ 26 170,581,728,179,578,208,256
21 6^ 3 216
21 6^ 3 216
22 6^ 22 131,621,703,842,267,136
22 6^ 22 131,621,703,842,267,136


Real time: 14.350 s User time: 13.900 s Sys. time: 0.268 s CPU share: 98.74 %
Real time: 9.091 s User time: 8.545 s Sys. time: 0.402 s CPU share: 98.41 %
</pre>
</pre>


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