Smallest numbers: Difference between revisions
(→{{header|Ring}}: also wrong) |
(→{{header|Phix}}: added gmp version) |
||
Line 57: | Line 57: | ||
</pre> |
</pre> |
||
Testing to 1,000,000 took 12mins 35s. |
Testing to 1,000,000 took 12mins 35s. |
||
===gmp version=== |
|||
<!--<lang Phix>--> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">51</span> <span style="color: #000080;font-style:italic;">-- (tested to 1,000,000)</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #7060A8;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #7060A8;">mpz</span> <span style="color: #000000;">zkk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</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> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">found</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zkk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">kk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zkk</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">kk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">and</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</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: #008080;">then</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">found</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"found %,d/%,d, at %d^%d which has %,d digits (%s)"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">found</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kk</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</span> |
|||
<!--</lang>--> |
|||
Same results, but nearly 30 times faster, finishing the 1,000,000 test in just 26.6s |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
Revision as of 05:26, 11 April 2021
- Task
Smallest number k > 0 such that the decimal expansion of k^k contains n, where n < 51
Phix
Native numbers won't cope, so instead of gmp I've gone with string math again. (Related recent tasks: here and here)
constant lim = 51 -- (tested to 1,000,000) atom t0 = time(), t1 = t0+1 sequence res = repeat(0,lim) integer found = 0, k = 1 while found<lim do string kk = "1" for i=1 to k do integer carry = 0 for j=length(kk) to 1 by -1 do integer digit = (kk[j]-'0')*k+carry kk[j] = remainder(digit,10)+'0' carry = floor(digit/10) end for while carry do kk = remainder(carry,10)+'0' & kk carry = floor(carry/10) end while end for for i=1 to length(kk) do integer digit = 0, j = i while j<=length(kk) and digit<=lim do digit = digit*10+kk[j]-'0' if digit<lim and res[digit+1]=0 then res[digit+1] = sprintf("%2d",k) found += 1 end if j += 1 end while end for if platform()!=JS and time()>t1 then progress("found %,d/%,d, at %d^%d which has %,d digits (%s)", {found,lim,k,k,length(kk),elapsed(time()-t0)}) t1 = time()+1 end if k += 1 end while puts(1,join_by(shorten(res,"",30),1,10))
- Output:
9 1 3 5 2 4 4 3 7 9 10 11 5 19 22 26 8 17 16 19 9 8 13 7 17 4 17 3 11 18 13 5 23 17 18 7 17 15 9 18 16 17 9 7 12 28 6 23 9 24 23
Testing to 1,000,000 took 12mins 35s.
gmp version
constant lim = 51 -- (tested to 1,000,000) include mpfr.e mpz zkk = mpz_init() atom t0 = time(), t1 = t0+1 sequence res = repeat(0,lim) integer found = 0, k = 1 while found<lim do mpz_ui_pow_ui(zkk,k,k) string kk = mpz_get_str(zkk) for i=1 to length(kk) do integer digit = 0, j = i while j<=length(kk) and digit<=lim do digit = digit*10+kk[j]-'0' if digit<lim and res[digit+1]=0 then res[digit+1] = sprintf("%2d",k) found += 1 end if j += 1 end while end for if platform()!=JS and time()>t1 then progress("found %,d/%,d, at %d^%d which has %,d digits (%s)", {found,lim,k,k,length(kk),elapsed(time()-t0)}) t1 = time()+1 end if k += 1 end while puts(1,join_by(shorten(res,"",30),1,10))
Same results, but nearly 30 times faster, finishing the 1,000,000 test in just 26.6s
Raku
<lang perl6>sub smallest ( $n ) {
state @powers = , |map { $_ ** $_ }, 1 .. *;
return @powers.first: :k, *.contains($n);
}
.say for (^51).map(&smallest).batch(10)».fmt('%2d');</lang>
- Output:
( 9 1 3 5 2 4 4 3 7 9) (10 11 5 19 22 26 8 17 16 19) ( 9 8 13 7 17 4 17 3 11 18) (13 5 23 17 18 7 17 15 9 18) (16 17 9 7 12 28 6 23 9 24) (23)
REXX
<lang rexx>/*REXX pgm finds the smallest positive integer K where K**K contains N, N < 51 */ numeric digits 200 /*ensure enough decimal digs for k**k */ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 51 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ w= 6 /*width of a number in any column. */ @spiKK=' smallest positive integer K where K**K contains N, 0 ≤ N < ' commas(hi) say ' N │'center(@spiKK, 5 + cols*(w+1) ) /*display the title of the output. */ say '─────┼'center("" , 5 + cols*(w+1), '─') /* " " separator " " " */ $=; idx= 0 /*define $ output list; index to 0.*/
do j=0 for hi; n= j + 1 /*look for a power of 6 that contains N*/ do k=1 until pos(j, k**k)>0 /*calculate a bunch of powers (K**K). */ end /*k*/ c= commas(k) /*maybe add commas to the powe of six. */ $= $ right(c, max(w, length(c) ) ) /*add a K (power) ──► list, allow big#*/ if n//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 5)'│'substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 5)"│"substr($,2) /*possible display any residual output.*/ say '─────┴'center("" , 5 + cols*(w+1), '─') /* " " 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 inputs:
N │ smallest positive integer K where K**K contains N, 0 ≤ N < 51 ─────┼─────────────────────────────────────────────────────────────────────────── 0 │ 9 1 3 5 2 4 4 3 7 9 10 │ 10 11 5 19 22 26 8 17 16 19 20 │ 9 8 13 7 17 4 17 3 11 18 30 │ 13 5 23 17 18 7 17 15 9 18 40 │ 16 17 9 7 12 28 6 23 9 24 50 │ 23 ─────┴───────────────────────────────────────────────────────────────────────────
Ring
<lang ring> load "stdlib.ring"
decimals(0) see "working..." + nl see "Smallest number k > 0 such that the decimal expansion of k^k contains n are:" + nl
row = 0 limit1 = 49 limit2 = 30
for n = 0 to limit1
strn = string(n) for m = 1 to limit2 powm = pow(m,m) strm = string(powm) ind = substr(strm,strn) if ind > 0 exit ok next row = row + 1 see "" + m + " " if row%10 = 0 see nl ok
next
see "done..." + nl </lang>
- Output:
working... Smallest number k > 0 such that the decimal expansion of k^k contains n are: 9 1 3 5 2 4 4 3 7 9 10 11 5 19 21 18 8 25 16 19 9 8 13 7 17 4 17 3 11 18 13 5 19 17 18 7 17 15 9 15 16 18 9 7 12 25 6 23 9 23 done...