Rosetta Code

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

Page Discussion

Smallest power of 6 whose decimal expansion contains n (view source)

Revision as of 12:36, 6 February 2024

5,478 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Haskell}}: (preferred find))
m (→‎{{header|Wren}}: Minor tidy)
(10 intermediate revisions by 4 users not shown)
Line 912:
=={{header|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, to get down < 10 secs on my 2200G for DIGITS = 7.TIO.RUN is slower.
<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 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 = 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;POT_LIMIT = 68479;
DIGITS = 7;POT_LIMIT = 21798;
// DIGITS = 6;POT_LIMIT = 6120;
// DIGITS = 5;POT_LIMIT = 1736;
// DIGITS = 4;POT_LIMIT = 444;
// DIGITS = 3;POT_LIMIT = 147;
// DIGITS = 2;POT_LIMIT = 46;
type
tMulElem = Uint32;
Line 942 ⟶ 945:
 
tFound = record
foundIndex: Uint32;,
foundStrfoundStrIdx :Ansistring Uint32;
end;
var
{$ALIGN 32}
PotArrN : tPotArrN;
{$ALIGN 32}
StrDec4Dgts : array[0..9999] of String[4];
{$ALIGN 32}
Str_Found : array of tFound;
FoundString : array of AnsiString;
CheckedNum : array of boolean;
Pot_N_str : AnsiString;
FirstMissing :NativeInt;,
FoundIdx :NativeInt;
T0 : INt64;
 
Line 1,016 ⟶ 1,020:
procedure Init_Mul(number:NativeInt);
var
dgtCount,
MaxMulIdx : NativeInt;
Begin
MaxMulIdxdgtCount := trunc(POT_LIMIT*ln(number)/ln(10)/calcDigits)+2)1;
MaxMulIdx := dgtCount DIV calcDigits +2;
setlength(PotArrN[0],MaxMulIdx);
setlength(PotArrN[1],MaxMulIdx);
PotArrN[0,0] := 1;
setlength(Pot_N_str,dgtCount);
end;
 
function Mul_6Mul_PowerBase(var Mul1,Mul2:tMul;limit:Uint32):NativeInt;
//Mul2 = n*Mul1. n must be < LongWordDec !
const
Line 1,037 ⟶ 1,044:
result :=0;
repeat
prod := 6PowerBase*pM1[result]+Carry;
Carry := prod Div LongWordDec;
pM2[result] := Prod - Carry*LongWordDec;
Line 1,050 ⟶ 1,057:
procedure ConvToStr(var s:Ansistring;const Mul:tMul;i:NativeInt);
var
s8: string[8calcDigits];
pS : pChar;
j,k,d,m : NativeInt;
Line 1,080 ⟶ 1,087:
//if it is still missing in the list
var
pChecked : pBoolean;
i,k,lmt,num : NativeInt;
csoneFound : Ansistringboolean;
begin
pChecked := @CheckedNum[0];
result := 0;
csoneFound := ''false;
lmt := length(s);
For i := 1 to lmt do
Line 1,092 ⟶ 1,101:
repeat
num := num*10+ Ord(s[k])-Ord('0');
IF (num >= FirstMissing) AND Not(str_FoundpChecked[num].foundIndex = 0) then
begin
//memorize that string commatized
str_Found[num].foundIndex:= pow+1;
if NOT(oneFound) then
// commatize only once. reference counted string
if cs ='' thenBegin
csoneFound := Commatize(s)true;
str_Found FoundString[numFoundIDX].foundStr := csCommatize(s);
FoundIDX += 1;
end;
pChecked[num]:= true;
with str_Found[num] do
Begin
foundIndex:= pow+1;
foundStrIdx:= FoundIDX-1;
end;
inc(result);
if num =FirstMissing then
repeat
while str_Found[FirstMissing].foundIndex <> 0 do
inc(FirstMissing);
until str_Found[FirstMissing].foundIndex =0;
end;
inc(k)
Line 1,110 ⟶ 1,128:
 
var
i,j,numberk,toggle,MaxMulIdx,found,decLimit: Int32;
Begin
T0 := GetTickCount64;
number := 6;
decLimit := 1;
For i := 1 to digits do
decLimit *= 10;
setlength(Str_Found,decLimit);
setlength(CheckedNum,decLimit);
setlength(FoundString,STRCOUNT);
FirstMissing := 0;
FoundIdx := 0;
Init_StrDec4Dgts;
Init_Mul(numberPowerBase);
writeln('Init in ',(GetTickCount64-T0)/1000:8:3,' secs');
 
T0 := GetTickCount64;
toggle := 0;
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);
inc(found,i := CheckOneString(Pot_N_str,j));
found += i;
MaxMulIdx := Mul_6(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
if i <> 0 then
k += 1;
MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx);
toggle := 1-toggle;
 
if FirstMissing = decLimit then
Begin
writeln(#10,'Max power ',j,' with ',length(Pot_N_str),' digits');
break;
end;
// if (j and 1023) = 0 then write(#13,j:10,found:10,FirstMissing:10);
// show me, that the program still runs
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');
 
writeln(#13#10,'Found: ',found,' 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,' ',numberPowerBase,'^',foundIndex-1:5,' ',foundStr(FoundString[foundStrIdx]):30);
end.
end.</syntaxhighlight>
</syntaxhighlight>
{{out}}
{{out|@TIO.RUN}}
<pre>
Init in 0.062 secs
TIO.RUN output
 
// Power found first missing
Max power 21798 with 16963 digits
0 1 0
 
1024 751817 10020
Found: 10000000 in 15889 strings. Time used 8.114 secs
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
 
0 6^ 9 10,077,696
Found: 10000000 Time used 13.717 secs
01 6^ 90 10,077,6961
12 6^ 03 1 216
23 6^ 32 21636
34 6^ 26 3646,656
45 6^ 6 46,656
56 6^ 61 46,656 6
67 6^ 15 6 7,776
78 6^ 12 5 7 2,176,782,776336
89 6^ 12 2,176,7824 1,336296
910 6^ 49 1 10,077,296696
1011 6^ 16 9 10 2,821,109,077907,696456
1112 6^ 16 2,821,109,9074 1,456296
1213 6^ 13 4 1 13,060,694,296016
1314 6^ 1328 13 6,140,942,214,464,060815,694497,016216
1415 6^ 2818 6,140,942,214 101,464559,815956,497668,216416
1516 6^ 18 101,559,956,668,4163 216
1617 6^ 10 3 216 60,466,176
1718 6^ 1015 60 470,184,466984,176576
1819 6^ 1521 470 21,936,950,184640,984377,576856
1920 6^ 2126 21 170,581,936728,950179,640578,377208,856256
2021 6^ 26 170,581,728,179,578,208,2563 216
2122 6^ 22 3 216 131,621,703,842,267,136
22 6^ 22 131,621,703,842,267,136
 
Real time: 148.350383 s User time: 138.900133 s Sys. time: 0.268185 s CPU share: 9899.7423 %
</pre>
 
Line 1,349 ⟶ 1,350:
20: 170581728179578208256
21: 216</pre>
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="Quackery"> [ 0 swap
[ dip 1+
10 /
dup 0 = until ]
drop ] is digits ( n --> n )
 
[ 10 over digits
** temp put
false unrot
[ over temp share mod
over = iff
[ rot not unrot ]
done
dip [ 10 / ]
over 0 = until ]
2drop
temp release ] is contains ( n n --> b )
 
[ -1 swap
[ dip 1+
over 6 swap **
over contains
until ]
drop ] is smallest ( n --> n )
 
22 times
[ i^ 10 < if sp
i^ echo
say " --> "
6 i^ smallest **
echo cr ]
cr
say "The smallest power of 6 whose decimal expansion contains 31415926 is 6^"
31415926 smallest echo say "." cr</syntaxhighlight>
 
{{out}}
 
<pre> 0 --> 10077696
1 --> 1
2 --> 216
3 --> 36
4 --> 46656
5 --> 46656
6 --> 6
7 --> 7776
8 --> 2176782336
9 --> 1296
10 --> 10077696
11 --> 2821109907456
12 --> 1296
13 --> 13060694016
14 --> 6140942214464815497216
15 --> 101559956668416
16 --> 216
17 --> 60466176
18 --> 470184984576
19 --> 21936950640377856
20 --> 170581728179578208256
21 --> 216
 
The smallest power of 6 whose decimal expansion contains 31415926 is 6^4261.</pre>
 
=={{header|Raku}}==
Line 1,491 ⟶ 1,556:
</pre>
 
=={{header|RPL}}==
1980s RPL can only handle 64-bit unsigned integers, which means a multi-precision multiplication is here required.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ 1000000000 → x n p
≪ { } # 0d
x SIZE 1 '''FOR''' j
x j GET n * +
DUP p / SWAP OVER p * - ROT + SWAP
-1 '''STEP'''
'''IF''' DUP # 0d ≠ '''THEN''' SWAP + '''ELSE''' DROP '''END'''
≫ ≫ '<span style="color:blue">MMULT</span>' STO
≪ "" SWAP
1 OVER SIZE '''FOR''' d
DUP d GET →STR 3 OVER SIZE 1 - SUB
'''IF''' d 1 ≠ '''THEN'''
'''WHILE''' DUP SIZE 9 < REPEAT "0" SWAP +
'''END END'''
ROT SWAP + SWAP
'''NEXT''' DROP
≫ '<span style="color:blue">M→STR</span>' STO
≪
{ # 1d } SWAP
WHILE DUP REPEAT
SWAP 6 <span style="color:blue">MMULT</span> SWAP 1 - END
DROP <span style="color:blue">M→STR</span>
≫ '<span style="color:blue">POW6</span>' STO
≪ DEC { }
0 21 '''FOR''' n
n →STR -1
DO 1 + DUP '''POW6'''
'''UNTIL''' 3 PICK POS '''END'''
<span style="color:blue">POW6</span> ROT SWAP + SWAP DROP
NEXT
≫ '<span style="color:blue">TASK</span>' STO
|
<span style="color:blue">MMULT</span> ''( { #multi #precision } n -- { #multi #precision } )''
initialize stack with empty result number and carry
loop from the lowest digit block
multiply block by n, add carry
prepare carry for next block
if carry ≠ 0 then add it as a new block
<span style="color:blue">M→STR</span> ''( { #multi #precision } -- "integer" )''
for each digit block
turn it into string, remove both ends
if not the highest block
fill with "0"
add to previous blocks' string
<span style="color:blue">POW6</span> ''( n -- { #multi #precision } )''
{ #1d } is 1 in multi-precision
multiply n times
by 6
make it a string
Forces decimal mode for integer display
for n < 22
turn n into string, initialize counter
get 6^n
until "n" in "6^n"
remake n a string and add it to result list
|}
{{out}}
<pre>
1: { "10077696" "1" "216" "36" "46656" "46656" "6" "7776" "2176782336" "1296" "10077696" "2821109907456" "1296" "13060694016" "6140942214464815497216" "101559956668416" "216" "60466176" "470184984576" "21936950640377856" "170581728179578208256" "216" }
</pre>
====2000s RPL version====
Big integers are native in this version.
{{works with|HP|49}}
≪ { }
0 21 '''FOR''' n
0
'''WHILE''' 6 OVER ^ →STR n →STR POS NOT
'''REPEAT''' 1 + '''END'''
"'6^" SWAP + STR→ +
'''NEXT'''
≫ '<span style="color:blue">TASK</span>' STO
 
{{out}}
<pre>
1: { 6^9 6^0 6^3 6^2 6^6 6^6 6^1 6^5 6^12 6^4 6^9 6^16 6^4 6^13 6^28 6^18 6^3 6^10 6^15 6^21 6^26 6^3 }
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def smallest_6(n)
i = 1
c = 0
s = n.to_s
until i.to_s.match?(s)
c += 1
i *= 6
end
[n, c, i]
end
 
(0..21).each{|n| puts "%3d**%-3d: %d" % smallest_6(n) }
</syntaxhighlight>
{{out}}
<pre> 0**9 : 10077696
1**0 : 1
2**3 : 216
3**2 : 36
4**6 : 46656
5**6 : 46656
6**1 : 6
7**5 : 7776
8**12 : 2176782336
9**4 : 1296
10**9 : 10077696
11**16 : 2821109907456
12**4 : 1296
13**13 : 13060694016
14**28 : 6140942214464815497216
15**18 : 101559956668416
16**3 : 216
17**10 : 60466176
18**15 : 470184984576
19**21 : 21936950640377856
20**26 : 170581728179578208256
21**3 : 216
</pre>
=={{header|Wren}}==
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./fmt" for Fmt
 
System.print(" n smallest power of 6 which contains n")
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/338546...354740"