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

27,862 bytes added , 3 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,476

edits

Revision as of 21:33, 9 April 2021 (view source) Not a robot (talk \| contribs) (Add Haskell) ← Older edit		Revision as of 12:36, 6 February 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy) Newer edit →
(32 intermediate revisions by 18 users not shown)
Line 6: =={{header\|11l}}== {{trans\|Python}} <syntaxhighlight lang="11l">F smallest_six(n) V p = BigInt(1) L String(n) !C String(p) p = 6 R p L(n) 22 print(‘#2: #.’.format(n, smallest_six(n)))</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 </pre> =={{header\|ALGOL 68}}== {{works with\|ALGOL 68G\|Any - tested with release 2.8.3.win32}} 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. <syntaxhighlight 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</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|ALGOL W}}== Algol W doesn't have integers larger than 32 bits, however we can handle the required numbers with arrays of digits. <syntaxhighlight 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.</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Arturo}}== <syntaxhighlight lang="arturo">loop 0..22 'n [ ns: to :string n print [pad to :string n 2 "->" 6 ^ first select.first 0..∞ 'x -> contains? to :string 6^x ns] ]</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 22 -> 131621703842267136</pre> =={{header\|AWK}}== <syntaxhighlight 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) } </syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|C}}== <syntaxhighlight 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; }</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</pre> =={{header\|C++}}== <syntaxhighlight 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; }</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</pre> =={{header\|CLU}}== <syntaxhighlight lang="clu">% This program uses the bigint type that comes with PCLU. % It is in "misc.lib" % % pclu -merge $CLUHOME/lib/misc.lib -compile n6_contains_6.clu smallest_power_6 = proc (n: int) returns (int, bigint) n_str: string := int$unparse(n) six_power: bigint := bigint$i2bi(1) six: bigint := bigint$i2bi(6) n_power: int := 0 while true do pow_str: string := bigint$unparse(six_power) if string$indexs(n_str, pow_str) ~= 0 then return(n_power, six_power) end six_power := six_power six n_power := n_power + 1 end end smallest_power_6 start_up = proc () po: stream := stream$primary_output() for n: int in int$from_to(0, 21) do p: int val: bigint stream$putright(po, int$unparse(n), 2) stream$puts(po, ": 6^") p, val := smallest_power_6(n) stream$putleft(po, int$unparse(p), 2) stream$puts(po, " = ") stream$putright(po, bigint$unparse(val), 30) stream$putl(po, "") end end start_up</syntaxhighlight> {{out}} <pre> 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</pre> =={{header\|F_Sharp\|F#}}== <~~lang~~syntaxhighlight 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 (e6I) (e6I) \|(_,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)) </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 117 ⟶ 568: Real: 00:00:00.066 </pre> =={{header\|Factor}}== {{works with\|Factor\|0.99 2021-02-05}} <~~lang~~syntaxhighlight lang="factor">USING: formatting kernel lists lists.lazy math math.functions present sequences tools.memory.private ; Line 128 ⟶ 580: present powers-of-6 [ present subseq? ] with lfilter car ; 22 [ dup smallest commas "%2d %s\n" printf ] each-integer</~~lang~~syntaxhighlight> {{out}} <pre> Line 155 ⟶ 607: </pre> ~~=={{header\|Haskell}}==~~ ~~<lang haskell>import Control.Monad~~ ~~import Data.List~~ ~~import Text.Printf~~ =={{header\|FreeBASIC}}== ~~sixes :: [Integer]~~ {{trans\|Ring}} ~~sixes = iterate (6) 1~~ <syntaxhighlight lang="freebasic"> Print !"\ntrabajando...\n" Print !"M¡nima potencia de 6 cuya expansi¢n decimal contiene n:\n" Dim As Uinteger num = 0, limit = 200, m ~~smallest :: Integer -> Integer~~ ~~smallest n = head $ filter (\r -> show n `isInfixOf` show r) sixes~~ For n As Ubyte = 0 To 21 ~~main :: IO ()~~ Dim As String strn = Str(n) ~~main = putStr $ concatMap (printf "%2d: %d\n" `ap` smallest) [0..21]</lang>~~ For m = 0 To limit Dim As String strpow = Str(6 ^ m) Dim As Ulong ind = Instr(strpow,strn) If ind > 0 Then Print Using "##. 6^\\ = &"; n; Str(m); strpow Exit For End If Next m Next n Print !"\n--- terminado, pulsa RETURN---" Sleep </syntaxhighlight> =={{header\|Go}}== {{trans\|Wren}} <syntaxhighlight 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++ } } }</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Haskell}}== <syntaxhighlight lang="haskell">import Data.List (find, isInfixOf) import Text.Printf (printf) smallest :: Integer -> Integer smallest n = d where Just d = find ((show n `isInfixOf`) . show) sixes sixes :: [Integer] sixes = iterate ( 6) 1 main :: IO () main = putStr $ [0 .. 21] >>= printf "%2d: %d\n" <> smallest</syntaxhighlight> {{out}} <pre> 0: 10077696 1: 1 Line 193 ⟶ 745: 20: 170581728179578208256 21: 216</pre> =={{header\|jq}}== '''Works with gojq, the Go implementation of jq''' gojq provides unbounded-precision integer arithmetic and is therefore appropriate for this task. <syntaxhighlight lang="jq"># To preserve precision: def power($b): . as $in \| reduce range(0;$b) as $i (1; . $in); range(0;22) \| . as $in \| tostring as $n \| first(range(0;infinite) as $i \| 6 \| power($i) \| . as $p \| tostring \| (index($n) // empty) \| [$in,$i,$p] )</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\|Julia}}== <~~lang~~syntaxhighlight lang="julia">using Formatting digcontains(n, dig) = contains(String(Char.(digits(n))), String(Char.(dig))) Line 211 ⟶ 802: println(rpad(n, 5), format(findpow6containing(n), commas=true)) end </~~lang~~syntaxhighlight>{{out}} <pre> 0 10,077,696 Line 236 ⟶ 827: 21 216 </pre> =={{header\|Mathematica}}/{{header\|Wolfram Language}}== <syntaxhighlight lang="mathematica">ClearAll[SmallestPowerContainingN] SmallestPowerContainingN[n_Integer] := Module[{i = 1, test}, While[True, test = 6^i; If[SequenceCount[IntegerDigits[test], IntegerDigits[n]] > 0, Return[{n, i, test}]]; i++; ] ] Grid[SmallestPowerContainingN /@ Range[0, 21]]</syntaxhighlight> {{out}} <pre>0 9 10077696 1 3 216 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\|Nim}}== {{libheader\|bignum}} <syntaxhighlight 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}"</syntaxhighlight> {{out}} <pre>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</pre> =={{header\|Pascal}}== ==={{~~Works with~~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. ~~Doing long multiplikation like in primorial task.~~ <~~lang~~syntaxhighlight lang="pascal">program PotOf6; //First occurence of a numberstring with max decimal DIGTIS digits in 6^n ~~{$IFDEF FPC} {$MODE DELPHI} {$ENDIF}~~ {$IFDEF FPC} {$MODE DELPHI} {$Optimization ON,ALL} {$COPERATORS ON}{$CODEALIGN proc=16} {$ENDIF} {$IFDEF WINDOWS} {$APPTYPE CONSOLE} {$ENDIF} uses sysutils~~,strutils~~; const //decimal places used by multiplication and for string conversion ~~// POT_LIMIT = 6260;DEC_LIMIT = 1000000;//'575115' in 6^6260~~ calcDigits = 8; ~~// POT_LIMIT = 1736;DEC_LIMIT = 100000;~~ PowerBase = 6; // don't use 10^n ;-) ~~//'83081' in 6^1736 mean power 422.48~~ ~~// POT_LIMIT = 444; DEC_LIMIT = 10000;~~ // for PowerBase = 2 maxvalues for POT_LIMIT and STRCOUNT ~~//'2565' mean power 135.82 0.157s~~ // DIGITS = 8;decLimit= 10010001000;POT_LIMIT = 114715;STRCOUNT = 83789; ~~// POT_LIMIT = 147; DEC_LIMIT = 1000;~~ DIGITS = 7;decLimit= 1010001000;POT_LIMIT = 32804;STRCOUNT = 24960; ~~//'120' mean power 44.21~~ // ~~POT_LIMIT~~DIGITS = 466;decLimit= ~~DEC_LIMIT~~ 10001000;POT_LIMIT = 9112;STRCOUNT = ~~100~~7348; // DIGITS = 5;decLimit= 1001000;POT_LIMIT = 2750;STRCOUNT = 2148; ~~//'52' mean power 15.71~~ // DIGITS = 4;decLimit= 101000;POT_LIMIT = 809;STRCOUNT = 616; ~~POT_LIMIT = 28;DEC_LIMIT = 22;~~ // DIGITS = 3;decLimit= 1000;POT_LIMIT = 215;STRCOUNT = 175; ~~//'14' mean power 9.73~~ // DIGITS = 2;decLimit= 100;POT_LIMIT = 66;STRCOUNT = 45; type tMulElem = Uint32; tMul = array of tMulElem; tpMul = pUint32; tPotArrN = array[0..1] of tMul; tFound = record foundIndex, foundStrIdx : Uint32; end; var {$ALIGN 32} ~~Pot_N_str : array of AnsiString;~~ PotArrN : tPotArrN; ~~T0,maxPow,PowerSum,lastpot,SumLenght : INt64;~~ 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; procedure ~~ConvToStr(var s:Ansistring;const Mul:tMul)~~Init_StrDec4Dgts; var s9s : string[94]; i : integer; a,b,c,d : char; begin i := 0; s := '0000'; For a := '0' to '9' do Begin s[1] := a; For b := '0' to '9' do begin s[2]:=b; For c := '0' to '9' do begin s[3] := c; For d := '0' to '9' do begin s[4] := d; StrDec4Dgts[i]:= s; inc(i); end; end; end; end; 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 +1 ; 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 Init_Mul(number:NativeInt); var dgtCount, MaxMulIdx : NativeInt; Begin dgtCount := trunc(POT_LIMITln(number)/ln(10))+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_PowerBase(var Mul1,Mul2:tMul;limit:Uint32):NativeInt; //Mul2 = nMul1. n must be < LongWordDec ! const LongWordDec = 10010001000; var pM1,pM2 : tpMul; carry,prod : Uint64; begin pM1 := @Mul1[0]; pM2 := @Mul2[0]; carry := 0; result :=0; repeat prod := PowerBasepM1[result]+Carry; Carry := prod Div LongWordDec; pM2[result] := Prod - CarryLongWordDec; inc(result); until result > limit; IF Carry <> 0 then pM2[result] := Carry else dec(result); end; procedure ConvToStr(var s:Ansistring;const Mul:tMul;i:NativeInt); var s8: string[calcDigits]; pS : pChar; i,j,k,d,m : NativeInt; begin ij := ~~High~~(~~MUL~~i+1)calcDigits; ~~j := (i+1)9;~~ setlength(s,j+1); pS := ~~pChar(~~@s)[1]; m := Mul[i]; ~~// fill complete with '0'~~ ~~fillchar~~str(pSMul[0i],~~j,'0'~~s8); j := length(s8); ~~str(Mul[i],S9);~~ move(s8[1],pS[0],j); ~~j := length(s9);~~ ~~move(s9[1],pS[0],j);~~ k := j; dec(i); If i >= 0 then repeat ~~str(Mul~~m := MUL[i]~~,S9)~~;~~// no leading '0'~~ jd := ~~length(s9)~~m div 10000; ~~inc(k,9)~~m := m-10000d; move(StrDec4Dgts[d][1],pS[k],4); ~~//move to the right place, leading '0' is already there~~ move(s9StrDec4Dgts[m][1],pS[k-j+4],j4); inc(k,calcDigits); dec(i); until i<0; setlength(s,k); ~~inc(SumLenght,k);~~ end; function ~~Mul_N~~CheckOneString(~~var~~const ~~Mul~~s:~~tMul~~Ansistring;npow:~~Uint64~~NativeInt):~~tMul~~NativeInt; //check every possible number from one to DIGITS digits, ~~//n<LongWordDec !~~ //if it is still missing in the list ~~const~~ ~~LongWordDec = 100010001000;~~ var ~~prod,carry~~pChecked : ~~Uint64~~pBoolean; ji,k,lmt,num : NativeInt; oneFound : boolean; begin pChecked := @CheckedNum[0]; ~~Setlength(result,length(Mul)+1);~~ ~~carry~~result := 0; oneFound := false; ~~For j := 0 to High(Mul) do~~ lmt := length(s); For i := 1 to lmt do Begin ~~prod~~ k := ~~nMul[j]+Carry~~i; ~~Carry~~num := ~~prod Div LongWordDec~~0; repeat ~~result[j] := Prod - CarryLongWordDec;~~ num := num10+ Ord(s[k])-Ord('0'); 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] do Begin 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); end; ~~IF Carry <> 0 then~~ ~~result[High(Mul)+1] := Carry~~ ~~else~~ ~~Setlength(result,length(Mul));~~ end; ~~procedure OutS(const s:Ansistring;j:nativeInt);~~ ~~begin~~ ~~writeln(s,' ',j);~~ ~~end;~~ ~~procedure GeneratePot_N_Str(number:NativeInt);~~ var i,j,k,toggle,MaxMulIdx,found: Int32; ~~PotArrN : array[0..1] of tMul;~~ ~~i,toggle : NativeInt;~~ Begin ~~setlength(Pot_N_str,POT_LIMIT+1);~~ ~~Pot_N_str[0] := '1';~~ ~~Pot_N_str[1] := IntToStr(number);~~ ~~setlength(PotArrN[0],1);~~ ~~setlength(PotArrN[1],1);~~ ~~PotArrN[0,0] := 1;~~ ~~PotArrN[1,0] := number;~~ ~~//create all pot of numbers up to numberPOT_LIMIT with clean up in parallel~~ ~~SumLenght :=0;~~ ~~i := 2;~~ ~~toggle := 0;~~ ~~while i <= POT_LIMIT do~~ ~~begin~~ ~~PotArrN[toggle] := Mul_N(PotArrN[1-toggle],number);~~ ~~ConvToStr(Pot_N_str[i],PotArrN[toggle]);~~ ~~toggle := 1-toggle;~~ ~~inc(i);~~ ~~end;~~ ~~writeln(' used by strings ',Numb2USA(IntToStr(SumLenght)),' bytes');~~ ~~end;~~ ~~procedure OutT(const s: Ansistring;j:NativeInt);~~ ~~Begin~~ ~~writeln(j:10,maxPow/(j+1):8:2,(maxPow-lastPot)/1024:8:2,(GetTickCount64-T0)/1000:10:3);~~ T0 := GetTickCount64; setlength(Str_Found,decLimit); ~~lastpot := maxPow;~~ setlength(CheckedNum,decLimit); ~~end;~~ setlength(FoundString,STRCOUNT); ~~var~~ FirstMissing := 0; ~~s: ansistring;~~ ~~i,j,number~~FoundIdx := ~~Int32~~0; Init_StrDec4Dgts; ~~Begin~~ Init_Mul(PowerBase); ~~number := 6;~~ writeln('Init in ',(GetTickCount64-T0)/1000:8:3,' secs'); T0 := GetTickCount64; toggle := 0; ~~GeneratePot_N_Str(number);~~ found := 0; ~~writeln('Generating time to power limit ',(GetTickCount64-T0)/1000:5:3,'s');~~ 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); i := CheckOneString(Pot_N_str,j); found += i; if i <> 0 then k += 1; MaxMulIdx := Mul_PowerBase(PotArrN[toggle],PotArrN[1-toggle],MaxMulIdx); toggle := 1-toggle; if FirstMissing = decLimit then ~~T0 := GetTickCount64;~~ ~~maxPow := 0;~~ ~~lastpot := 0;~~ ~~For i := 0 to DEC_LIMIT-1 do~~ ~~begin~~ ~~str(i,s);~~ ~~For j := 0 to POT_LIMIT do~~ Begin writeln(#10,'Max power ',j,' with ',length(Pot_N_str),' digits'); ~~if Pos(s,Pot_N_str[j])>0 then~~ ~~Begin~~break; ~~IF maxPow<j then~~ ~~maxPow := J;~~ ~~PowerSum +=j;~~ ~~IF POT_Limit > 99 then~~ ~~write(s:3,number:3,'^',j:5,maxPow:6,#13)~~ ~~else~~ ~~writeln(s:3,number:3,'^',j:2,' ', Pot_N_str[j]);~~ ~~break;~~ ~~end;~~ 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'); ~~writeln;~~ For i := 0 to 22 do//decLimit-1 do ~~writeln('mean power to find string',PowerSum/DEC_LIMIT:8:2);~~ with Str_Found[i] do ~~end.</lang>~~ writeln(i:10,' ',PowerBase,'^',foundIndex-1:5,' ',(FoundString[foundStrIdx]):30); ~~{{out}}~~ end. </syntaxhighlight> {{out\|@TIO.RUN}} <pre> Init in 0.062 secs ~~used by strings 330~~ ~~Generating time to power limit 0.000s~~ ~~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~~ ~~mean~~Max power to21798 ~~find~~with ~~string~~16963 ~~9.73~~digits Found: 10000000 in 15889 strings. Time used 8.114 secs ~~//Search strings 0 to 99999~~ ~~used by strings 1,174,099 bytes~~ ~~Generating time to power limit 0.008s~~ ~~99999 6^ 1287 1736~~ ~~mean power to find string 422.48~~ 0 6^ 9 10,077,696 ~~real 0m14,684s~~ 1 6^ 0 1 ~~user 0m14,522s</pre>~~ 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: 8.383 s User time: 8.133 s Sys. time: 0.185 s CPU share: 99.23 % </pre> =={{header\|Perl}}== <~~lang~~syntaxhighlight lang="perl">use strict; use warnings; use List::Util 'first'; Line 436 ⟶ 1,214: my $e = first { 6$_ =~ /$n/ } 0..1000; printf "%7d: 6^%-3s %s\n", $n, $e, comma 6$e; }</~~lang~~syntaxhighlight> {{out}} <pre> 0: 6^9 10,077,696 Line 466 ⟶ 1,244: (Related recent task: [[Show_the_(decimal)_value_of_a_number_of_1s_appended_with_a_3,_then_squared#Phix]]) <!--<~~lang~~syntaxhighlight ~~Phix~~lang="phix">(phixonline)--> <span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">22</span> <span style="color: #000080;font-style:italic;">-- (tested to 10,000,000)</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> Line 512 ⟶ 1,290: <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">printf</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"%2d %29s = 6^%d\n"</span><span style="color: #0000FF;">},</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pwr</span><span style="color: #0000FF;">}),</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)})</span> <!--</~~lang~~syntaxhighlight>--> {{out}} Line 541 ⟶ 1,319: 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. =={{header\|~~Raku~~Python}}== <syntaxhighlight 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)))</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</pre> =={{header\|Quackery}}== ~~<lang perl6>use Lingua::EN::Numbers;~~ <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}}== <syntaxhighlight lang="raku" line>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; Line 552 ⟶ 1,424: sprintf "%3d: 6%-4s %s", $n, .&super, comma @po6[$_] given @po6.first: .contains($n), :k };</~~lang~~syntaxhighlight> {{out}} <pre> 0: 6⁹ 10,077,696 Line 579 ⟶ 1,451: =={{header\|REXX}}== <~~lang~~syntaxhighlight 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 6N / parse arg hi . /obtain optional argument from the CL./ Line 600 ⟶ 1,472: 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~~syntaxhighlight> {{out\|output\|text=  when using the default input:}} <pre> Line 631 ⟶ 1,503: =={{header\|Ring}}== <~~lang~~syntaxhighlight lang="ring"> load "stdlib.ring" Line 654 ⟶ 1,526: see "done..." + nl </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 684 ⟶ 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> 09 : 10077696 10 : 1 23 : 216 32 : 36 46 : 46656 56 : 46656 61 : 6 75 : 7776 812 : 2176782336 94 : 1296 109 : 10077696 1116 : 2821109907456 124 : 1296 1313 : 13060694016 1428 : 6140942214464815497216 1518 : 101559956668416 163 : 216 1710 : 60466176 1815 : 470184984576 1921 : 21936950640377856 2026 : 170581728179578208256 213 : 216 </pre> =={{header\|Wren}}== {{libheader\|Wren-big}} {{libheader\|Wren-fmt}} <~~lang~~syntaxhighlight ~~ecmascript~~lang="wren">import "./big" for BigInt import "./fmt" for Fmt System.print(" n smallest power of 6 which contains n") Line 702 ⟶ 1,711: i = i + 1 } }</~~lang~~syntaxhighlight> {{out}} Line 730 ⟶ 1,739: 21 6^3 = 216 </pre> =={{header\|Yabasic}}== {{trans\|Python}} <syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Smallest_power_of_6_whose_decimal_expansion_contains_n // by Galileo, 05/2022 sub smallest_six(n) local p, n$ n$ = str$(n) p = 1 while not instr(str$(p, "%1.f"), n$) p = p 6 : wend return p end sub for n = 0 to 21 : print n, ": ", str$(smallest_six(n), "%1.f") : next</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 ---Program done, press RETURN---</pre>