Mathematik/Programmiertechnik zum Wochenende – Lösung

[Gunnar Bittersmann]

@@Matthias Apsel

Man ermittle alle Zahlen n, für die gilt n = z.

Aus der Bildungsvorschrift von z ergibt sich, dass z maximal 10stellig sein kann. Damit können auch die gesuchten mit z übereinstimmenden n maximal 10stellig sein.

Auf die Suche!

Eine Methode, um die Vorkommen eines Zeichens (einer Zeichenkette) in einem String zu zählen:

String.prototype.occurrences = function (character) {
	return this.match(new RegExp(character, 'g'))?.length || 0;
};

Ist es eigentlich eine gute oder eine blöde Idee, Basisobjekte prototypisch zu erweitern? (Ernsthafte Frage.)

Damit erhält man z(n):

function z(n) {
	const nString = n.toString();
	let zString = '';
	for (let digit = 0; digit <= 9; digit++) {
		zString += nString.occurrences(digit);
	}
	return Number.parseInt(zString, 10);
};

Jetzt braucht man nur noch alle maximal 10stelligen Zahlen untersuchen:

for (let n = 0; n < 1e10; n++) {
	if (n == z(n)) {
		console.log(n);
	}
}

(Die nicht in N einthalten Zahlen 1111111111 (zehn Einsen), 2222222222, …, 9999999999 würde man einfach ignorieren, sollten sie Treffer sein.)

Das Problem daran: Das Script läuft eeeeeeeeeewig. Bzw.: Es tut es nicht; der Browser fragt immer wieder nach, ob er es weiter ausführen soll. Es läuft durch bis 10⁶; mit wiederholten Aufforderungen weiterzumachen kommt man auch bei 10⁷ zum Ende. Aber bis 10¹⁰ sind’s noch Größenordnungen …

Andere Implementierungen mögen schneller sein und keine Nachfrage erzeugen; 10¹⁰ Schleifendurchläufe sind auch dann kaum praktikabel. (Bei nur einer Zehntelmillisekunde pro Durchlauf würde das Script 10⁶ Sekunden laufen; das sind über 11½ Tage.)

Aber wir wissen schon mal, dass es keine Zahl n = z(n) gibt, die 7 oder weniger Stellen hat.

Das muss anders gehen als mit brute force; Gewalt ist keine Lösung.

---

Ich hatte mich schon gefragt, ob ich mit „Ich habe zwei Zahlen gefunden, für die n = z(z(n)) gilt“ nicht schon zu viel vom Lösungsweg verraten hatte …

Lassen wir uns doch mal z(n) ausgeben:

function check(n) {
	console.log(n, n == z(n) ? '🌞🌞🌞' : z(n));
}

Für 0:

check(0); // 0 1000000000

Und jetzt setzen wir das Ergebnis wieder ein:

check(1000000000); // 1000000000 9100000000

Und wieder und wieder:

check(9100000000); // 9100000000 8100000001

check(8100000001); // 8100000001 7200000010

check(7200000010); // 7200000010 7110000100

check(7110000100); // 7110000100 6300000100

check(6300000100); // 6300000100 7101001000

check(7101001000); // 7101001000 6300000100

Wir landen im Zyklus 6300000100 ↔︎ 7101001000.

Und dasselbe passiert auch für den Startwert 1, 2, 3, …, 98765, …

Das legt die Vermutung nahe, dass das für alle Startwerte so ist, d.h. dass es keine Zahl gibt, für die n = z(n) gilt.

An der Stelle kommt @Matthias Apsel ins Spiel, der mir zuflüsterte, dass es doch eine solche Zahl gibt. Dann heißt’s wohl, die Nadel im Heuhaufen zu suchen …

---

Und dafür eine Funktion geschrieben, die z(z(z(…))) berechnet, bis sie in den Zyklus läuft oder nach einigen Durchläufen abbricht. (Wie wir gesehen hatten, kommt man recht schnell in den Zyklus; 10 Schleifen sollten reichen.)

function attractor(n) {
	for (let i = 0; i < 10; i++) {
		if (n == 7101001000) {
			return n;
		}
		else {
			n = z(n);
		}
	}
	return null;
};

console.log(attractor(0)); // 7101001000

Voller Verzweiflung hab ich dann wahllos auf der Tastatur rumgeklimpert (ich schwör’s, so war’s):

console.log(attractor(42189658268)); // null

Nanu? Reichen 10 Schleifen doch nicht? Auf 100 erhöht, 1000, 10000 – selbes Ergebnis.

Huch, was’n da los?

check(42189658268); // 42189658268 120112031

check(120112031); // 120112031 2421000000

check(2421000000); // 2421000000 6120100000

check(6120100000); // 6120100000 6210001000

check(6210001000); // 6210001000 "🌞🌞🌞"

Punker Maria, du ich hab die Nadel gefunden! (Didi)

Es gibt sie wirklich: 6210001000 ist so eine gesuchte Zahl mit n = z(n).

---

Jetzt stellt sich die Frage, ob ich einfach nur wahnsinnig viel Glück hatte oder ob es viele Startwerte gibt, die nicht in den Zyklus 6300000100 ↔︎ 7101001000, sondern zu 6210001000 führen.

Die Funktion abgewandelt zu

function attractor(n) {
	const attractors = [
		6210001000,
		7101001000,
	];

	for (let i = 0; i < 10; i++) {
		if (attractors.includes(n)) {
			return n;
		}
		else {
			n = z(n);
		}
	}
	return null;
};

und mit 10000 Zufallszahlen aus dem Bereich [0, 10¹⁰[ geprüft ergibt: Etwa 34½ % der Zahlen führen zu 6210001000; 65½ % zum Zylus 7101001000 ↔︎ 6300000100. Es war keine Zahl dabei, die nicht zu einem der beiden führt.

Das ist ein Indiz, aber kein Beweis dafür, dass es nicht noch weitere Zyklen gibt; womöglich gar welche der Länge 1, d.h. weitere Zahlen mit der Eigenschaft n = z(n).

Um das auszuschließen, fiele mir jetzt wieder nur brute force ein …

Es war also doch nicht die Nadel, die ich im Heuhaufen gefunden hab; es gibt viele davon. Warum ich anfangs keine gefunden hatte: es gibt keine Nadeln < 10⁶. Die kleinste Zahl, die zu 6210001000 führt, ist 1000123.

Hier noch der Link zu meiner Spielwiese.

🖖 Stay hard! Stay hungry! Stay alive! Stay home!