12
\$\begingroup\$

An Armstrong number (AKA Plus Perfect number, or narcissistic number) is a number which is equal to its sum of n-th power of the digits, where n is the number of digits of the number.

For example, 153 has 3 digits, and 153 = 1^3 + 5^3 + 3^3, so 153 is an Armstrong number.

For example, 8208 has 4 digits, and 8208 = 8^4 + 2^4 + 0^4 + 8^4, so 8208 is an Armstrong number.

On 14th Nov 2013, we tested if a number is an Armstrong number.

Now, we would like to list all Armstrong numbers. There are exactly 88 Armstrong numbers:

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 1517841543307505039 3289582984443187032 4498128791164624869 4929273885928088826 63105425988599693916 128468643043731391252 449177399146038697307 21887696841122916288858 27879694893054074471405 27907865009977052567814 28361281321319229463398 35452590104031691935943 174088005938065293023722 188451485447897896036875 239313664430041569350093 1550475334214501539088894 1553242162893771850669378 3706907995955475988644380 3706907995955475988644381 4422095118095899619457938 121204998563613372405438066 121270696006801314328439376 128851796696487777842012787 174650464499531377631639254 177265453171792792366489765 14607640612971980372614873089 19008174136254279995012734740 19008174136254279995012734741 23866716435523975980390369295 1145037275765491025924292050346 1927890457142960697580636236639 2309092682616190307509695338915 17333509997782249308725103962772 186709961001538790100634132976990 186709961001538790100634132976991 1122763285329372541592822900204593 12639369517103790328947807201478392 12679937780272278566303885594196922 1219167219625434121569735803609966019 12815792078366059955099770545296129367 115132219018763992565095597973971522400 115132219018763992565095597973971522401

Your task is to output exactly the list above.

Flexibility

The separator does not have to be be a line-break, but the separator must not contain any digit.

A trailing separator at the end of the output is optional.

Also, your code must terminate before the heat death of the universe in a reasonable amount of time (say, less than a day).

You may hard-code the result or any part thereof.

References

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Related: 4-perfect numbers \$\endgroup\$ Commented Jun 19, 2016 at 2:58
  • \$\begingroup\$ Can multiple separators be printed between successive elements? \$\endgroup\$ Commented Jun 20, 2016 at 8:09
  • \$\begingroup\$ @Mego as long as the separator does not contain any digit. \$\endgroup\$ Commented Jun 20, 2016 at 8:22
  • \$\begingroup\$ Just out of curiosity, is it formally proven that there are only 88 of them, or is that just how many have been confirmed so far? \$\endgroup\$ Commented Jun 20, 2016 at 18:45
  • \$\begingroup\$ Linear isn't an option here unless your language can execute 10e33 instructions per second. \$\endgroup\$ Commented Sep 15, 2017 at 20:31

3 Answers 3

Reset to default
13
\$\begingroup\$

CJam, 626 397 325 218 168 134 93 55 54 53 bytes

8A#{[_8b3394241224Ab?A0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

Execution takes roughly four and a half hours on my machine. One Armstrong number is hardcoded, the remaining ones are computed.

Computing all Armstrong numbers is theoretically possible in 24 hours, but the approach

9A#{_9b8 9erA0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

drives the garbage collector nuts. So far, all settings I've tried resulting either in a GC error message or too much memory consumption.

How it works

8A# e# Compute 8¹⁰ = 1,073,741,824. { e# Map the following block over all I in [0 ... 1,073,741,824]. [ e# Begin an array. _8b e# Copy I and convert the copy to base 8. 3394241224Ab e# Push [3 3 9 4 2 4 1 2 2 4], the representation of the e# Armstrong number 1122763285329372541592822900204593. ? e# If I is non-zero, select the array of base 8 digits. e# Otherwise, select the hardcoded representation. A0e[ e# Left-pad the digit array with 0's to length 10. A, e# Push [0 1 2 3 4 5 6 7 8 9]. ] e# End the array. ze~ e# Transpose and perform run-length decoding, repeating the e# digit n k times, where k in the n-th entry of the repr. e# This is a potential Armstrong number, with sorted digits. _ e# Push a copy. _, e# Compute the length of yet another copy. f# e# Elevate all digits to that power. :+s e# Add the results and cast to string. _$ e# Push a sorted copy. @s e# Stringify the sorted digits. =* e# Compare for equality and repeat the string that many times. e# This pushes either the representation of an Armstong number e# or an empty string. ~ e# Evaluate, pushing the number or doing nothing. }% e# $1> e# Sort and remove the lowest number (0). N* e# Join, separating by linefeeds.
Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ It's very impressive that you made this 85% shorter than what you started with. \$\endgroup\$ Commented Jun 19, 2016 at 23:26
  • 3
    \$\begingroup\$ @DrGreen Well, the time limit kept getting relaxed. It said under a minute when I started cracking, so hardcoding was pretty much the only option. Now that we have a day, I hope to get under 50 bytes. \$\endgroup\$ Commented Jun 20, 2016 at 1:04
1
\$\begingroup\$

Pyth, 330 bytes

0000000: 6a 6d 73 2e 65 2a 73 62 5e 6b 73 73 4d 64 64 63 jms.e*sb^kssMddc 0000010: 2e 5a 22 78 da ad 50 51 76 03 30 08 ba 52 04 4d .Z"x..PQv.0..R.M 0000020: de ee 7f b1 81 26 dd f6 bf f6 35 35 28 08 59 b1 .....&....55(.Y. 0000030: 3e 9f 7f 2e e7 3b 68 ac f7 8b 3f c0 c5 e2 57 73 >....;h...?...Ws 0000040: 2d bc f3 02 e8 89 8b a3 eb be cf a1 ae 3b 33 84 -............;3. 0000050: 01 66 1a 23 d7 40 8c 06 d0 eb e6 fa aa 96 12 17 .f.#.@.......... 0000060: 11 bc f8 d0 e0 6d 96 e2 d0 f1 b3 41 c7 8a 74 19 .....m.....A..t. 0000070: 3d b8 fc 77 2b 2c ce 88 05 86 d6 9e d5 f5 4c 37 =..w+,........L7 0000080: b0 9e ab 46 75 a1 37 f1 5d 5b 36 dd 86 e5 6e 15 ...Fu.7.][6...n. 0000090: a4 09 b4 0c 40 a7 01 1d 2a 8d a8 49 e4 ac 23 1d ....@...*..I..#. 00000a0: 25 c5 55 53 02 be 66 c7 dd bd c3 4a 28 9d 39 57 %.US..f....J(.9W 00000b0: 6f 11 92 ca 94 8a a5 87 38 4e 1d 25 17 60 3a 2d o.......8N.%.`:- 00000c0: 51 5a 96 55 7e 04 7a 41 aa b1 84 c4 88 10 fd 28 QZ.U~.zA.......( 00000d0: 04 37 64 68 ab 58 1e 0c 66 99 de a6 4c 34 2e 51 .7dh.X..f...L4.Q 00000e0: 19 96 fc a7 ea 01 6d de b4 2b 59 01 52 1b 1c 6e ......m..+Y.R..n 00000f0: 92 eb 38 5c 22 68 6f 69 60 e9 ab 17 60 6e e9 6b ..8\"hoi`...`n.k 0000100: 44 d6 52 44 33 fd 72 c9 7a 95 28 b2 a8 91 12 88 D.RD3.r.z.(..... 0000110: 74 0a 7b 10 59 16 ab 44 5a 4e d8 17 e5 d8 a8 a3 t.{.Y..DZN...... 0000120: 97 09 27 d9 7b bf 8a fc ca 6b 2a a5 11 28 89 09 ..'.{....k*..(.. 0000130: 76 3a 19 3a 93 3b b6 2d eb 2c 9c dc 45 a9 65 1c v:.:.;.-.,..E.e. 0000140: f9 be d5 37 27 6e aa cf 22 54 ...7'n.."T

Encodes the count of the number of 0-9 in each number.

Ÿ.ç;h¬÷‹?ÀÅâWs-¼ó艋£ë¾Ï¡®;3„f#×@ŒÐëæúª–¼øÐàm–âÐñ³ANJt=¸üw+,Έ†ÖžÕõL7°ž«Fu¡7ñ][6݆ån¤ ´ @§*¨Iä¬#%ÅUS¾fÇݽÃJ(9Wo’Ê”Š¥‡8N%`:-QZ–U~zAª±„Ĉý(7dh«X f™Þ¦L4.Q–ü§êmÞ´+YRn’ë8\"hoi`é«`nékDÖRD3ýrÉz•(²¨‘ˆt{Y«DZNØåب£— 'Ù{¿ŠüÊk*¥(‰ v::“;¶-ë,œÜE©eù¾Õ7'nªÏ"T&debug=0" rel="nofollow noreferrer">Try it online!

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

Python 2, 358 204 bytes

-6 bytes thanks to @JonathanFrech

from itertools import* R=range S=sorted A=[] for i in R(40): B=(i>31)*10 for c in combinations_with_replacement(R(10),i-B):t=sum(d**i for d in c);A+=[t]*(S(map(int,str(t)))==S(S(c)+R(B))) print S(A)[1:]

In my computer, it ran in 11 and a half hours.

How it works?

Only one thing is hardcoded, the fact that from 32 digits onwards, all armstrong numbers have the digits 0 to 9. This is handled by the uses of the variable B in the code. It's speed goes down significantly as the number of combinations reduces a lot.

Improve this answer
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Python's + operator for lists is defined to work with other sequences, so you can replace A+=[t] with A+=t, to save a byte. \$\endgroup\$ Commented Sep 16, 2017 at 7:50
  • 1
    \$\begingroup\$ sorted appears three times, so you can replace all occurences with Z and define Z=sorted. \$\endgroup\$ Commented Sep 16, 2017 at 7:54
  • \$\begingroup\$ Since it is Python 2, you can replace your for-loop indentation (4 spaces) with one tab and save another six bytes. \$\endgroup\$ Commented Sep 16, 2017 at 7:57
  • \$\begingroup\$ @JonathanFrech t is not a sequence, so i can't do A+=t, i was using tabs and spaces to save bytes, it must have exchanged back when i copied the code earlier, thanks \$\endgroup\$ Commented Sep 16, 2017 at 11:21
  • \$\begingroup\$ @JonathanFrech i misread your comment about the A+t,. i didn't see the comma there \$\endgroup\$ Commented Sep 16, 2017 at 11:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.