Rosetta Code

Smallest numbers: Difference between revisions

Page Discussion

Smallest numbers (view source)

Revision as of 08:22, 13 April 2021

1,618 bytes added ,  3 years ago
→‎{{header|Pascal}}: remove unused parts added GMP-version
m (→‎{{header|Julia}}: string version)
(→‎{{header|Pascal}}: remove unused parts added GMP-version)
Line 80:
made like Phix but own multiplikation to BASE 1E9 [[Smallest_power_of_6_whose_decimal_expansion_contains_n#Pascal|here]]
<lang pascal>program K_pow_K;
//First occurence of a numberstring with max DIGTIS digits in 6k^nk
{$IFDEF FPC}
{$MODE DELPHI}
Line 92:
const
LongWordDec = 1000*1000*1000;
Digits = 6;
 
POT_LIMIT = 10;
Digits = 7;
 
type
Line 100 ⟶ 98:
tMul = array of tMulElem;
tpMul = pUint32;
tPotArrN = array[0..1] of tMul;
 
tFound = Uint32;
var
PotArrN : tPotArrN;
Pot_N_str : AnsiString;
Str_Found : array of tFound;
Line 110 ⟶ 105:
T0 : INt64;
 
procedure Init_MulOut_Results(number,found:NativeInt);
var
MaxMulIdxi : NativeInt;
Begin
writeln;
MaxMulIdx := trunc(POT_LIMIT*ln(POT_LIMIT)/ln(10)/9+2);
writeln(#10,'Found: ',found,' at ',number,' with ',length(Pot_N_str),
setlength(PotArrN[0],MaxMulIdx);
' digits in Time used ',(GetTickCount64-T0)/1000:8:3,' secs');
setlength(PotArrN[1],MaxMulIdx);
writeln ;
PotArrN[0,0] := 1;
writeln(' 0 1 2 3 4 5 6 7 8 9');
writeln(MaxMulIdx);
write(' |__________________________________________________');
end;
For i := 0 to 99 do//decLimit-1 do
 
begin
procedure SquareMul(var Mul1,Mul2:tMul);
if i MOD 10 = 0 then
//Mul2 = MUl1*Mul1
var
prod,carry: Uint64;
i,j,lmt,n : NativeInt;
Begin
lmt := length(Mul1);
setlength(Mul2,2*lmt+1);
FillDword(Mul2[0],2*lmt+1,0);
lmt -= 1;
For i := 0 to lmt do
Begin
carry := 0;
n := Mul1[i];
For j := 0 to Lmt do
Begin
writeln;
prod := n*Mul1[j]+Mul2[i+j]+carry;
carry := prodwrite((i DIV LongWordDec10)*10:10,'|');
Mul2[i+j]:=prod-carry*LongWordDec;
end;
number := Str_Found[i]-1;
// If carry<>0 then
if number Mul2[i+lmt+1]> :=0 carry;then
write(number:5);
end;
writeln;
i := High(Mul2);
while (i>=1) AND (Mul2[i]=0) do
dec(i);
setlength(Mul2,i+1);
end;
 
Line 179 ⟶ 158:
dec(i);
setlength(Mul2,i+1);
end;
 
function Commatize(const s: AnsiString):AnsiString;
var
fromIdx,toIdx :Int32;
Begin
result := '';
fromIdx := length(s);
toIdx := fromIdx-1;
if toIdx < 3 then
Begin
result := s;
exit;
end;
toIdx := 4*(toIdx DIV 3)+toIdx MOD 3;
inc(toIdx);
setlength(result,toIdx);
repeat
result[toIdx] := s[FromIdx];
result[toIdx-1] := s[FromIdx-1];
result[toIdx-2] := s[FromIdx-2];
result[toIdx-3] := ',';
dec(toIdx,4);
dec(FromIdx,3);
until FromIdx<=3;
while fromIdx>=1 do
Begin
result[toIdx] := s[FromIdx];
dec(toIdx);
dec(fromIdx);
end;
end;
 
Line 272 ⟶ 220:
 
var
MulErg,Square :tMUl;
number,i,j,number,toggle,found,decLimit: Int32;
Begin
T0 := GetTickCount64;
Line 287 ⟶ 235:
setlength(MulErg,1);
MulErg[0] := 1;
setlength(PotArrN[0]Square,1);
setlength(PotArrNSquare[10],1):= number;
PotArrN[0,0]:= number;
PotArrN[1,0]:= 1;
toggle := 0;
 
If number AND 1 <> 0 then
MulErg[0] := PotArrN[toggle]number;
j := 2;
while j <= number do
Begin
Mul_12(Square,Square);
SquareMul(PotArrN[toggle],PotArrN[1-toggle]);
toggle := 1-toggle;
If number AND J <> 0 then
Mul_12(PotArrN[toggle]Square,MulErg);
j:= j*2;
end;
Line 309 ⟶ 253:
if number AND 511 = 0 then
write(#13,number:7,' with ',length(Pot_N_str), ' digits.Found ',found);
until found >=decLimit;
Out_Results(number,found);
end.
</lang>
{{out}}
<pre>
TIO.RUN for 6 Digits
 
512 with 1385 digits.Found 334811
1024 with 3080 digits.Found 777542
1536 with 4891 digits.Found 968756
2048 with 6778 digits.Found 998285
2560 with 8722 digits.Found 999959
3072 with 10710 digits.Found 999999
 
Found: 1000000 at 3173 with 11107 digits in Time used 2.719 secs
 
0 1 2 3 4 5 6 7 8 9
|__________________________________________________
0| 9 1 3 5 2 4 4 3 7 9
10| 10 11 5 19 22 26 8 17 16 19
20| 9 8 13 7 17 4 17 3 11 18
30| 13 5 23 17 18 7 17 15 9 18
40| 16 17 9 7 12 28 6 23 9 24
50| 23 13 18 11 7 14 4 18 14 13
60| 19 11 25 17 17 6 6 8 14 27
70| 11 26 8 16 9 13 17 8 15 19
80| 14 21 7 21 16 11 17 9 17 9
90| 15 12 13 15 27 16 18 19 21 23
 
Found: 1000000 at 3173 with 11107 digits in Time used 2.785 secs
 
... at home for 7 Digits
only calc k^k for 1..9604
Found: 0 at 9604 with 0 digits in Time used 45.700 secs
with ConvToStr
Found: 0 at 9604 with 38244 digits in Time used 46.406 secs
with ConvToStr and CheckOneString
Found: 10000000 at 9604 with 38244 digits in Time used 52.222 secs
9216 with 36533 digits.Found 9999997
</pre>
===gmp-version===
<lang pascal>program K_pow_K_gmp;
//First occurence of a numberstring with max DIGTIS digits in k^k
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
 
uses
sysutils,gmp;
const
LongWordDec = 1000*1000*1000;
 
Digits = 7;
 
var
Pot_N_str : AnsiString;
Str_Found : array of Uint32;
FirstMissing :NativeInt;
T0 : INt64;
 
procedure Out_Results(number,found:NativeInt);
var
i : NativeInt;
Begin
writeln;
writeln(#10,'Found: ',found,' at ',number,' with ',length(pChar(Pot_N_str)),
' digits in Time used ',(GetTickCount64-T0)/1000:8:3,' secs');
writeln ;
writeln(' 0 1 2 3 4 5 6 7 8 9');
write(' |__________________________________________________');
 
write(0:10);
j := 1;
For i := 0 to 99 do//decLimit-1 do
begin
numberif i MOD 10 := Str_Found[i]-1;0 then
if number > 0 then
write(number:5);
if (i+1) MOD 10 = 0 then
Begin
writeln;
write(((i+1) DIV 10)*10:10,'|');
end;
number := Str_Found[i]-1;
if number > 0 then
write(number:5);
end;
writeln;
end.</lang>;
{{out}}
<pre>
TIO.RUN
512 with 1385 digits.Found 334811
1024 with 3080 digits.Found 777542
1536 with 4891 digits.Found 968756
2048 with 6778 digits.Found 998285
2560 with 8722 digits.Found 999959
3072 with 10710 digits.Found 999999
 
function CheckOneString(const s:Ansistring;lmt,pow:NativeInt):NativeInt;
Found: 1000000 at 3173 with 11107 digits in Time used 2.785 secs
//check every possible number from one to DIGITS digits
var
i,k,num : NativeInt;
begin
result := 0;
 
For i := 1 to lmt do
0 1 2 3 4 5 6 7 8 9
Begin
0 9 1 3 5 2 4 4 3 7 9
k := i;
10 10 11 5 19 22 26 8 17 16 19
num := 0;
20 9 8 13 7 17 4 17 3 11 18
repeat
30 13 5 23 17 18 7 17 15 9 18
num := num*10+ Ord(s[k])-Ord('0');
40 16 17 9 7 12 28 6 23 9 24
IF (num >= FirstMissing) AND (str_Found[num] = 0) then
50 23 13 18 11 7 14 4 18 14 13
begin
60 19 11 25 17 17 6 6 8 14 27
str_Found[num]:= pow+1;
70 11 26 8 16 9 13 17 8 15 19
inc(result);
80 14 21 7 21 16 11 17 9 17 9
if num =FirstMissing then
90 15 12 13 15 27 16 18 19 21 23
100 Begin
while str_Found[FirstMissing] <> 0 do
... at home
inc(FirstMissing);
9216 with 36533 digits.Found 9999997
end;
end;
inc(k)
until (k>lmt) or (k-i >DIGITS-1);
end;
end;
 
 
Found: 10000000 at 9604 with 38244 digits in Time used 52.662 secs
var
zkk: mpz_t;
number,i,found,lenS,decLimit: Int32;
Begin
T0 := GetTickCount64;
mpz_init(zkk);
 
decLimit := 1;
For i := 1 to digits do
decLimit *= 10;
setlength(Str_Found,decLimit);
 
//calc digits for max number := 10000
number:= 10000;
i := trunc(number*ln(number)/ln(10))+5;
setlength(Pot_N_str,i);
 
found := 0;
FirstMissing := 0;
number := 1;
lenS :=1;
repeat
mpz_ui_pow_ui(zkk,number,number);
mpz_get_str(pChar(Pot_N_str),10,zkk);
while Pot_N_str[lenS] <> #0 do inc(lenS);
// lenS := length(pChar(Pot_N_str));
inc(found,CheckOneString(Pot_N_str,lenS,number));
inc(number);
if number AND 511 = 0 then
write(#13,number:7,' with ',lenS, ' digits.Found ',found);
until number>9604;// found >=decLimit;
Out_Results(number,found);
end.</lang>
{{out}}
<pre>
TIO.RUN for 7 digits same as above
512 with 1386 digits.Found 608645
1024 with 3081 digits.Found 1952296
...
Found: 10000000 at 9604 with 38244 digits in Time used 13.538 secs
//only mpz_ui_pow_ui(zkk,number,number); takes <0.5s up to 9604 with string conversion 3.3s
</pre>
 
=={{header|Perl}}==
<lang perl>use strict;
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/311380"