Narcissistic decimal number: Difference between revisions
Content added Content deleted
(Added APL version) |
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
||
Line 3,420: | Line 3,420: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
string d = sprintf("%d",n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">narcissistic</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer l = length(d) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer sumn = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to l do |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">sumn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
sumn += power(d[i]-'0',l) |
|||
<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: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">sumn</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
return sumn=n |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">sumn</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence s = {} |
|||
integer n = 0 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
while length(s)<25 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
if narcissistic(n) then s &= n end if |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">25</span> <span style="color: #008080;">do</span> |
|||
n += 1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">narcissistic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
?s</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,445: | Line 3,448: | ||
At least 100 times faster, gets the first 47 (the native precision limit) before the above gets the first 25.<br> |
At least 100 times faster, gets the first 47 (the native precision limit) before the above gets the first 25.<br> |
||
I tried a gmp version, but it was 20-odd times slower, presumably because it uses that mighty sledgehammer for many small int cases. |
I tried a gmp version, but it was 20-odd times slower, presumably because it uses that mighty sledgehammer for many small int cases. |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>-- Begin with zero, which is narcissistic by definition and is never the only digit used in other numbers. |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
sequence output = {`0`} |
|||
<span style="color: #000080;font-style:italic;">-- Begin with zero, which is narcissistic by definition and is never the only digit used in other numbers.</span> |
|||
bool done = false |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">output</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">`0`</span><span style="color: #0000FF;">}</span> |
|||
integer m = 0 |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
integer q |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">q</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> |
|||
procedure recurse(sequence digits, atom powsum, integer rem) |
|||
-- Recursive subhandler. Builds lists containing m digit values while summing the digits' mth powers. |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">recurse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">powsum</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span> |
|||
-- If m digits have been obtained, compare the sum of powers's digits with the values in the list. |
|||
<span style="color: #000080;font-style:italic;">-- Recursive subhandler. Builds lists containing m digit values while summing the digits' mth powers. |
|||
-- Otherwise continue branching the recursion to derive longer lists. |
|||
-- If m digits have been obtained, compare the sum of powers's digits with the values in the list. |
|||
if rem=0 then |
|||
-- Otherwise continue branching the recursion to derive longer lists.</span> |
|||
atom temp = powsum |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
integer unmatched = m |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">powsum</span> |
|||
while temp do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">unmatched</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span> |
|||
integer d = find(remainder(temp,10),digits) |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">temp</span> <span style="color: #008080;">do</span> |
|||
if d=0 then exit end if |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> |
|||
digits[d] = -1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
unmatched -= 1 |
|||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> |
|||
temp = floor(temp/10) |
|||
<span style="color: #000000;">unmatched</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
end while |
|||
<span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
-- If all the digits have been matched, the sum of powers is narcissistic. |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
if unmatched=0 then |
|||
<span style="color: #000080;font-style:italic;">-- If all the digits have been matched, the sum of powers is narcissistic.</span> |
|||
output = append(output,sprintf("%d",powsum)) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">unmatched</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
if length(output)=q then done = true end if |
|||
<span style="color: #000000;">output</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">output</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">powsum</span><span style="color: #0000FF;">))</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">output</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">q</span> <span style="color: #008080;">then</span> <span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
else |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
-- If fewer than m digits at this level, derive longer lists from the current one. |
|||
<span style="color: #008080;">else</span> |
|||
-- Adding only values that are less than or equal to the last one makes each |
|||
<span style="color: #000080;font-style:italic;">-- If fewer than m digits at this level, derive longer lists from the current one. |
|||
-- collection unique and turns up the narcissistic numbers in numerical order. |
|||
-- Adding only values that are less than or equal to the last one makes each |
|||
-- |
|||
-- collection unique and turns up the narcissistic numbers in numerical order. |
|||
-- ie/eg if sum(sq_power({9,7,4,4},4))==9474, and as shown sort(digits)==list, |
|||
-- |
|||
-- then 9474 is the one and only permutation that is narcissistic, obviously, |
|||
-- ie/eg if sum(sq_power({9,7,4,4},4))==9474, and as shown sort(digits)==list, |
|||
-- and there is no point looking at any other permutation of that list, ever. |
|||
-- |
-- then 9474 is the one and only permutation that is narcissistic, obviously, |
||
-- and there is no point looking at any other permutation of that list, ever. |
|||
-- the 999 four-digit numbers beginning 1 that might otherwise be checked, |
|||
-- |
-- Also 1000,1100,1110,1111 are the only 4 lists beginning 1, as opposed to |
||
-- |
-- the 999 four-digit numbers beginning 1 that might otherwise be checked, |
||
-- |
-- and likewise 9000..9999 is actually just 220 rather than the full 999. |
||
-- (I can see that exploring smaller partial sums first will tend to issue |
|||
-- |
|||
-- results in numeric order, but cannot see an absolute certainty of that) |
|||
for d=0 to digits[$] do |
|||
--</span> |
|||
recurse(digits & d, powsum + power(d,m), rem-1) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[$]-</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">do</span> |
|||
if done then exit end if |
|||
<span style="color: #000000;">recurse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">powsum</span> <span style="color: #0000FF;">+</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">done</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
function narcissisticDecimalNumbers(integer qp) |
|||
atom t1 = time()+1 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">narcissisticDecimalNumbers</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">qp</span><span style="color: #0000FF;">)</span> |
|||
q = qp |
|||
<span style="color: #004080;">atom</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> |
|||
-- Initiate the recursive building and testing of collections of increasing numbers of digit values. |
|||
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">qp</span> |
|||
while not done do |
|||
<span style="color: #000080;font-style:italic;">-- Initiate the recursive building and testing of collections of increasing numbers of digit values.</span> |
|||
m += 1 |
|||
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">done</span> <span style="color: #008080;">do</span> |
|||
if m > iff(machine_bits()=32?16:17) then |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
output = append(output,"Remaining numbers beyond number precision") |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">></span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">16</span><span style="color: #0000FF;">:</span><span style="color: #000000;">17</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
done = true |
|||
<span style="color: #000000;">output</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">output</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Remaining numbers beyond number precision"</span><span style="color: #0000FF;">)</span> |
|||
else |
|||
<span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
for digit=1 to 9 do |
|||
<span style="color: #008080;">else</span> |
|||
recurse({digit}, power(digit,m), m-1) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
if done then exit end if |
|||
<span style="color: #000000;">recurse</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">&</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">done</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if not done and time()>t1 then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"searching... %d found, length %d, %s\n", |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">done</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;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span> |
|||
{length(output),m,elapsed(time()-t0)}) |
|||
<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;">"searching... %d found, length %d, %s\n"</span><span style="color: #0000FF;">,</span> |
|||
t1 = time()+1 |
|||
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">output</span><span style="color: #0000FF;">),</span><span style="color: #000000;">m</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> |
|||
end if |
|||
<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> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return output |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">output</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence r = narcissisticDecimalNumbers(iff(machine_bits()=32?44:47)) |
|||
pp(r) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">narcissisticDecimalNumbers</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">44</span><span style="color: #0000FF;">:</span><span style="color: #000000;">47</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"found %d in %s\n",{length(r),elapsed(time()-t0)})</lang> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</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;">"found %d in %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</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> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |