Dass es nicht unendlich viele Lösungen geben kann läßt sich einfach zeigen:
Nehmen wir an, wir würden nur die Ziffer '9' verwenden. Dann gilt:
Die Summe = n * 9 ^ n muss mindestens n Stellen im Dezimalsystem haben.
Man kann nun zeigen, dass bei n>60 dies nicht mehr möglich ist:
mit n=61 ergibt sich die Summe als 9.8655865e+59. Also keine 61 stellige Zahl.
Dass nun nur 88 Zahlen möglich sind, ja dafür braucht es einen Computer, welcher alle Möglichkeiten bis n=60 versucht.
Ab n>39 bis n=60 gibt es noch viel zu testen, aber keine Lösung mehr!
Berechnung, aber wie?
Hier gibt es folgende Herausforderungen:
Die Zahlen werden groß und Standard Typen wie integer reichen nicht weit.
int +2 147 483 647
long +9 223 372 036 854 775 807
Die Anzahl der Kombinationen steigt drastisch mit jeder weiteren Ziffer.
Ein brutal-force Ansatz würde für n-stelllige Zahl 10^n Kombinationen testen.
Selbst bei sehr flotten 10^9 Prüfungen pro Sekunde kommt man sehr schnell an Grenzen:
n-stellig
Sekunden
Stunden
Tage
10
10
11
100
12
1000
0.28
13
2.78
14
27.8
15
278
11.6
16
116
Zum Vergleich: Das Alter der Welt seit dem Urknall wird aktuell mit (4.354±0.012)×10^17 Sekunden angegeben.
Wir bräuchten aber 10^30 Sekunden um die 39 stellige Zahl zu finden!
Mögliche Ansätze sind:
BigInteger anstelle von large (64Bit) kann 'beliebig' große Zahlen handlen.
Allerdings steigt damit die Rechenzeit an, je größer die Zahlen werden.
Man versucht cut-off Bedingungen zu finden, damit nicht alle Kombinationen getestet werden.
Wir definieren Abbruchbedinungen für die größte / kleinsten Zahlen.
So kann beispielsweise die Tiefensuche abgebrochen werden, wenn die Summe der Potenzen die Zahl der Stellen der Dezimalzahl überschreitet.
Permutation
Jede Potenzsumme hat weitere Permutationen. So gibt es bei 1³ + 5³ + 3³ =153 auch weitere 5 Summenbildungen mit 153 durch vertauchen der Summanden.
Also 1³ + 3³ + 5³ == 3³ + 5³ + 1³ == 3³ + 1³ + 5³ == 5³ + 3³ + 1³ == 5³ + 1³ + 3³
Es reicht also vollkommen, nur eine Kombination zu prüfen. Nehmen wir 5³ + 3³ + 1³ und bilden die Summe, dann sehen wir, das die Summe exakt die gleiche Anzahl an Ziffern verwendet.
Bsp. für 20 stellige Zahlen mit den ersten 3 links stehenden Ziffern. Es gilt die weiter rechts stehende Ziffer ist maximal so groß wie die links stehende.
Anzahl führender Ziffern '9'
Vor allem bei großen Zahlen ist es notwendig, viele '9' zu verwenden.
bei 39 stelliger Zahl ist es so, dass 5 mal die Ziffer '9' nicht reicht, selbst wenn alle anderen Zahlen eine '8' wären:
5 * 9^39 + (39-5) * 8 ^39 = 8.7 E37
Diese Kriterium reduziert die Rechenzeit vor allem bei extrem großen Zahlen hefig:
So werden bei 60 stelliger Zahl nur noch 715 Kombinationen untersucht, da die ersten 56 stellen mit der Ziffer '9' zu besetzen sind.
die 2 Lösungen für 39 stelliger Zahl zu finden erfordert noch immer 445891810 zu untersuchende Kombinationen.
Lösungen
Diese wurde als single thread auf dem PI gefunden, eine Lösung nach der anderen.
Diese wurde als concurrend thread auf dem Intel I5 PCgefunden.
Last modified: 2022-03-12 16:49:11.
Welcome to 'Narzistische Zahlen' V 1.2
Suche Loesungen mit 1 bis 60 Stellen.
Diese n-stelligen Zahlen entsprechen der Summe der n-ten Potenz ihrer Ziffern.
Start, using 6 CPU for calculation!
Operating system Name: Windows 10
Intel64 Family 6 Model 158 Stepping 10, GenuineIntel
1 stellige Zahlen: 0.002 seconds
---------------------------------------
combinations=10; tried=10
9^1 = 9
8^1 = 8
7^1 = 7
6^1 = 6
5^1 = 5
4^1 = 4
3^1 = 3
2^1 = 2
1^1 = 1
0^1 = 0
2 stellige Zahlen: 0.002 seconds
---------------------------------------
combinations=55; tried=41
3 stellige Zahlen: 0.007 seconds
---------------------------------------
combinations=220; tried=150
4^3 + 0^3 + 7^3 = 407
3^3 + 7^3 + 1^3 = 371
3^3 + 7^3 + 0^3 = 370
1^3 + 5^3 + 3^3 = 153
5 stellige Zahlen: 0.02 seconds
---------------------------------------
combinations=2002; tried=1329
9^5 + 3^5 + 0^5 + 8^5 + 4^5 = 93084
9^5 + 2^5 + 7^5 + 2^5 + 7^5 = 92727
5^5 + 4^5 + 7^5 + 4^5 + 8^5 = 54748
6 stellige Zahlen: 0.046 seconds
---------------------------------------
combinations=5005; tried=3259
5^6 + 4^6 + 8^6 + 8^6 + 3^6 + 4^6 = 548834
4 stellige Zahlen: 0.142 seconds
---------------------------------------
combinations=715; tried=479
9^4 + 4^4 + 7^4 + 4^4 = 9474
8^4 + 2^4 + 0^4 + 8^4 = 8208
1^4 + 6^4 + 3^4 + 4^4 = 1634
60 stellige Zahlen: 0.346 seconds
---------------------------------------
combinations=715; tried=715; using digit '9' at least 56 times
7 stellige Zahlen: 0.348 seconds
---------------------------------------
combinations=11440; tried=7496
9^7 + 9^7 + 2^7 + 6^7 + 3^7 + 1^7 + 5^7 = 9926315
9^7 + 8^7 + 0^7 + 0^7 + 8^7 + 1^7 + 7^7 = 9800817
4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7 = 4210818
1^7 + 7^7 + 4^7 + 1^7 + 7^7 + 2^7 + 5^7 = 1741725
8 stellige Zahlen: 0.928 seconds
---------------------------------------
combinations=24310; tried=16131
8^8 + 8^8 + 5^8 + 9^8 + 3^8 + 4^8 + 7^8 + 7^8 = 88593477
2^8 + 4^8 + 6^8 + 7^8 + 8^8 + 0^8 + 5^8 + 1^8 = 24678051
2^8 + 4^8 + 6^8 + 7^8 + 8^8 + 0^8 + 5^8 + 0^8 = 24678050
10 stellige Zahlen: 1.337 seconds
---------------------------------------
combinations=92378; tried=61980
4^10 + 6^10 + 7^10 + 9^10 + 3^10 + 0^10 + 7^10 + 7^10 + 7^10 + 4^10 = 4679307774
9 stellige Zahlen: 2.419 seconds
---------------------------------------
combinations=48620; tried=32697
9^9 + 1^9 + 2^9 + 9^9 + 8^9 + 5^9 + 1^9 + 5^9 + 3^9 = 912985153
5^9 + 3^9 + 4^9 + 4^9 + 9^9 + 4^9 + 8^9 + 3^9 + 6^9 = 534494836
4^9 + 7^9 + 2^9 + 3^9 + 3^9 + 5^9 + 9^9 + 7^9 + 5^9 = 472335975
1^9 + 4^9 + 6^9 + 5^9 + 1^9 + 1^9 + 2^9 + 0^9 + 8^9 = 146511208
59 stellige Zahlen: 4.062 seconds
---------------------------------------
combinations=24310; tried=24310; using digit '9' at least 51 times
12 stellige Zahlen: 4.563 seconds
---------------------------------------
combinations=293930; tried=191534
11 stellige Zahlen: 4.791 seconds
---------------------------------------
combinations=167960; tried=111035
9^11 + 4^11 + 2^11 + 0^11 + 4^11 + 5^11 + 9^11 + 1^11 + 9^11 + 1^11 + 4^11 = 94204591914
8^11 + 2^11 + 6^11 + 9^11 + 3^11 + 9^11 + 1^11 + 6^11 + 5^11 + 7^11 + 8^11 = 82693916578
4^11 + 9^11 + 3^11 + 8^11 + 8^11 + 5^11 + 5^11 + 0^11 + 6^11 + 0^11 + 6^11 = 49388550606
4^11 + 4^11 + 7^11 + 0^11 + 8^11 + 6^11 + 3^11 + 5^11 + 6^11 + 7^11 + 9^11 = 44708635679
4^11 + 2^11 + 6^11 + 7^11 + 8^11 + 2^11 + 9^11 + 0^11 + 6^11 + 0^11 + 3^11 = 42678290603
4^11 + 0^11 + 0^11 + 2^11 + 8^11 + 3^11 + 9^11 + 4^11 + 2^11 + 2^11 + 5^11 = 40028394225
3^11 + 2^11 + 1^11 + 6^11 + 4^11 + 0^11 + 4^11 + 9^11 + 6^11 + 5^11 + 1^11 = 32164049651
3^11 + 2^11 + 1^11 + 6^11 + 4^11 + 0^11 + 4^11 + 9^11 + 6^11 + 5^11 + 0^11 = 32164049650
14 stellige Zahlen: 5.391 seconds
---------------------------------------
combinations=817190; tried=531179
2^14 + 8^14 + 1^14 + 1^14 + 6^14 + 4^14 + 4^14 + 0^14 + 3^14 + 3^14 + 5^14 + 9^14 + 6^14 + 7^14 = 28116440335967
13 stellige Zahlen: 9.045 seconds
---------------------------------------
combinations=497420; tried=322783
15 stellige Zahlen: 15.247 seconds
---------------------------------------
combinations=1307504; tried=850355
16 stellige Zahlen: 21.958 seconds
---------------------------------------
combinations=2042975; tried=1334478
4338281769391371
4338281769391370
58 stellige Zahlen: 30.311 seconds
---------------------------------------
combinations=293930; tried=293930; using digit '9' at least 46 times
17 stellige Zahlen: 34.669 seconds
---------------------------------------
combinations=3124550; tried=2007380
35875699062250035
35641594208964132
21897142587612075
18 stellige Zahlen: 55.974 seconds
---------------------------------------
combinations=4686825; tried=3081727
19 stellige Zahlen: 92.421 seconds
---------------------------------------
combinations=6906900; tried=4631973
4929273885928088826
4498128791164624869
3289582984443187032
1517841543307505039
20 stellige Zahlen: 126.744 seconds
---------------------------------------
combinations=10015005; tried=6789917
63105425988599693916
57 stellige Zahlen: 175.344 seconds
---------------------------------------
combinations=2042975; tried=2042975; using digit '9' at least 41 times
21 stellige Zahlen: 181.442 seconds
---------------------------------------
combinations=14307150; tried=9847044
449177399146038697307
128468643043731391252
22 stellige Zahlen: 264.53 seconds
---------------------------------------
combinations=20160075; tried=13283351
23 stellige Zahlen: 351.419 seconds
---------------------------------------
combinations=28048800; tried=17243835
35452590104031691935943
28361281321319229463398
27907865009977052567814
27879694893054074471405
21887696841122916288858
24 stellige Zahlen: 446.939 seconds
---------------------------------------
combinations=38567100; tried=21598582
239313664430041569350093
188451485447897896036875
174088005938065293023722
56 stellige Zahlen: 505.826 seconds
---------------------------------------
combinations=6906900; tried=6906900; using digit '9' at least 37 times
25 stellige Zahlen: 595.967 seconds
---------------------------------------
combinations=38567100; tried=28616431; using digit '9' at least 1 times
4422095118095899619457938
3706907995955475988644381
3706907995955475988644380
1553242162893771850669378
1550475334214501539088894
26 stellige Zahlen: 754.697 seconds
---------------------------------------
combinations=52451256; tried=38678211; using digit '9' at least 1 times
27 stellige Zahlen: 1028.93 seconds
---------------------------------------
combinations=70607460; tried=52414219; using digit '9' at least 1 times
177265453171792792366489765
174650464499531377631639254
128851796696487777842012787
121270696006801314328439376
121204998563613372405438066
55 stellige Zahlen: 1316.523 seconds
---------------------------------------
combinations=20160075; tried=20160075; using digit '9' at least 33 times
28 stellige Zahlen: 1427.921 seconds
---------------------------------------
combinations=94143280; tried=70580192; using digit '9' at least 1 times
29 stellige Zahlen: 1693.098 seconds
---------------------------------------
combinations=94143280; tried=78484744; using digit '9' at least 2 times
23866716435523975980390369295
19008174136254279995012734741
19008174136254279995012734740
14607640612971980372614873089
30 stellige Zahlen: 1970.187 seconds
---------------------------------------
combinations=124403620; tried=94628589; using digit '9' at least 2 times
54 stellige Zahlen: 2093.961 seconds
---------------------------------------
combinations=38567100; tried=38567100; using digit '9' at least 30 times
31 stellige Zahlen: 2530.05 seconds
---------------------------------------
combinations=163011640; tried=124404192; using digit '9' at least 2 times
2309092682616190307509695338915
1927890457142960697580636236639
1145037275765491025924292050346
32 stellige Zahlen: 3191.876 seconds
---------------------------------------
combinations=163011640; tried=163011585; using digit '9' at least 3 times
17333509997782249308725103962772
33 stellige Zahlen: 3212.45 seconds
---------------------------------------
combinations=211915132; tried=164573914; using digit '9' at least 3 times
186709961001538790100634132976991
186709961001538790100634132976990
53 stellige Zahlen: 3354.335 seconds
---------------------------------------
combinations=70607460; tried=70607460; using digit '9' at least 27 times
34 stellige Zahlen: 4088.163 seconds
---------------------------------------
combinations=211915132; tried=211915132; using digit '9' at least 4 times
1122763285329372541592822900204593
52 stellige Zahlen: 4762.076 seconds
---------------------------------------
combinations=124403620; tried=124403620; using digit '9' at least 24 times
36 stellige Zahlen: 5466.061 seconds
---------------------------------------
combinations=350343565; tried=273438889; using digit '9' at least 4 times
35 stellige Zahlen: 5529.264 seconds
---------------------------------------
combinations=273438880; tried=273438880; using digit '9' at least 4 times
12679937780272278566303885594196922
12639369517103790328947807201478392
51 stellige Zahlen: 5645.035 seconds
---------------------------------------
combinations=163011640; tried=163011640; using digit '9' at least 22 times
50 stellige Zahlen: 6570.025 seconds
---------------------------------------
combinations=211915132; tried=211915132; using digit '9' at least 20 times
37 stellige Zahlen: 6919.389 seconds
---------------------------------------
combinations=350343565; tried=350343565; using digit '9' at least 5 times
1219167219625434121569735803609966019
38 stellige Zahlen: 6947.344 seconds
---------------------------------------
combinations=350343565; tried=350343565; using digit '9' at least 6 times
12815792078366059955099770545296129367
39 stellige Zahlen: 7104.174 seconds
---------------------------------------
combinations=445891810; tried=360861865; using digit '9' at least 6 times
115132219018763992565095597973971522401
115132219018763992565095597973971522400
49 stellige Zahlen: 7534.684 seconds
---------------------------------------
combinations=273438880; tried=273438880; using digit '9' at least 18 times
40 stellige Zahlen: 8087.774 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 7 times
47 stellige Zahlen: 8186.085 seconds
---------------------------------------
combinations=350343565; tried=350343565; using digit '9' at least 15 times
41 stellige Zahlen: 8253.436 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 8 times
48 stellige Zahlen: 8261.199 seconds
---------------------------------------
combinations=350343565; tried=350343565; using digit '9' at least 16 times
42 stellige Zahlen: 8304.385 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 9 times
44 stellige Zahlen: 8386.987 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 11 times
43 stellige Zahlen: 8394.113 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 10 times
45 stellige Zahlen: 8437.592 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 12 times
46 stellige Zahlen: 8495.851 seconds
---------------------------------------
combinations=445891810; tried=445891810; using digit '9' at least 13 times
JNumbers.java
package jnumbers;
public class JNumbers {
static boolean singleThread = false;
// -------------------------------------------------------------------------
public static void main(String[] args) throws InterruptedException {
int max = 10;
int min = 1;
System.out.println("Welcome to 'Narzistische Zahlen' V 1.2");
if (args.length == 0) {
System.out.println("Argument 1 max Stellenanzahl 1..60");
System.out.println("Argument 2 min, max Stellenanzahl");
System.out.println("Argument 3 min, max, SingleThread");
System.exit(1);
}
if (args.length == 1) {
min = new Integer(args[0]);
max = new Integer(args[0]);
System.out.println("Berechne Loesungen fuer " + max + " Stellen.");
}
if (args.length > 1) {
max = new Integer(args[1]);
System.out.println("Suche Loesungen mit " + min + " bis " + max + " Stellen.");
}
if (args.length == 3) {
singleThread = true;
}
if (min > max) {
System.out.println("use 2 arguments: min, max with max>min");
System.exit(1);
}
System.out.println("Diese n-stelligen Zahlen entsprechen der Summe der n-ten Potenz ihrer Ziffern.\n");
int nCPU = Runtime.getRuntime().availableProcessors();
if (singleThread || min == max) {
nCPU = 1;
}
System.out.println("\tStart, using " + nCPU + " CPU for calculation!");
String nameOS = System.getProperty("os.name");
System.out.println("\tOperating system Name: " + nameOS);
String tmp=System.getenv("PROCESSOR_IDENTIFIER");
if (tmp==null) tmp="";
System.out.println("\t" +tmp +"\n\n");
long startTime = System.nanoTime();
for (int n = min; n <= max; n++) {
Runnable task = new BigNumPermThread(n, startTime); // initialise class
Thread worker = new Thread(task); // setup Thread
worker.start();
if (singleThread) {
worker.join(); // wait for finish
}
}
}
}
BigNumPermThread.java
package jnumbers;
import java.math.BigInteger;
/**
*
* @author Rolf
*/
public class BigNumPermThread implements Runnable {
/* use BigInteger for large numbers instead of long */
BigInteger zifferPotenz[] = null; // ^ n
int zifferPos[] = null; // Ziffer an Position n-1,..,3,2,1,0
BigInteger sumPotenz; // sumPotenz = 1³ + 5³ + 3³
BigInteger sumMax; // max sum e.g. 999 for n=3
BigInteger sumMin; // min sum e.g. 99 for n=3
int n = 0; // Anzahl Ziffern
StringBuffer sb; // Ausgabe zusammenhängend
int cnt9Min; // minium of '9' to use
long cnt = 0;
long cntCut = 0;
long startTimeMain = 0L;
/*public void startTime(Long s) {
startTimeMain=s;
}*/
// -------------------------------------------------------------------------
public BigNumPermThread(int n, long startTime) {
// initialize
this.n = n;
startTimeMain = startTime;
zifferPotenz = new BigInteger[10]; // remember 1..10 ^ n
zifferPos = new int[n]; // remember positions
for (int i = 0; i < 10; i++) {
zifferPotenz[i] = new BigInteger(i + "");
zifferPotenz[i] = zifferPotenz[i].pow(n);
}
BigInteger ONE = new BigInteger("1");
sumMax = new BigInteger("10").pow(n);
sumMin = new BigInteger("10").pow(n - 1).subtract(ONE);
sumPotenz = new BigInteger("0");
/*
try to find out, how often '9' ist at least required
----------------------------------------------------
n=39
If we use 5 digits with '9' the max number will be
5 * 9^39 + (39-5) * 8 ^39 = 8.7 E37 still too small!
*/
cnt9Min = n;
for (int k = 0; k <= n; k++) {
BigInteger big_k = new BigInteger(k + "");
BigInteger big_nk = new BigInteger(n - k + "");
int len = zifferPotenz[9].multiply(big_k)
.add(zifferPotenz[8].multiply(big_nk))
.toString().length();
if (len > n) {
cnt9Min = 0;
break;
}
if (len == n) {
cnt9Min = k;
break;
}
}
}
// -------------------------------------------------------------------------
public void run() {
if (n < 10) {
sb = new StringBuffer(" ");
} else {
sb = new StringBuffer();
}
sb.append(n + " stellige Zahlen:");
if (cnt9Min > 0) {
sb.append("\tuse digit '9' at least " + cnt9Min + " times");
}
long startTime = System.nanoTime();
sb.append("\n-------------------\n\t");
if (tryIt(9, n - 1)) {
long endTime = System.nanoTime();
long sec = (endTime - startTime) / 1000000;
sb.append("execution time:\t" + sec / 1000.0 + " seconds\t\tcombinations=" + cnt + "\ttried=" + cntCut + "\n");
sec = (endTime - startTimeMain) / 1000000;
sb.append("\ttotal time:\t" + sec / 1000.0 + " seconds\n");
System.out.println(sb);
} else {
if (n < 10) {
System.out.println(" "+n + " stellige Zahlen:");
} else
System.out.println(n + " stellige Zahlen:");
}
}
// -------------------------------------------------------------------------
private boolean tryIt(int maxZiff, int posIdx) {
boolean fnd = false;
if (posIdx < 0) {
cnt++;
// check for solution found
if (sumPotenz.compareTo(sumMin) >= 0 && sumPotenz.compareTo(sumMax) < 0) {
// Range check ok
cntCut++;
String oneChar;
String sumPotenzStr = sumPotenz + "";
for (posIdx = 0; posIdx < n; posIdx++) {
oneChar = Long.toString(zifferPos[posIdx]);
if (sumPotenzStr.indexOf(oneChar) < 0) {
return false; // ups not found, no solution!
}
sumPotenzStr = sumPotenzStr.replaceFirst(oneChar, " ");
}
// list nice solution
String solved = sumPotenz.toString();
int len = solved.length();
if (len < 16) {
for (int i = 0; i < len; i++) {
sb.append(solved.charAt(i) + "^" + len);
if (i < len - 1) {
sb.append(" + ");
} else {
sb.append(" = ");
}
}
}
sb.append(solved + "\n\t");
fnd = true;
}
} else {
// build up sumPotenz
// start from most significant digit with maxZiff down to 0
int minZiff = 0;
if (cnt9Min-- > 0) {
minZiff = 9;
}
for (int i = maxZiff; i >= minZiff; i--) {
//for (int i = 0; i <= maxZiff; i++) {
zifferPos[posIdx] = i; // log digit used at position posIDx
sumPotenz = sumPotenz.add(zifferPotenz[i]); // sumPotenz = 1³ + 5³ + 3³
if (tryIt(i, posIdx - 1)) {
fnd = true;
};
sumPotenz = sumPotenz.subtract(zifferPotenz[i]);
}
}
return fnd;
}
}
Berechnung
Die Berechnung läuft hier parallel, wenn für ein 'bis' Wert angegeben wird.
Ein größere Anzahl Dezimalstellen braucht deutlich Zeit, daher wurden die Eingabe Werte deutlich limitiert.