Smallest power of 6 whose decimal expansion contains n: Difference between revisions
m (→{{header|Pascal}}: can't imagine that PHIX tested limit -- (tested to 10,000,000)) |
|||
Line 92: | Line 92: | ||
Doing long multiplikation like in primorial task. |
Doing long multiplikation like in primorial task. |
||
<lang pascal>program PotOf6; |
<lang pascal>program PotOf6; |
||
{$IFDEF FPC |
{$IFDEF FPC} |
||
{$MODE DELPHI} |
|||
{$OPTIMIZATION ON,ALL} |
|||
{$ELSE} |
|||
{$APPTYPE CONSOLE} |
|||
{$ENDIF} |
|||
uses |
uses |
||
sysutils; |
sysutils; |
||
const |
const |
||
// POT_LIMIT = |
// POT_LIMIT = 6260;DEC_LIMIT = 1000000;//'575115' in 6^6260 //22min // ~Limit x10 ~> runtime x 87 |
||
// POT_LIMIT = |
// POT_LIMIT = 1736;DEC_LIMIT = 100000;//'83081' in 6^1736 //15.3s |
||
// POT_LIMIT = |
// POT_LIMIT = 444;DEC_LIMIT = 10000;//'2565' // 0.19s |
||
// POT_LIMIT = |
// POT_LIMIT = 147;DEC_LIMIT = 1000;//'120' |
||
POT_LIMIT = |
// POT_LIMIT = 46;DEC_LIMIT = 100;//'52' |
||
POT_LIMIT = 28;DEC_LIMIT = 22;//'14' |
|||
type |
type |
||
tMulElem = Uint32; |
tMulElem = Uint32; |
||
tMul = array of tMulElem; |
tMul = array of tMulElem; |
||
var |
var |
||
⚫ | |||
Pot_N_str : array of AnsiString; |
Pot_N_str : array of AnsiString; |
||
function ConvToStr(const Mul:tMul):AnsiString; |
function ConvToStr(const Mul:tMul):AnsiString; |
||
const |
|||
NineZeros:string[9] ='000000000'; |
|||
var |
var |
||
s,dummy: string[9]; |
|||
i,j : integer; |
|||
begin |
begin |
||
setlength(result,length(MUL)*9); |
|||
i := High(Mul); |
i := High(Mul); |
||
result := IntToStr(Mul[i]); |
result := IntToStr(Mul[i]); |
||
Line 117: | Line 126: | ||
If i >= 0 then |
If i >= 0 then |
||
repeat |
repeat |
||
result += Format('%.9d',[Mul[i]]); |
// result += Format('%.9d',[Mul[i]]); takes > double time |
||
dummy := NineZeros; |
|||
s := IntToStr(Mul[i]); |
|||
j := length(s); |
|||
move(s[1],dummy[9+1-j],j); |
|||
result += dummy; |
|||
dec(i); |
dec(i); |
||
until i<0; |
until i<0; |
||
Line 135: | Line 149: | ||
Begin |
Begin |
||
prod := n*Mul[j]+Carry; |
prod := n*Mul[j]+Carry; |
||
Carry := prod |
Carry := prod DIV LongWordDec; |
||
result[j] := Prod - Carry*LongWordDec; |
result[j] := Prod - Carry*LongWordDec; |
||
end; |
end; |
||
Line 143: | Line 157: | ||
Setlength(result,length(Mul)); |
Setlength(result,length(Mul)); |
||
end; |
end; |
||
procedure GeneratePot_N_Str(number:NativeInt); |
|||
var |
var |
||
⚫ | |||
⚫ | |||
i |
i : NativeInt; |
||
⚫ | |||
Begin |
Begin |
||
setlength(Pot_N_str,POT_LIMIT+1); |
setlength(Pot_N_str,POT_LIMIT+1); |
||
setlength(PotArrN,POT_LIMIT+1); |
setlength(PotArrN,POT_LIMIT+1); |
||
⚫ | |||
setlength(PotArrN[0],1); |
setlength(PotArrN[0],1); |
||
setlength(PotArrN[1],1); |
setlength(PotArrN[1],1); |
||
Line 160: | Line 171: | ||
PotArrN[1,0] := number; |
PotArrN[1,0] := number; |
||
Pot_N_str[1] := IntToStr(number); |
Pot_N_str[1] := IntToStr(number); |
||
//create all pot of numbers up to number**POT_LIMIT with clean up in parallel |
//create all pot of numbers up to number**POT_LIMIT with clean up in parallel |
||
i := 2; |
i := 2; |
||
while i <= POT_LIMIT do |
while i <= POT_LIMIT do |
||
Line 168: | Line 179: | ||
setlength(PotArrN[i-1],0); |
setlength(PotArrN[i-1],0); |
||
inc(i); |
inc(i); |
||
IF i AND 1023 = 0 then |
|||
write(i,#13); |
|||
end; |
end; |
||
setlength(PotArrN[i-1],0); |
setlength(PotArrN[i-1],0); |
||
setlength(PotArrN[0],0); |
setlength(PotArrN[0],0); |
||
setlength(PotArrN,0); |
setlength(PotArrN,0); |
||
end; |
|||
var |
|||
⚫ | |||
i,j,number,maxpos: NativeInt; |
|||
⚫ | |||
Begin |
|||
⚫ | |||
GeneratePot_N_Str(number); |
|||
//Now check for first occurence str of i |
//Now check for first occurence str of i |
||
maxpos := 0; |
|||
For i := 0 to DEC_LIMIT-1 do |
For i := 0 to DEC_LIMIT-1 do |
||
begin |
begin |
||
Line 182: | Line 204: | ||
Begin |
Begin |
||
found := true; |
found := true; |
||
If maxpos<j then |
|||
⚫ | |||
maxpos:= j; |
|||
IF POT_Limit > 99 then |
|||
write(s:3,number:3,'^',j:5,maxpos:6,#13) |
|||
else |
|||
⚫ | |||
break; |
break; |
||
end; |
end; |
||
Line 191: | Line 218: | ||
end; |
end; |
||
end; |
end; |
||
writeln; |
|||
writeln('max pot :',maxpos); |
|||
// clean up strings |
// clean up strings |
||
For j := POT_LIMIT downto 0 do |
For j := POT_LIMIT downto 0 do |
||
setlength(Pot_N_str[ |
setlength(Pot_N_str[j],0); |
||
setlength(Pot_N_str,0); |
setlength(Pot_N_str,0); |
||
end.</lang> |
end.</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
0 6^ 9 10077696 |
0 6^ 9 10077696 |
||
1 6^ 0 1 |
1 6^ 0 1 |
||
Line 219: | Line 249: | ||
19 6^21 21936950640377856 |
19 6^21 21936950640377856 |
||
20 6^26 170581728179578208256 |
20 6^26 170581728179578208256 |
||
21 6^ 3 216 |
21 6^ 3 216 |
||
max pot :28</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
Revision as of 10:42, 8 April 2021
- Task
Show the smallest (non-negative integer) power of 6 whose decimal expansion contains n, where n < 22
Factor
<lang factor>USING: formatting kernel lists lists.lazy math math.functions present sequences tools.memory.private ;
- powers-of-6 ( -- list )
0 lfrom [ 6 swap ^ ] lmap-lazy ;
- smallest ( m -- n )
present powers-of-6 [ present subseq? ] with lfilter car ;
22 [ dup smallest commas "%2d %s\n" printf ] each-integer</lang>
- Output:
0 10,077,696 1 1 2 216 3 36 4 46,656 5 46,656 6 6 7 7,776 8 2,176,782,336 9 1,296 10 10,077,696 11 2,821,109,907,456 12 1,296 13 13,060,694,016 14 6,140,942,214,464,815,497,216 15 101,559,956,668,416 16 216 17 60,466,176 18 470,184,984,576 19 21,936,950,640,377,856 20 170,581,728,179,578,208,256 21 216
Julia
<lang julia>using Formatting
digcontains(n, dig) = contains(String(Char.(digits(n))), String(Char.(dig)))
function findpow6containing(needle)
dig = digits(needle) for i in 0:1000 p = big"6"^i digcontains(p, dig) && return p end error("could not find a power of 6 containing $dig")
end
for n in 0:21
println(rpad(n, 5), format(findpow6containing(n), commas=true))
end
</lang>
- Output:
0 10,077,696 1 1 2 216 3 36 4 46,656 5 46,656 6 6 7 7,776 8 2,176,782,336 9 1,296 10 10,077,696 11 2,821,109,907,456 12 1,296 13 13,060,694,016 14 6,140,942,214,464,815,497,216 15 101,559,956,668,416 16 216 17 60,466,176 18 470,184,984,576 19 21,936,950,640,377,856 20 170,581,728,179,578,208,256 21 216
Pascal
Doing long multiplikation like in primorial task. <lang pascal>program PotOf6; {$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils;
const // POT_LIMIT = 6260;DEC_LIMIT = 1000000;//'575115' in 6^6260 //22min // ~Limit x10 ~> runtime x 87 // POT_LIMIT = 1736;DEC_LIMIT = 100000;//'83081' in 6^1736 //15.3s // POT_LIMIT = 444;DEC_LIMIT = 10000;//'2565' // 0.19s // POT_LIMIT = 147;DEC_LIMIT = 1000;//'120' // POT_LIMIT = 46;DEC_LIMIT = 100;//'52'
POT_LIMIT = 28;DEC_LIMIT = 22;//'14'
type
tMulElem = Uint32; tMul = array of tMulElem;
var
Pot_N_str : array of AnsiString;
function ConvToStr(const Mul:tMul):AnsiString; const
NineZeros:string[9] ='000000000';
var
s,dummy: string[9]; i,j : integer;
begin
setlength(result,length(MUL)*9); i := High(Mul); result := IntToStr(Mul[i]); dec(i); If i >= 0 then repeat
// result += Format('%.9d',[Mul[i]]); takes > double time
dummy := NineZeros; s := IntToStr(Mul[i]); j := length(s); move(s[1],dummy[9+1-j],j); result += dummy; dec(i); until i<0;
end;
function Mul_N(var Mul:tMul;n:Uint64):tMul; //n<LongWordDec ! const
LongWordDec = 1000*1000*1000;
var
prod,carry : Uint64; j : NativeInt;
begin
Setlength(result,length(Mul)+1); carry := 0; For j := 0 to High(Mul) do Begin prod := n*Mul[j]+Carry; Carry := prod DIV LongWordDec; result[j] := Prod - Carry*LongWordDec; end; IF Carry <> 0 then result[High(Mul)+1] := Carry else Setlength(result,length(Mul));
end; procedure GeneratePot_N_Str(number:NativeInt); var
PotArrN : array of tMul; i : NativeInt;
Begin
setlength(Pot_N_str,POT_LIMIT+1);
setlength(PotArrN,POT_LIMIT+1); setlength(PotArrN[0],1); setlength(PotArrN[1],1); PotArrN[0,0] := 1; Pot_N_str[0] := '1'; PotArrN[1,0] := number; Pot_N_str[1] := IntToStr(number);
//create all pot of numbers up to number**POT_LIMIT with clean up in parallel
i := 2; while i <= POT_LIMIT do begin PotArrN[i] := Mul_N(PotArrN[i-1],number); Pot_N_str[i] := ConvToStr(PotArrN[i]); setlength(PotArrN[i-1],0); inc(i); IF i AND 1023 = 0 then write(i,#13); end; setlength(PotArrN[i-1],0); setlength(PotArrN[0],0); setlength(PotArrN,0);
end; var
s:AnsiString; i,j,number,maxpos: NativeInt; found:Boolean;
Begin
number:= 6; GeneratePot_N_Str(number);
//Now check for first occurence str of i maxpos := 0; For i := 0 to DEC_LIMIT-1 do begin s := intToStr(i); found:= false; For j := 0 to POT_LIMIT do if Pos(s,Pot_N_str[j])>0 then Begin found := true; If maxpos<j then maxpos:= j; IF POT_Limit > 99 then write(s:3,number:3,'^',j:5,maxpos:6,#13) else writeln(s:3,number:3,'^',j:2,' ', Pot_N_str[j]); break; end; if Not(Found) then Begin Write(s,' Not Found '); readln; end; end; writeln; writeln('max pot :',maxpos); // clean up strings For j := POT_LIMIT downto 0 do setlength(Pot_N_str[j],0); setlength(Pot_N_str,0);
end.</lang>
- Output:
0 6^ 9 10077696 1 6^ 0 1 2 6^ 3 216 3 6^ 2 36 4 6^ 6 46656 5 6^ 6 46656 6 6^ 1 6 7 6^ 5 7776 8 6^12 2176782336 9 6^ 4 1296 10 6^ 9 10077696 11 6^16 2821109907456 12 6^ 4 1296 13 6^13 13060694016 14 6^28 6140942214464815497216 15 6^18 101559956668416 16 6^ 3 216 17 6^10 60466176 18 6^15 470184984576 19 6^21 21936950640377856 20 6^26 170581728179578208256 21 6^ 3 216 max pot :28
Phix
Another good opportunity to do some string math, this time with embedded commas. Scales effortlessly.
(Related recent task: Show_the_(decimal)_value_of_a_number_of_1s_appended_with_a_3,_then_squared#Phix)
constant lim = 22 -- (tested to 10,000,000) atom t0 = time(), t1 = t0+1 sequence res = repeat(0,lim), pwr = repeat(0,lim) string p6 = "1" res[2] = p6 integer found = 1, p = 0 while found<lim do integer carry = 0 for i=length(p6) to 1 by -1 do if p6[i]!=',' then integer digit = (p6[i]-'0')*6+carry p6[i] = remainder(digit,10)+'0' carry = floor(digit/10) end if end for if carry then if remainder(length(p6)+1,4)=0 then p6 = "," & p6 end if p6 = carry+'0' & p6 end if p += 1 for i=1 to length(p6) do if p6[i]!=',' then integer digit = 0, j = i while j<=length(p6) and digit<=lim do j += p6[j]=',' digit = digit*10+p6[j]-'0' if digit<lim and res[digit+1]=0 then res[digit+1] = p6 pwr[digit+1] = p found += 1 end if j += 1 end while end if end for if time()>t1 then progress("found %,d/%,d, at 6^%,d which has %,d digits (%s)", {found,lim,p,length(p6)*3/4,elapsed(time()-t0)}) t1 = time()+1 end if end while papply(true,printf,{1,{"%2d %29s = 6^%d\n"},shorten(columnize({tagset(lim-1,0),res,pwr}),"",10)})
- Output:
0 10,077,696 = 6^9 1 1 = 6^0 2 216 = 6^3 3 36 = 6^2 4 46,656 = 6^6 5 46,656 = 6^6 6 6 = 6^1 7 7,776 = 6^5 8 2,176,782,336 = 6^12 9 1,296 = 6^4 10 10,077,696 = 6^9 11 2,821,109,907,456 = 6^16 12 1,296 = 6^4 13 13,060,694,016 = 6^13 14 6,140,942,214,464,815,497,216 = 6^28 15 101,559,956,668,416 = 6^18 16 216 = 6^3 17 60,466,176 = 6^10 18 470,184,984,576 = 6^15 19 21,936,950,640,377,856 = 6^21 20 170,581,728,179,578,208,256 = 6^26 21 216 = 6^3
Raku
<lang perl6>use Lingua::EN::Numbers;
sub super ($n) { $n.trans(<0 1 2 3 4 5 6 7 8 9> => <⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹>) }
my @po6 = ^Inf .map: *.exp: 6;
put join "\n", (flat ^22, 120).map: -> $n {
sprintf "%3d: 6%-4s %s", $n, .&super, comma @po6[$_] given @po6.first: *.contains($n), :k
};</lang>
- Output:
0: 6⁹ 10,077,696 1: 6⁰ 1 2: 6³ 216 3: 6² 36 4: 6⁶ 46,656 5: 6⁶ 46,656 6: 6¹ 6 7: 6⁵ 7,776 8: 6¹² 2,176,782,336 9: 6⁴ 1,296 10: 6⁹ 10,077,696 11: 6¹⁶ 2,821,109,907,456 12: 6⁴ 1,296 13: 6¹³ 13,060,694,016 14: 6²⁸ 6,140,942,214,464,815,497,216 15: 6¹⁸ 101,559,956,668,416 16: 6³ 216 17: 6¹⁰ 60,466,176 18: 6¹⁵ 470,184,984,576 19: 6²¹ 21,936,950,640,377,856 20: 6²⁶ 170,581,728,179,578,208,256 21: 6³ 216 120: 6¹⁴⁷ 2,444,746,349,972,956,194,083,608,044,935,243,159,422,957,210,683,702,349,648,543,934,214,737,968,217,920,868,940,091,707,112,078,529,114,392,164,827,136
REXX
<lang rexx>/*REXX pgm finds the smallest (decimal) power of 6 which contains N, where N < 22. */ numeric digits 100 /*ensure enough decimal digs for 6**N */ parse arg hi . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 22 /*Not specified? Then use the default.*/ w= 50 /*width of a number in any column. */
@smp6= ' smallest power of six (expressed in decimal) which contains N'
say ' N │ power │'center(@smp6, 20 + w ) /*display the title of the output. */ say '─────┼───────┼'center("" , 20 + w, '─') /* " " separator " " " */
do j=0 for hi /*look for a power of 6 that contains N*/ do p=0; x= 6**p /*compute a power of six (in decimal). */ if pos(j, x)>0 then leave /*does the power contain an N ? */ end /*p*/ c= commas(x) /*maybe add commas to the powe of six. */ z= right(c, max(w, length(c) ) ) /*show a power of six, allow biger #s. */ say center(j, 5)'│'center(p, 7)"│" z /*display what we have so far (cols). */ end /*j*/
say '─────┴───────┴'center("" , 20 + w, '─') /* " " separator " " " */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</lang>
- output when using the default input:
N │ power │ smallest power of six (expressed in decimal) which contains N ─────┼───────┼────────────────────────────────────────────────────────────────────── 0 │ 9 │ 10,077,696 1 │ 0 │ 1 2 │ 3 │ 216 3 │ 2 │ 36 4 │ 6 │ 46,656 5 │ 6 │ 46,656 6 │ 1 │ 6 7 │ 5 │ 7,776 8 │ 12 │ 2,176,782,336 9 │ 4 │ 1,296 10 │ 9 │ 10,077,696 11 │ 16 │ 2,821,109,907,456 12 │ 4 │ 1,296 13 │ 13 │ 13,060,694,016 14 │ 28 │ 6,140,942,214,464,815,497,216 15 │ 18 │ 101,559,956,668,416 16 │ 3 │ 216 17 │ 10 │ 60,466,176 18 │ 15 │ 470,184,984,576 19 │ 21 │ 21,936,950,640,377,856 20 │ 26 │ 170,581,728,179,578,208,256 21 │ 3 │ 216 ─────┴───────┴──────────────────────────────────────────────────────────────────────
Ring
<lang ring> load "stdlib.ring"
decimals(0) see "working..." + nl see "Smallest power of 6 whose decimal expansion contains n:" + nl
num = 0 limit = 200
for n = 1 to 21
strn = string(n) for m = 0 to limit strpow = string(pow(6,m)) ind = substr(strpow,strn) if ind > 0 see "" + n + ". " + "6^" + m + " = " + strpow + nl exit ok next
next
see "done..." + nl </lang>
- Output:
working... Smallest power of 6 whose decimal expansion contains n: 1. 6^0 = 1 2. 6^3 = 216 3. 6^2 = 36 4. 6^6 = 46656 5. 6^6 = 46656 6. 6^1 = 6 7. 6^5 = 7776 8. 6^12 = 2176782336 9. 6^4 = 1296 10. 6^9 = 10077696 11. 6^16 = 2821109907456 12. 6^4 = 1296 13. 6^13 = 13060694016 14. 6^28 = 6140942214464815497216 15. 6^18 = 101559956668416 16. 6^3 = 216 17. 6^10 = 60466176 18. 6^15 = 470184984576 19. 6^21 = 21936950640377856 20. 6^26 = 170581728179578208256 21. 6^3 = 216 done...
Wren
<lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt
System.print(" n smallest power of 6 which contains n") var six = BigInt.new(6) for (n in 0..21) {
var i = 0 while (true) { var pow6 = six.pow(i).toString if (pow6.contains(n.toString)) { Fmt.print("$2d 6^$-2d = $,s", n, i, pow6) break } i = i + 1 }
}</lang>
- Output:
n smallest power of 6 which contains n 0 6^9 = 10,077,696 1 6^0 = 1 2 6^3 = 216 3 6^2 = 36 4 6^6 = 46,656 5 6^6 = 46,656 6 6^1 = 6 7 6^5 = 7,776 8 6^12 = 2,176,782,336 9 6^4 = 1,296 10 6^9 = 10,077,696 11 6^16 = 2,821,109,907,456 12 6^4 = 1,296 13 6^13 = 13,060,694,016 14 6^28 = 6,140,942,214,464,815,497,216 15 6^18 = 101,559,956,668,416 16 6^3 = 216 17 6^10 = 60,466,176 18 6^15 = 470,184,984,576 19 6^21 = 21,936,950,640,377,856 20 6^26 = 170,581,728,179,578,208,256 21 6^3 = 216