Teilbare Fakultäten

Vor kurzem war ich von diesem Tweet aus der Farm Library völlig verblüfft:


"Das passiert, wenn man nicht multipliziert, sondern in der Fakultät teilt."

Als ich ihn sah, musste ich mein Geschäft aufgeben, mir ein Notizbuch schnappen und die Formel überprüfen. Der Entwurf des Ergebnisses schien logisch. Seit der multiplikativen Version $$$n!$ mit zunehmender $$$n$ neigt zur Unendlichkeit, dann sollte die "teilende" Version gegen Null tendieren. Und $$$\ frac {n ^ 2} {n!}$ verhält sich so; Polynomfunktion $$$n ^ 2$ wächst langsamer als eine Potenzfunktion $$$n!$ für groß genug $$$n$ ::

$$

$$\ frac {1} {1}, \ frac {4} {2}, \ frac {9} {6}, \ frac {16} {24}, \ frac {25} {120}, \ frac {36 } {720}, \ frac {49} {5040}, \ frac {64} {40320}, \ frac {81} {362880}, \ frac {100} {3628800}$$

Aber warum nimmt das Teilungsergebnis die Form an? $$$\ frac {n ^ 2} {n!}$ ? Woher kommt es? $$$n ^ 2$ ?

Um diese Frage zu beantworten, musste ich das alte Trauma, das mit dem Studium der fraktionierten Teilung verbunden war, abbauen, aber ich kam mit dem Schmerz zurecht. Wenn wir von der Tweet-Formel von links nach rechts gehen, erhalten wir zuerst $$$\ frac {n} {n-1}$ . Teilen Sie dann diesen Wert durch $$$n-2$ wir bekommen

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

Wenn wir so weitermachen, erhalten wir:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

Um das im Tweet angezeigte Ergebnis zu erhalten $$$\ frac {n ^ 2} {n!}$ Wir multiplizieren nur den Zähler und den Nenner mit $$$n$ . (Obwohl für meinen Geschmack der Ausdruck $$$\ frac {n} {(n-1)!}$ klarer.)

---

Ich bin ein offiziell anerkannter Fakultätsfan. Behalten Sie Ihre Fibonacci-Sequenzen bei sich; Hier ist mein Lieblingsfeature. Jedes Mal, wenn ich eine neue Programmiersprache lerne, besteht meine erste Übung darin, mehrere Verfahren zur Berechnung der Fakultäten zu schreiben. Im Laufe der Jahre habe ich mir verschiedene Variationen dieses Themas ausgedacht, zum Beispiel einen Ersatz in der Definition $$$\ times$ auf $$$+$ (was uns dreieckige Zahlen gibt). Aber anscheinend habe ich noch nie darüber nachgedacht, etwas zu ersetzen $$$\ times$ auf $$$\ mathbin {/}$ . Es stellt sich als seltsam heraus. Da die Multiplikation kommutativ und assoziativ ist, können wir definieren $$$n!$ genauso wie das Produkt aller ganzen Zahlen aus $$$1$ vorher $$$n$ ohne sich um die Reihenfolge der Operationen zu sorgen. Beim Teilen kann die Reihenfolge jedoch nicht ignoriert werden. Im allgemeinen Fall $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ und $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

Im Tweet der Farm Library sind die Teiler in absteigender Reihenfolge: $$$n, n-1, n-2, \ ldots, 1$ . Am offensichtlichsten wird dies durch eine aufsteigende Reihenfolge ersetzt: $$$1, 2, 3, \ ldots, n$ . Was passiert, wenn wir die Fakultät der Teilung als definieren $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ? Eine weitere Rückkehr zum Bruchteilungsalgorithmus der Schule gibt uns eine einfache Antwort:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ mal 3 \ mal 4 \ mal \ cdots \ mal n} = \ frac {1} {n!}$$

Mit anderen Worten, wenn wir viele Male teilen, zählen wir ab $$$1$ vorher $$$n$ ist das Endergebnis gleich dem Kehrwert $$$n!$ . (Ich möchte am Ende dieses Satzes ein Ausrufezeichen setzen, aber leider!) Wenn Sie nach einer kanonischen Antwort auf die Frage suchen: „Was bekommen wir, wenn wir teilen, anstatt zu multiplizieren? $$$n!$ ? ", Dann würde ich das sagen $$$\ frac {1} {n!}$ Ist ein besserer Kandidat als $$$\ frac {n} {(n - 1)!}$ . Warum akzeptieren wir nicht die Symmetrie zwischen $$$n!$ und sein umgekehrter Wert?

Natürlich gibt es viele andere Möglichkeiten, n ganzzahlige Werte in die Menge einzufügen $$$\ {1 \ ldots n \}$ . Aber wie viel genau? Wie sich herausstellte, genau $$$n!$ ! Daher scheint es, dass es gibt $$$n!$ einzigartige Möglichkeiten zur Definition einer Teilungsfunktion $$$n!$ . Wenn wir jedoch die Antworten der beiden oben gezeigten Permutationen studieren, verstehen wir, dass hier ein einfacheres Muster funktioniert. Welches Element der Sequenz auch immer zuerst erscheint, es erscheint im Zähler eines großen Bruchs, und das Produkt aller anderen Elemente ist der Nenner. Daher gibt es am Ende nur $$$n$ unterschiedliche Ergebnisse (vorausgesetzt, wir führen Divisionsoperationen immer ausschließlich von links nach rechts durch). Für jede ganze Zahl $$$k$ im Bereich von $$$1$ vorher $$$n$ durch Einstellen $$$k$ Am Anfang der Zeile erstellen wir eine Teilung $$$n!$ gleich $$$k$ geteilt durch alle anderen Faktoren. Sie können dies wie folgt schreiben:

$$

$$\ cfrac {k} {\ frac {n!} {k}}, \ text {, der in} \ frac {k ^ 2} {n!} $ konvertiert werden kan$$

Und so haben wir ein kleines Rätsel gelöst, wie in diesem Tweet $$$\ frac {n} {(n-1)!}$ verwandelte sich in $$$\ frac {n ^ 2} {n!}$ .
Es ist erwähnenswert, dass alle diese Funktionen gegen Null konvergieren, wenn $$$n$ bis unendlich. Aus asymptotischer Sicht $$$\ frac {1 ^ 2} {n!}, \ frac {2 ^ 2} {n!}, \ ldots, \ frac {n ^ 2} {n!}$ identisch.

---

Ja! Mission erfüllt. Das Problem ist gelöst. Die Arbeit ist erledigt. Jetzt wissen wir alles, was wir zum Teilen von Fakultäten brauchen, oder?

Nun, vielleicht gibt es noch eine Frage. Was sagt der Computer? Wenn wir unseren bevorzugten faktoriellen Algorithmus verwenden und das tun, was in einem Tweet vorgeschlagen wird, ersetzen Sie alle Vorkommen des Operators $$$\ times$ (oder * ) am / , was wird passieren? Welche von $$$n$ Teilungsoptionen $$$n!$ Wird uns das Programm geben?

Hier ist mein Lieblingsalgorithmus zur Berechnung von Fakultäten als Programm für Julia :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

Dieser Algorithmus führte ganze Generationen von Nerds in das Konzept der Rekursion ein. In Textform lautet es: if $$$n$ gleich $$$1$ dann $$$mul! (n)$ gleich $$$1$ . Andernfalls müssen Sie die Funktion berechnen $$$mul! (n-1)$ und multiplizieren Sie dann das Ergebnis mit $$$n$ .

_{Sie können fragen, was passiert, wenn} $$_{$n$ wird Null oder negativ sein. Sie können fragen, aber es ist besser, dies nicht zu tun. Für unsere aktuellen Ziele} $$_{$n \ in \ mathbb {N}$ .}

Beginnend mit einem positiven $$$n$ wird die Folge von rekursiven Aufrufen früher oder später auf fallen $$$n = 1$ .

Eine Funktion kann mit dem einzeiligen Julia-Definitionsstil prägnanter geschrieben werden:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

Ist der rechte Teil des Zuweisungsoperators ein bedingter Ausdruck oder ein ternärer Operator der Form a ? b : c a ? b : c . Hier ist a die boolesche Bedingung des Tests, die entweder true oder false . Wenn a true , wird Ausdruck b ausgewertet und das Ergebnis wird zum Wert des gesamten Ausdrucks. Andernfalls wird c berechnet.

Um sicherzugehen, dass ich alles richtig gemacht habe, sind hier die ersten 10 Fakultäten, die von diesem Programm berechnet wurden:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

Lassen Sie uns nun diese Definition ändern und das einzige Vorkommen * in / transformieren, wobei alles andere unverändert bleibt (mit Ausnahme des Namens der Funktion).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

Und das gibt das Programm zurück, wenn wir es für die Werte ausführen $$$n$ von $$$1$ vorher $$$20$ ::

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

Was? Es ist definitiv nicht so, als würde man gegen Null konvergieren $$$\ frac {1} {n!}$ oder $$$\ frac {n} {n - 1}$ . Tatsächlich sehen die Werte nicht so aus, weil sie nicht konvergieren werden. Nach der folgenden Grafik zu urteilen, besteht die Sequenz aus zwei verschachtelten Komponenten, von denen jede langsam gegen unendlich zu wachsen scheint und auch von der anderen abweicht.


Wenn Sie verstehen, was wir hier beobachten, ist es hilfreich, den Ausgabetyp der div! Funktion zu ändern div! . Anstatt den Divisionsoperator / , der den Wert als Gleitkommazahl zurückgibt, können wir ihn durch den Operator // ersetzen, der den exakten rationalen Wert zurückgibt, der auf den niedrigsten Term gerundet ist.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

Hier ist eine Folge von Werten für n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

Die Liste ist voller interessanter Muster. Dies ist eine Doppelhelix, bei der sich gerade und ungerade Zahlen im Zickzack in komplementären Fäden bewegen. Gerade Zahlen sind nicht nur gerade, sie sind alle Grade $$$2$ . Außerdem erscheinen sie paarweise - zuerst im Zähler, dann im Nenner - und ihre Reihenfolge nimmt nicht ab. Aber es gibt Lücken; Nicht alle Abschlüsse sind vorhanden $$$2$ . Der ungerade Thread sieht noch komplexer aus, verschiedene kleine einfache Koeffizienten erscheinen und verschwinden in den Zahlen. (Primzahlen müssen klein sein, zumindest weniger $$$n$ .)

Dieses Ergebnis hat mich überrascht. Ich erwartete eine viel mildere Sequenz, wie ich sie auf Papier berechnet hatte. All diese kaputten Sprünge machten keinen Sinn. Auch der allgemeine Trend zu unbegrenztem Wachstum der Quote machte keinen Sinn. Wie können wir uns ständig teilen, während wir alle immer größeren Zahlen erhalten?

An diesem Punkt können Sie das Lesen unterbrechen und versuchen, eine eigene Theorie darüber zu erstellen, woher diese Zick-Zack-Zahlen stammen. Wenn Sie einen Hinweis benötigen, dann haben Sie ihn und einen sehr starken, fast einen Spoiler: Suchen Sie in der Online-Enzyklopädie der ganzzahligen Sequenzen nach einer Folge von Zählern oder einer Folge von Nennern.

---

Hier ist ein weiterer Hinweis. Eine kleine Änderung im div! Programm div! konvertiert die Ausgabe vollständig. Ändern Sie einfach den letzten Ausdruck, indem Sie n // div!(n - 1) durch div!(n - 1) // n ersetzen.

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

Jetzt sehen die Ergebnisse so aus:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

Dies ist die Umkehrfunktion der Fakultät, die wir bereits gesehen haben, eine Reihe von Werten, die erzeugt werden, indem in einer zunehmenden Folge von Teilern von links nach rechts gegangen wird $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

Es überrascht nicht, dass das Ändern des letzten Ausdrucks in einer Prozedur das Ergebnis ändert. Am Ende wissen wir, dass die Teilung weder kommutativ noch assoziativ ist. Es ist jedoch schwer zu verstehen, warum die vom ursprünglichen Programm erzeugte Folge von Werten eine so seltsame Zick-Zack-Form ergibt. Welcher Mechanismus führt zu solchen gepaarten Zweierpotenzen und abwechselnden ungeraden und geraden Werten?

Ich fand, dass es in einer iterativen Version der Prozedur einfacher ist zu erklären, was in einer Zick-Zack-Sequenz passiert, als in einer rekursiven. (Diese Aussage mag für diejenigen ärgerlich erscheinen, die rekursive Definitionen einfacher finden, aber es ist einfach passiert.) So sieht das Programm aus:

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

Ich erkläre, dass diese Prozedur mit einem Funktionszyklus mit einer rekursiven Funktion identisch ist, in dem Sinne, dass wenn div!(n) und div!_iter(n) ein Ergebnis für eine positive ganze Zahl n , es immer dasselbe sein wird. Hier ist mein Beweis:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

Berücksichtigen Sie die sequentiellen Werte der Variablen, um den Prozess zu verstehen, der diese Zahlen generiert $$$i$ und $$$q$ jedes Mal, wenn Sie eine Schleife ausführen. Ursprünglich $$$i$ und $$$q$ sind gleich $$$1$ ;; daher ergibt sich nach dem ersten Durchgang des Zyklus der Ausdruck q = i // q $$$q$ Wert $$$\ frac {1} {1}$ . Dann $$$i = 2$ und $$$q = \ frac {1} {1}$ das heißt, eine neue Bedeutung $$$q$ gleich $$$\ frac {2} {1}$ . In der dritten Iteration $$$i = 3$ und $$$q = \ frac {2} {1}$ das gibt uns $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . Wenn dies immer noch verwirrend ist, dann stellen Sie sich vor $$$\ frac {i} {q}$ wie $$$i \ times \ frac {1} {q}$ . Eine wichtige Beobachtung hierbei ist, dass bei jedem Schleifenzyklus $$$q$ bekommt den entgegengesetzten Wert, wird $$$\ frac {1} {q}$ .

Wenn Sie diese Operationen erweitern und die Multiplikationen und Divisionen betrachten, die in jedem Element der Reihe enthalten sind, entsteht ein Muster:

$$

$$\ frac {1} {1}, \ quad \ frac {2} {1}, \ quad \ frac {1 \ cdot 3} {2}, \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }, \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

In allgemeiner Form:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {odd} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {gerade} n)$$

---

Funktionen $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ für ungerade $$$n$ und $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ für gerade $$$n$ habe ihren eigenen Namen! Sie werden doppelte Fakultäten genannt und als geschrieben $$$n !!$ .

_{Schreckliche Terminologie, richtig? Es wäre besser, wenn sie "semi-Fakultät" genannt würden. Und wenn ich es nicht wüsste, würde ich lesen} $$_{$n !!$ als Fakultät Fakultät.}

Die doppelte Fakultät n ist definiert als das Produkt von n und allen kleineren positiven ganzen Zahlen derselben Parität. Unsere merkwürdige Folge von Zick-Zack-Werten ist also gerecht $$$\ frac {n !!} {(n-1) !!}$ .

Ein Artikel von Henry W. Gould und Jocelyn Quentens (leider hinter Paywall) aus dem Jahr 2012 befasst sich mit der Verwendung von Doppelfaktoren. Sie sind viel häufiger als Sie vielleicht denken. Mitte des 17. Jahrhunderts leitete John Wallis die folgende Identität ab:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

Eine noch seltsamere Reihe mit einem Würfel aus doppelten Fakultätswerten wird in zusammengefasst $$$\ frac {2} {\ pi}$ . Er wurde von niemand anderem als Srinivasa Ramanujan entdeckt.

Gould und Kientens betrachteten auch das doppelte faktorielle Äquivalent für Binomialkoeffizienten. Der Standard-Binomialkoeffizient ist definiert als:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (n-k)!}$$

Die Dual-Version sieht folgendermaßen aus:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (n-k) !!}$$

Beachten Sie, dass unsere Zick-Zack-Zahlen dieser Beschreibung entsprechen und daher als Binomialkoeffizienten von Doppelfaktoren betrachtet werden können. Genauer gesagt handelt es sich um solche Zahlen:

$$

$$\ left (\! \ binom {n} {1} \! \ right) = \ left (\! \ binom {n} {n - 1} \! \ right) = \ frac {n !!} {1 !! (n-1) !!}$$

Einfache Bohne $$$\ binom {n} {1}$ nicht sehr interessant; er ist einfach gleich $$$n$ . Aber die Doppelversion $$$\ left (\! \ binom {n} {1} \! \ right)$ Wie wir gesehen haben, tanzt ein lebhafterer Tanz. Und im Gegensatz zum üblichen Binomial ist es nicht immer eine ganze Zahl. (Die einzigen ganzzahligen Werte sind $$$1$ und $$$2$ .)

Ein Blick auf Zickzackzahlen als Quotienten aus doppelten Fakultäten erklärt einige ihrer Eigenschaften, beginnend mit abwechselnden geraden und ungeraden Werten. Wir können auch sehen, warum alle geraden Zahlen in der Sequenz Potenzen von 2 sind. Betrachten Sie das Beispiel mit $$$n = 6$ . Der Zähler dieser Fraktion ist $$$2 \ cdot 4 \ cdot 6 = 48$ Empfangen von $$$6$ Multiplikator $$$3$ . Aber der Nenner ist $$$1 \ cdot 3 \ cdot 5 = $ 1$ . Die Drillinge oben und unten schrumpfen und verlassen uns $$$\ frac {16} {5}$ . Solche Reduzierungen treten jeweils auf. Jedes Mal, wenn ein ungerader Faktor in der Folge von geraden Zahlen erscheint $$$m$ hat es notwendigerweise die Form $$$2 \ cdot m$ aber zu diesem Zeitpunkt selbst $$$m$ sollte bereits in einer Folge von ungeraden Zahlen erscheinen.

---

Ist eine Folge von Zickzackzahlen eine vernünftige Antwort auf die Frage: „Was passiert, wenn wir teilen, anstatt zu multiplizieren? $$$n!$ ? " Oder hat sich das Computerprogramm, das sie generiert, als fehlerhafter Algorithmus herausgestellt? Meiner persönlichen Meinung nach $$$\ frac {1} {n!}$ - eine intuitivere Antwort, aber $$$\ frac {n !!} {(n - 1) !!}$ - interessanter.

Darüber hinaus erweitert die Existenz einer Zick-Zack-Sequenz unseren Horizont. Wie oben erwähnt, wenn Sie darauf bestehen, dass der Divisionsalgorithmus die Liste der Zähler immer in der richtigen Reihenfolge durchläuft $$$n$ Bei jedem Schritt, bei dem die Zahl links durch die Zahl rechts geteilt wird, ergibt sich eine Summe $$$n$ mögliche Ergebnisse, und sie sehen alle sehr ähnlich aus. Die Zick-Zack-Lösung bietet jedoch viel größere Möglichkeiten. Wir können das Problem wie folgt formulieren: Nehmen Sie den Satz von Zählern $$$\ {1 \ dots n \}$ Wählen Sie die Teilmenge aus und invertieren Sie alle Elemente dieser Teilmenge. Jetzt multiplizieren wir alle Zähler, sowohl invers als auch direkt. Wenn die invertierte Teilmenge leer ist, ist das Ergebnis eine reguläre Fakultät $$$n!$ . Wenn alle Zähler zu ihren Werten invers geworden sind, erhalten wir das Gegenteil $$$\ frac {1} {n!}$ . Und wenn jeder zweite Zähler konvertiert wird, beginnend mit $$$n - 1$ Dann ist das Ergebnis ein Element einer Zick-Zack-Sequenz.

Dies sind nur einige der vielen verfügbaren Optionen. Insgesamt gibt es $$$2 ^ n$ Teilmengen von $$$n$ Elemente. Zum Beispiel können Sie die Umkehrung jeder Zahl nehmen, die eine Primzahl oder eine Primzahl ist $$$(2, 3, 4, 5, 7, 8, 9, 11, \ Punkte)$ . Bei klein $$$n$ Ergebnisse springen, bleiben aber ständig kleiner als $$$1$ ::


Wenn ich dieses Diagramm jedoch für mehr fortsetzte $$$n$ würde er in die Stratosphäre abheben. Die Grade der Primzahlen werden auf der Zahlenlinie sehr spärlich.

---

Jetzt werde ich eine Frage stellen. Wir sahen faktorielle Variationen nahe Null als $$$n$ zum Beispiel bis ins Unendliche $$$1 / n!$ . Wir haben gesehen, dass andere Variationen mit zunehmender Anzahl zunehmen $$$n$ unbegrenzt, auch ich $$$n!$ und Zickzackzahlen. Gibt es Varianten des Fakultätsprozesses, die zu einer endlichen Grenze konvergieren, die nicht Null ist?

Zunächst kam mir folgender Algorithmus in den Sinn:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

Wir durchlaufen ganzzahlige Werte von $$$n$ bis zu $$$1$ Berechnung des aktuellen Produkts / Quotienten im Prozess $$$q$ . Bei jedem Schritt ist der aktuelle Wert $$$q$ mehr $$$1$ teilen wir es durch den nächsten Zähler, andernfalls führen wir die Multiplikation durch. Dieses Schema implementiert eine Art Feedback-Management oder Zielsuchverhalten. Wenn $$$q$ Wenn wir zu groß werden, reduzieren wir es. Wenn es zu klein ist, erhöhen wir es. Ich schlug das vor, während ich mich bemühte $$$n$ bis unendlich $$$q$ konvergiert zu einem sich ständig verengenden Wertebereich neben $$$1$ .

Aber das Experiment warf mir eine weitere Überraschung:


Eine solche Sägezahnwelle ist nicht ganz das, was ich erwartet habe. Seltsamerweise ist die Kurve nicht symmetrisch $$$1$ ;; Abweichungen von oben haben eine größere Amplitude als von unten. Diese Verzerrung ist jedoch eher visuell als mathematisch. Als $$$q$ ist privat, Entfernung von $$$1$ vorher $$$10$ gleich wie Abstand von $$$1$ vorher $$$\ frac {1} {10}$ aber auf einer linearen Skala sieht das nicht so aus. Sie können dies beheben, indem Sie ein logarithmisches Diagramm des Quotienten erstellen:


Jetzt ist der Graph symmetrisch oder zumindest ungefähr gleich und relativ zum Wert zentriert $$$0$ Welches ist der Logarithmus $$$1$ . Aber es bleibt ein ernsthafteres Geheimnis. Die Sägezahnwelle ist sehr regelmäßig und hat eine Periode $$$4$ , ohne Anzeichen einer Kompression in Richtung des erwarteten Grenzwerts zu zeigen $$$\ log q = 0$ . Numerische Werte legen nahe, dass wann $$$n$ bis unendlich konvergieren die Spitzen der Kurve zu einem etwas höheren Wert $$$q = \ frac {5} {3}$ und die Tiefs nähern sich einem etwas niedrigeren Wert $$$q = \ frac {3} {5}$ . (Entsprechende Basislogarithmen $$$10$ sind ungefähr gleich $$$\ pm0.222$ ) Ich konnte nicht herausfinden, warum dies geschieht. Vielleicht kann jemand erklären.

Ein Fehler mit diesem gierigen Algorithmus bedeutet nicht, dass wir die faktorielle Konvergenz nicht teilen können $$$q = 1$ .

_{Wenn wir mit den Logarithmen von Zählern arbeiten, wird dieses Verfahren zum Fall eines bekannten Rechenproblems, das als "Problem der Aufteilung einer Menge von Zahlen" bezeichnet wird. Wir erhalten viele reelle Zahlen, und wir müssen sie in zwei Mengen aufteilen, deren Summe gleich oder der Gleichheit so nahe wie möglich kommt. Dies ist eine nachweislich schwierige Aufgabe, wird aber auch ( PDF ) als "einfachste komplexe Aufgabe" bezeichnet.}

Für jeden $$$n$ Wir können feststellen, dass wir bei Verwendung der inversen Werte einer anderen Teilmenge von Zählern eine bessere Annäherung an erhalten $$$n! = 1$ . Für kleine $$$n$ Wir können dieses Problem mit brutaler Gewalt lösen: Betrachten Sie einfach alles $$$2 ^ n$ Teilmengen und wählen Sie die besten.

Ich habe die optimalen Partitionen bis berechnet $$$n = 30$ wenn Sie aus einer Milliarde Optionen auswählen müssen.


Offensichtlich wird die Grafik flacher. Sie können dieselbe Methode verwenden, um die Konvergenz zu einem anderen Wert im Bereich von zu erzwingen $$$0$ vorher $$$n!$ .

Und so bekommen wir eine weitere Antwort auf die Frage von Tweet und haben unsere Reise begonnen. Was passiert, wenn wir teilen und nicht multiplizieren? $$$n!$ ? Alles was wir wollen.