Narcissistic decimal number: Difference between revisions
Content added Content deleted
m (→{{header|AppleScript}}: Idiomatic: minor optimisation, rewritten preamble.) |
(→{{header|Phix}}: added faster version) |
||
Line 2,983: | Line 2,983: | ||
<pre> |
<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} |
{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> |
</pre> |
||