Mathematik/Programmiertechnik zum Wochenende - Anzahl der n

[Rolf B]

Hallo,

für die Antwort auf Frage 1 habe ich nicht versucht, alle n zu bilden und ihr z zu berechnen. Das dauert mutmaßlich länger, als unsere Sonne brennt.

Statt dessen schaue ich mir alle möglichen z an, das sind ja nur 9999999999, und bereche für jedes z die möglichen n. Das ist gar nicht so schwer.

Sei im Folgenden $$h_i : \mathrm N \rightarrow \mathbb N$$ die Funktion, die die Häufigkeit der Ziffer i in der der Zahl $$n \in \mathrm N$$ angibt. Dann definiere ich z in der Gunnar-Variante als

$$\displaystyle z: \mathrm N \rightarrow \mathbb N, z(n) = \sum_{i=0}^9 h_i(n)10^{9-i}$$

Sei darüberhinaus $$q: \mathbb N \rightarrow \mathbb N$$ die Funktion, die zu einer Zahl ihre Quersumme liefert, und $$z_i$$ die Stelle einer Zahl z, die die Ziffernhäufkeit der Ziffer i angibt.

Der naive Ansatz wäre, bei gegebenem z für die Anzahl der möglichen n mit z(n)=z den einfachen kombinatorischen Ansatz zu wählen:

$$\displaystyle | \left\{ n | n \in \mathrm N, z(n)=z \right\} | = \frac{q(z)!}{z_0!z_1!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}$$

Für Ziffern, die in n nicht vorkommen, ist $$z_i!=1$$, da muss man also nicht besonders aufpassen. Aber das Ergebnis ist trotzdem falsch, weil es n mit führenden Nullen mitzählt, die in n nicht erlaubt sind.

Deshalb muss man es mühsamer machen. Für jede Ziffer von 1-9, die mindestens einmal vorkommt, muss man ermitteln, wie sich die übrigen Ziffern dahinter kombinieren lassen. Beispielsweise für die 1 (start(n) bezeiche die erste Ziffer von n):

$$\displaystyle N_{z,1} := \left\{ n | n \in \mathrm N, \mathrm{start}(n)=1, z(n)=z \right\}, | N_{z,1} | = \frac{(q(z)-1)!}{z_0!(z_1-1)!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}$$

Das macht man für die Ziffern von 1-9 und addiert auf. Fertig. Irgendwann 😟. Das geht doch bestimmt besser!

Das $$(z_i-1)!$$ im Nenner ist extrem unhandlich für n die die Ziffer i nicht enthalten, das muss mal als erstes weg. Wenn man den Bruch für $$|N_{z,1}|$$ mit $$z_1$$ erweitert, dann bekommt man

$$\displaystyle | N_{z,1} | = \frac{z_1 \cdot (q(z)-1)!}{z_0!z_1(z_1-1)!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}= \frac{z_1 \cdot (q(z)-1)!}{z_0!z_1!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}$$

und das ist eine Erleuchtung, denn bis auf das $$z_i$$ im Zähler ist dieser Bruch für alle Ziffern gleich. Und für Ziffern, die in n nicht vorkommen, liefert der Term brav den Wert 0. Eine Fallunterscheidung, ob Ziffern vorkommen oder nicht, entfällt damit. Nach Aufaddieren und Ausklammern des Fakultätenhaufens ist die Anzahl aller n zu einem z:

$$\displaystyle | N_z | = \frac{(z_1+z_2+z_3+z_4+z_5+z_6+z_7+z_8+z_9) \cdot (q(z)-1)!}{z_0!z_1!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}$$
$$\displaystyle = \frac{(q(z)-z_0) \cdot (q(z)-1)!}{z_0!z_1!z_2!z_3!z_4!z_5!z_6!z_7!z_8!z_9!}$$

(wieso funktionieren \align-Umgebungen nicht mehr⁉️)

Die Fakultäten der Zahlen von 0-90 kann man noch vorausberechnen und in einem Array ablegen, so dass man sie nur noch abrufen muss statt für jedes z neu berechnen. Das sieht in C# dann so aus:

   double[] fakTab = new double[91];
   for (int i = 0; i <= 90; i++)
      fakTab[i] = fakultät(i);

   double allCombs = 0;
   Digits d = new Digits(z1);
   for (long z = 1; z < 10000000000; z++)
   {
      double combs = (fakTab[d.quersumme - 1] * (d.quersumme - d.d0))
                   / (fakTab[d.d0] * fakTab[d.d1] * fakTab[d.d2] * fakTab[d.d3]
                    * fakTab[d.d4] * fakTab[d.d5] * fakTab[d.d6] * fakTab[d.d7] 
                    * fakTab[d.d8] * fakTab[d.d9])
                        ;
      allCombs += combs;
      d.Increment();
   }
   Console.WriteLine("{0} Kombinationen", allCombs);

Diese Schleife läuft bei mir in ca 2 Minuten durch und ermittelt 9,626183655 E+82 mögliche n. Ich hätte es aber auch schneller haben können. Alle z, deren Quersumme unter 50 liegt, haben eine Quersumme, deren Fakultät die um viele Größenordnungen kleiner ist als die Fakultät der maximalen Quersumme 90 (10^73). Bei 70 ist es noch 10^38, aber es kommt auch der Effekt des kleineren Nenners hinzu, darum sieht man da schon erste Abweichungen:

        9999999999 z gerechnet: 9,62618365528156E+82 - 125s
q > 50, 2750633666 z gerechnet: 9,62618365528156E+82 -  63s
q > 70,   19106230 z gerechnet: 9,62618365528149E+82 -  41s
q > 75,    1951246 z gerechnet: 9,62618365316412E+82 -  38s 
q > 80,      92378 z gerechnet: 9,62615856375375E+82 -  37,6s
q > 99,       nichts gerechnet:                      -  37,5s

Unter 37 komme ich nicht, das ist der Anteil der Increment-Methode.

Rolf