Rosetta Code

Narcissistic decimal number: Difference between revisions

Page Discussion

Narcissistic decimal number (view source)

Revision as of 19:00, 24 February 2022

15,977 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
(Added APL version)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 3,420:
 
=={{header|Phix}}==
<!--<lang Phix>function narcissistic(integer nphixonline)-->
<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}}
<pre>
Line 3,445 ⟶ 3,448:
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.
<!--<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.
-- Alsothen 1000,1100,1110,11119474 areis the one and only 4permutation liststhat beginningis 1narcissistic, as opposed to 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,
-- andAlso likewise1000,1100,1110,1111 9000..9999are isthe actuallyonly just4 220lists ratherbeginning than1, theas opposed fullto 999.
-- (Ithe can999 seefour-digit thatnumbers exploringbeginning smaller1 partial sums firstthat willmight tendotherwise tobe issuechecked,
-- and results inlikewise numeric9000..9999 order,is butactually cannotjust see220 anrather absolutethan certaintythe offull that)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}}
<pre>
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/241371"