Alle Armstrong-Nummern

11

Eine Armstrong-Zahl (AKA Plus Perfect-Zahl oder narzisstische Zahl) ist eine Zahl, die der Summe der n-ten Potenz der Ziffern entspricht, wobei ndie Anzahl der Ziffern der Zahl ist.

Zum Beispiel 153hat 3Ziffern und 153 = 1^3 + 5^3 + 3^3, so 153ist eine Armstrong - Nummer.

Zum Beispiel 8208hat 4Ziffern und 8208 = 8^4 + 2^4 + 0^4 + 8^4, so 8208ist eine Armstrong - Nummer.

Am 14. November 2013 haben wir getestet, ob eine Nummer eine Armstrong-Nummer ist.

Nun möchten wir alle Armstrong-Nummern auflisten. Es gibt genau 88Armstrong-Nummern:

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

Ihre Aufgabe ist es, genau die obige Liste auszugeben.

Flexibilität

Das Trennzeichen muss kein Zeilenumbruch sein, aber das Trennzeichen darf keine Ziffer enthalten.

Ein nachfolgendes Trennzeichen am Ende der Ausgabe ist optional.

Außerdem muss Ihr Code vor dem Hitzetod des Universums in angemessener Zeit (z. B. weniger als einem Tag ) beendet werden.

Sie können das Ergebnis oder einen Teil davon fest codieren.

Verweise

Undichte Nonne
quelle
Verwandte: 4-perfekte Zahlen
Sp3000
Können mehrere Trennzeichen zwischen aufeinanderfolgenden Elementen gedruckt werden?
Mego
@Mego solange das Trennzeichen keine Ziffer enthält.
Undichte Nonne
Ist es aus Neugier formell bewiesen, dass es nur 88 von ihnen gibt, oder ist das nur, wie viele bisher bestätigt wurden?
Patrick Roberts
Linear ist hier keine Option, es sei denn, Ihre Sprache kann 10e33Anweisungen pro Sekunde ausführen .
Magic Octopus Urn

Antworten:

13

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

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

Die Ausführung auf meinem Computer dauert ungefähr viereinhalb Stunden. Eine Armstrong-Nummer ist fest codiert, die restlichen werden berechnet.

Die Berechnung aller Armstrong-Zahlen ist theoretisch in 24 Stunden möglich, aber der Ansatz

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

treibt die Müllsammelmuttern an. Bisher haben alle Einstellungen, die ich versucht habe, entweder zu einer GC-Fehlermeldung oder zu viel Speicherplatz geführt.

Wie es funktioniert

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.
Dennis
quelle
2
Es ist sehr beeindruckend, dass Sie dies 85%kürzer gemacht haben als das, womit Sie begonnen haben.
James
3
@ DrGreen Nun, das Zeitlimit wurde immer lockerer. Es hieß weniger als eine Minute, als ich anfing zu knacken, also war Hardcodierung so ziemlich die einzige Option. Jetzt, da wir einen Tag haben, hoffe ich, unter 50 Bytes zu kommen.
Dennis
1

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

Codiert die Anzahl der 0-9 in jeder Nummer.

Probieren Sie es online aus!

Undichte Nonne
quelle
0

Python 2 , 358 204 Bytes

-6 Bytes dank @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:]

Auf meinem Computer lief es in elfeinhalb Stunden.

Wie es funktioniert?

Nur eines ist fest codiert: Die Tatsache, dass ab 32 Ziffern alle Armstrong-Zahlen die Ziffern 0 bis 9 haben. Dies wird durch die Verwendung der Variablen Bim Code behandelt. Die Geschwindigkeit nimmt erheblich ab, da sich die Anzahl der Kombinationen stark verringert.

Felipe Nardi Batista
quelle
1
Pythons +Operator für Listen wird die Arbeit mit anderen Sequenzen definiert, so dass Sie ersetzen können , A+=[t]mit A+=t,zu speichern einem Byte.
Jonathan Frech
1
sortedwird dreimal angezeigt, sodass Sie alle Vorkommen durch ersetzen Zund definieren können Z=sorted.
Jonathan Frech
Da es sich um Python 2 handelt, können Sie Ihren for-loop-Einzug (4 Leerzeichen) durch eine Registerkarte ersetzen und weitere sechs Bytes speichern.
Jonathan Frech
@ JonathanFrech tist keine Sequenz, also kann ich nicht A+=t, ich habe Tabulatoren und Leerzeichen verwendet, um Bytes zu speichern. Es muss zurückgetauscht worden sein, als ich den Code früher kopiert habe, danke
Felipe Nardi Batista
@ JonathanFrech Ich habe Ihren Kommentar über die falsch verstanden A+t,. Ich habe das Komma dort nicht gesehen
Felipe Nardi Batista