Smallest power of 6 whose decimal expansion contains n
- Task
Show the smallest (non-negative integer) power of 6 whose decimal expansion contains n, where n < 22
ALGOL 68
Uses ALGOL 68G's LONG LONG INT large integers, the default precision is sufficient for this task. Also uses the ALGOL 68G specific string in string procedure. <lang algol68>BEGIN # find the smallest k such that the decimal representation of 6^k contains n for 0 <= n <= 21 #
# returns s blank-padded on the right to at least len characters #
PROC right pad = ( STRING s, INT len )STRING:
BEGIN
INT s len = ( UPB s - LWB s ) + 1;
IF s len >= len THEN s ELSE s + ( len - s len ) * " " FI
END # right pad # ;
# returns s blank-padded on the left to at least len characters #
PROC left pad = ( STRING s, INT len )STRING:
BEGIN
INT s len = ( UPB s - LWB s ) + 1;
IF s len >= len THEN s ELSE ( ( len - s len ) * " " ) + s FI
END # left pad # ;
# returns a string representation of unformatted with space separators #
PROC space separate = ( STRING unformatted )STRING:
BEGIN
STRING result := "";
INT ch count := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF ch count <= 2 THEN ch count +:= 1
ELSE ch count := 1; " " +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END # space separate # ;
# start with powers up to 6^12, if this proves insufficient, the kk array will be extended #
FLEX[ 0 : 12 ]STRING kk;
FOR k FROM LWB kk TO UPB kk DO kk[ k ] := whole( LONG LONG INT( 6 ) ^ k, 0 ) OD;
# find the numbers #
FOR i FROM 0 TO 21 DO
STRING n = whole( i, 0 );
BOOL try again := TRUE;
WHILE try again DO
try again := FALSE;
BOOL found := FALSE;
FOR k FROM LWB kk TO UPB kk WHILE NOT found DO
IF string in string( n, NIL, kk[ k ] ) THEN
found := TRUE;
print( ( whole( i, -2 ), right pad( ": 6^" + whole( k, 0 ), 8 ), " ", left pad( space separate( kk[ k ] ), 30 ), newline ) )
FI
OD;
IF NOT found THEN
# haven't got enough k^k values - get some more #
kk := HEAP[ 1 : UPB kk * 2 ]STRING;
FOR k FROM LWB kk TO UPB kk DO kk[ k ] := whole( LONG LONG INT( 6 ) ^ k, 0 ) OD;
try again := TRUE
FI
OD
OD
END</lang>
- Output:
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
ALGOL W
Algol W doesn't have integers larger than 32 bits, however we can handle the required numbers with arrays of digits. <lang algolw>begin % find the smallest power of 6 that contains n for 0 <= n <= 21 %
% we assume that powers of 6 upto 6^32 will be sufficient %
% as Algol W does not have integers longer than 32 bits, the powers %
% will be held in an array where each element is a single digit of the %
% power, the least significant digit of 6^n is in powers( n, 1 ) %
integer array powers ( 0 :: 32, 1 :: 32 ); % the powers %
integer array digits ( 0 :: 32 ); % the number of digits in each power %
integer array lowest ( 0 :: 21 ); % the lowest power containing the idx %
for n := 0 until 21 do lowest( n ) := -1;
% 6^0 = 1, which is the lowest power containing 1 %
lowest( 1 ) := 0;
powers( 0, 1 ) := 1;
for d := 2 until 32 do powers( 0, d ) := 0;
digits( 0 ) := 1;
% calculate the remaining powers and find the numbers 0..21 %
for p := 1 until 32 do begin
integer carry, dPos, dMax;
dPos := 1;
dMax := digits( p - 1 );
carry := 0;
% compute the power p and find the single digit numbers %
while dPos <= dMax do begin
integer d;
d := carry + ( powers( p - 1, dPos ) * 6 );
carry := d div 10;
d := d rem 10;
if lowest( d ) < 0 then lowest( d ) := p;
powers( p, dPos ) := d;
dPos := dPos + 1
end while_dPos_le_dMax ;
if carry = 0
then digits( p ) := dMax
else begin
% the power p has one more digit than the previous %
digits( p ) := dPos;
powers( p, dPos ) := carry;
if lowest( carry ) < 0 then lowest( carry ) := p;
end if_carry_eq_0__ ;
% find the two digit numbers %
for n := 10 until 21 do begin
if lowest( n ) < 0 then begin
integer h, l;
h := n div 10;
l := n rem 10;
for d := digits( p ) - 1 step -1 until 1 do begin
if powers( p, d ) = l and powers( p, d + 1 ) = h then lowest( n ) := p
end for_d
end if_lowest_n_lt_0
end for_n
end for_p ;
% show the lowest powers that contain the numbers 0..21 %
for n := 0 until 21 do begin
integer p;
p := lowest( n );
write( i_w := 2, s_w := 0, n, " in 6^", p, ": " );
for d := digits( p ) step -1 until 1 do writeon( i_w := 1, s_w := 0, powers( p, d ) )
end for_n
end.</lang>
- Output:
0 in 6^ 9: 10077696 1 in 6^ 0: 1 2 in 6^ 3: 216 3 in 6^ 2: 36 4 in 6^ 6: 46656 5 in 6^ 6: 46656 6 in 6^ 1: 6 7 in 6^ 5: 7776 8 in 6^12: 2176782336 9 in 6^ 4: 1296 10 in 6^ 9: 10077696 11 in 6^16: 2821109907456 12 in 6^ 4: 1296 13 in 6^13: 13060694016 14 in 6^28: 6140942214464815497216 15 in 6^18: 101559956668416 16 in 6^ 3: 216 17 in 6^10: 60466176 18 in 6^15: 470184984576 19 in 6^21: 21936950640377856 20 in 6^26: 170581728179578208256 21 in 6^ 3: 216
AWK
<lang AWK>
- syntax: GAWK -f SMALLEST_POWER_OF_6_WHOSE_DECIMAL_EXPANSION_CONTAINS_N.AWK
BEGIN {
printf(" n power %30s\n","smallest power of 6")
for (n=0; n<22; n++) {
p = 1
power = 0
while (p !~ n) {
p *= 6
power++
}
printf("%2d %5d %'30d\n",n,power,p)
}
exit(0)
} </lang>
- Output:
n power smallest power of 6 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
C
<lang C>#include <stdio.h>
- include <string.h>
- include <gmp.h>
char *power_of_six(unsigned int n, char *buf) {
mpz_t p; mpz_init(p); mpz_ui_pow_ui(p, 6, n); mpz_get_str(buf, 10, p); mpz_clear(p); return buf;
}
char *smallest_six(unsigned int n) {
static char nbuf[32], powbuf[1024];
unsigned int p = 0;
do {
sprintf(nbuf, "%u", n);
power_of_six(p++, powbuf);
} while (!strstr(powbuf, nbuf));
return powbuf;
}
int main() {
unsigned int i;
for (i=0; i<22; i++) {
printf("%d: %s\n", i, smallest_six(i));
}
return 0;
}</lang>
- Output:
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
C++
<lang cpp>#include <iostream>
- include <iomanip>
- include <string>
- include <gmpxx.h>
std::string smallest_six(unsigned int n) {
mpz_class pow = 1;
std::string goal = std::to_string(n);
while (pow.get_str().find(goal) == std::string::npos) {
pow *= 6;
}
return pow.get_str();
}
int main() {
for (unsigned int i=0; i<22; i++) {
std::cout << std::setw(2) << i << ": "
<< smallest_six(i) << std::endl;
}
return 0;
}</lang>
- Output:
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
F#
<lang fsharp> // Nigel Galloway. April 9th., 2021 let rec fN i g e l=match l%i=g,l/10I with (true,_)->e |(_,l) when l=0I->fN i g (e*6I) (e*6I) |(_,l)->fN i g e l [0I..99I]|>Seq.iter(fun n->printfn "%2d %A" (int n)(fN(if n>9I then 100I else 10I) n 1I 1I)) </lang>
- Output:
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 22 131621703842267136 23 2176782336 24 1023490369077469249536 25 170581728179578208256 26 16926659444736 27 279936 28 2821109907456 29 1296 30 13060694016 31 131621703842267136 32 4738381338321616896 33 2176782336 34 1023490369077469249536 35 609359740010496 36 36 37 21936950640377856 38 131621703842267136 39 221073919720733357899776 40 13060694016 41 78364164096 42 131621703842267136 43 28430288029929701376 44 16926659444736 45 470184984576 46 46656 47 470184984576 48 6140942214464815497216 49 470184984576 50 21936950640377856 51 1326443518324400147398656 52 623673825204293256669089197883129856 53 789730223053602816 54 6140942214464815497216 55 101559956668416 56 46656 57 470184984576 58 3656158440062976 59 16926659444736 60 60466176 61 1679616 62 362797056 63 47751966659678405306351616 64 78364164096 65 46656 66 46656 67 1679616 68 101559956668416 69 10077696 70 362797056 71 131621703842267136 72 170581728179578208256 73 16926659444736 74 2821109907456 75 47751966659678405306351616 76 7776 77 7776 78 2176782336 79 279936 80 28430288029929701376 81 789730223053602816 82 2176782336 83 78364164096 84 470184984576 85 21936950640377856 86 36845653286788892983296 87 61886548790943213277031694336 88 28430288029929701376 89 789730223053602816 90 2821109907456 91 221073919720733357899776 92 16926659444736 93 279936 94 13060694016 95 101559956668416 96 1296 97 362797056 98 470184984576 99 279936 Real: 00:00:00.066
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
Go
<lang go>package main
import (
"fmt" "math/big" "strconv" "strings"
)
// Adds thousand separators to an integral string. func commatize(s string) string {
neg := false
if strings.HasPrefix(s, "-") {
s = s[1:]
neg = true
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if !neg {
return s
}
return "-" + s
}
func main() {
fmt.Println(" n smallest power of 6 which contains n")
six := big.NewInt(6)
for n := 0; n <= 21; n++ {
ns := strconv.Itoa(n)
i := int64(0)
for {
bi := big.NewInt(i)
pow6 := bi.Exp(six, bi, nil).String()
if strings.Contains(pow6, ns) {
fmt.Printf("%2d 6^%-2d = %s\n", n, i, commatize(pow6))
break
}
i++
}
}
}</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
Haskell
<lang haskell>import Data.List (isInfixOf) import Text.Printf (printf)
sixes :: [Integer] sixes = iterate (* 6) 1
smallest :: Integer -> Integer smallest n =
head $
filter
((show n `isInfixOf`) . show)
sixes
main :: IO () main =
putStr $
concatMap
(printf "%2d: %d\n" <*> smallest)
[0 .. 21]</lang>
- Output:
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
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
Nim
<lang Nim>import strformat, strutils import bignum
var toFind = {0..21} var results: array[0..21, (int, string)] var p = newInt(1) var k = 0 while toFind.card > 0:
let str = $p
for n in toFind:
if str.find($n) >= 0:
results[n] = (k, str)
toFind.excl(n)
p *= 6
inc k
echo "Smallest values of k such that 6^k contains n:" for n, (k, s) in results:
echo &"{n:2}: 6^{k:<2} = {s}"</lang>
- Output:
Smallest values of k such that 6^k contains n: 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
Pascal
Doing long multiplikation like in primorial task.
I used to check every numberstring one after the other on one 6^ n string.Gets really slow on high n
After a closer look into 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.
<lang pascal>program PotOf6;
//First occurence of a numberstring with max DIGTIS digits in 6^n
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
const
POT_LIMIT = 70000;
{ DIGITS = 8;
67584 99999998 46238296
Max power 68479 Found: 100000000 Time used 148.584 secs}
DIGITS = 7;
type
tMulElem = Uint32; tMul = array of tMulElem; tpMul = pUint32; tPotArrN = array[0..1] of tMul;
tFound = record
foundIndex: Uint32;
foundStr :Ansistring;
end;
var
PotArrN : tPotArrN; Pot_N_str : AnsiString; Str_Found : array of tFound; FirstMissing :NativeInt; T0 : INt64;
procedure Init_Mul(number:NativeInt); var
MaxMulIdx : NativeInt;
Begin
MaxMulIdx := trunc(POT_LIMIT*ln(number)/ln(10)/9+2); setlength(PotArrN[0],MaxMulIdx); setlength(PotArrN[1],MaxMulIdx); PotArrN[0,0] := 1;
end;
function Mul_N(var Mul1,Mul2:tMul;limit,n:Uint32):NativeInt; //Mul2 = n*Mul1. n must be < LongWordDec ! const
LongWordDec = 1000*1000*1000;
var
pM1,pM2 : tpMul; carry,prod : Uint64;
begin
pM1 := @Mul1[0]; pM2 := @Mul2[0]; carry := 0; result :=0; repeat prod := n*pM1[result]+Carry; Carry := prod Div LongWordDec; pM2[result] := Prod - Carry*LongWordDec; inc(result); until result > limit; IF Carry <> 0 then pM2[result] := Carry else dec(result);
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;
procedure ConvToStr(var s:Ansistring;const Mul:tMul;i:NativeInt); var
s9: string[9]; pS : pChar; j,k : NativeInt;
begin // i := High(MUL);
j := (i+1)*9;
setlength(s,j+1);
pS := pChar(s);
// fill complete with '0'
fillchar(pS[0],j,'0');
str(Mul[i],S9);
j := length(s9);
move(s9[1],pS[0],j);
k := j;
dec(i);
If i >= 0 then
repeat
str(Mul[i],S9);// no leading '0'
j := length(s9);
inc(k,9);
//move to the right place, leading '0' is already there
move(s9[1],pS[k-j],j);
dec(i);
until i<0;
setlength(s,k);
end;
function CheckOneString(const s:Ansistring;pow:NativeInt):NativeInt; //check every possible number from one to DIGITS digits, //if it is still missing in the list var
i,k,lmt,num : NativeInt; cs : Ansistring;
begin
result := 0;
cs := ;
lmt := length(s);
For i := 1 to lmt do
Begin
k := i;
num := 0;
repeat
num := num*10+ Ord(s[k])-Ord('0');
IF (num >= FirstMissing) AND (str_Found[num].foundIndex = 0) then
begin
str_Found[num].foundIndex:= pow+1;
// commatize only once. reference counted string
if cs = then
cs := Commatize(s);
str_Found[num].foundStr:= cs;
inc(result);
if num =irstMissing then
while str_Found[FirstMissing].foundIndex <> 0 do
inc(FirstMissing);
end;
inc(k)
until (k>lmt) or (k-i >DIGITS-1);
end;
end;
var
i,j,number,toggle,MaxMulIdx,found,decLimit: Int32;
Begin
T0 := GetTickCount64; number := 6;//<1e9 no power of 10 ;-) decLimit := 1; For i := 1 to digits do decLimit *= 10; setlength(Str_Found,decLimit); Init_Mul(number);
toggle := 0;
found := 0;
FirstMissing := 0;
MaxMulIdx := 0;
For j := 0 to POT_LIMIT do
Begin
ConvToStr(Pot_N_str,PotArrN[toggle],MaxMulIdx);
inc(found,CheckOneString(Pot_N_str,j));
MaxMulIdx := Mul_N(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx,number);
toggle := 1-toggle;
if found>=decLimit then
Begin
writeln(#10,'Max power ',j);
break;
end;
if (j and 1023) = 0 then
write(j:10,found:10,firstMissing:10,#13);
end;
writeln(#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
if foundIndex >0 then
writeln(i:10,' ',number,'^',foundIndex-1:5,' ',foundStr);
readln;
end.</lang>
- Output:
TIO.RUN output
//Power found first missing
0 1 0
1024 751817 10020
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
Found: 10000000 Time used 14.882 secs
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
22 6^ 22 131,621,703,842,267,136
Real time: 15.373 s
User time: 14.953 s
Sys. time: 0.254 s
CPU share: 98.92 %
Perl
<lang perl>use strict; use warnings; use List::Util 'first'; use Math::AnyNum ':overload';
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
for my $n (0..21, 314159) {
my $e = first { 6**$_ =~ /$n/ } 0..1000;
printf "%7d: 6^%-3s %s\n", $n, $e, comma 6**$e;
}</lang>
- Output:
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
314159: 6^494 2,551,042,473,957,557,281,758,472,595,966,885,638,262,058,644,568,332,160,010,313,393,465,384,231,415,969,801,503,269,402,221,368,959,426,761,447,049,526,922,498,341,120,174,041,236,629,812,681,424,262,988,020,546,286,492,213,224,906,594,147,652,459,693,833,191,626,748,973,370,777,591,205,509,673,825,541,899,874,436,305,798,094,943,728,762,682,333,192,202,041,960,669,401,031,964,634,164,426,985,990,195,192,836,400,994,016,666,910,919,499,884,972,133,471,176,804,190,463,444,807,178,864,658,551,422,631,018,496
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
A limit of 10,000,000 takes 1 min 41s, reaches 6^21,798 which has 16,963 digits (not including commas) and is the first to contain 8091358, at offset 13,569.
Python
<lang python>def smallest_six(n):
p = 1 while str(n) not in str(p): p *= 6 return p
for n in range(22):
print("{:2}: {}".format(n, smallest_six(n))</lang>
- Output:
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
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