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 12:36, 6 February 2024
, 3 months ago→{{header|Wren}}: Minor tidy
m (→{{header|Free Pascal}}: Commatize was a huge time factor) |
m (→{{header|Wren}}: Minor tidy) |
||
(8 intermediate revisions by 4 users not shown) | |||
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 = 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;
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;
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;
end;
pChecked[num]:= true;
with str_Found[num]
foundIndex:= pow+1;
foundStrIdx:= FoundIDX-1;
end;
inc(result);
if num =FirstMissing then
repeat
inc(FirstMissing)
until str_Found[FirstMissing].foundIndex =0;
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.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Init in 0.062 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>
Line 1,355 ⟶ 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,497 ⟶ 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="
import "./fmt" for Fmt
System.print(" n smallest power of 6 which contains n")
|