Narcissistic decimal number: Difference between revisions
→{{header|Phix}}: added faster version
m (→{{header|AppleScript}}: Idiomatic: minor optimisation, rewritten preamble.) |
(→{{header|Phix}}: added faster version) |
||
Line 2,983:
<pre>
{0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084,548834,1741725,4210818,9800817,9926315}
</pre>
=== faster ===
{{trans|AppleScript}}
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>-- Begin with zero, which is narcissistic by definition and is never the only digit used in other numbers.
sequence output = {`0`}
bool done = false
integer m = 0
integer q
atom t0 = time()
procedure recurse(sequence digits, atom powsum, integer rem)
-- Recursive subhandler. Builds lists containing m digit values while summing the digits' mth powers.
-- If m digits have been obtained, compare the sum of powers's digits with the values in the list.
-- Otherwise continue branching the recursion to derive longer lists.
if rem=0 then
atom temp = powsum
integer unmatched = m
while temp do
integer d = find(remainder(temp,10),digits)
if d=0 then exit end if
digits[d] = -1
unmatched -= 1
temp = floor(temp/10)
end while
-- If all the digits have been matched, the sum of powers is narcissistic.
if unmatched=0 then
output = append(output,sprintf("%d",powsum))
if length(output)=q then done = true end if
end if
else
-- If fewer than m digits at this level, derive longer lists from the current one.
-- 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,
-- and there is no point looking at any other permutation of that list, ever.
-- 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
recurse(digits & d, powsum + power(d,m), rem-1)
if done then exit end if
end for
end if
end procedure
function narcissisticDecimalNumbers(integer qp)
atom t1 = time()+1
q = qp
-- Initiate the recursive building and testing of collections of increasing numbers of digit values.
while not done do
m += 1
if m > iff(machine_bits()=32?16:17) then
output = append(output,"Remaining numbers beyond number precision")
done = true
else
for digit=1 to 9 do
recurse({digit}, power(digit,m), m-1)
if done then exit end if
end for
if not done and time()>t1 then
printf(1,"searching... %d found, length %d, %s\n",
{length(output),m,elapsed(time()-t0)})
t1 = time()+1
end if
end if
end while
return output
end function
sequence r = narcissisticDecimalNumbers(iff(machine_bits()=32?44:47))
pp(r)
printf(1,"found %d in %s\n",{length(r),elapsed(time()-t0)})</lang>
{{out}}
<pre>
searching... 41 found, length 13, 1.0s
searching... 42 found, length 15, 3.3s
searching... 44 found, length 16, 5.7s
{`0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`, `153`, `370`, `371`,
`407`, `1634`, `8208`, `9474`, `54748`, `92727`, `93084`, `548834`,
`1741725`, `4210818`, `9800817`, `9926315`, `24678050`, `24678051`,
`88593477`, `146511208`, `472335975`, `534494836`, `912985153`,
`4679307774`, `32164049650`, `32164049651`, `40028394225`, `42678290603`,
`44708635679`, `49388550606`, `82693916578`, `94204591914`,
`28116440335967`, `4338281769391370`, `4338281769391371`,
`21897142587612075`, `35641594208964132`, `35875699062250035`}
found 47 in 8.2s
</pre>
| |||