Die Stern-Brocot-Folge (A002487 in OEISA002487 ist die Bezeichnung der Zahlenfolge in der On-Line Encyclopedia of Integer Sequences), auch als „diatomische Folge von Stern und Brocot“ oder „Stern-Sequenz“ bekannt, ist eine Folge ganzer Zahlen, die unabhängig vom Mathematiker Gotthold Eisenstein und dem Uhrmacher Achille Brocot entdeckt und vom Mathematiker Moritz Stern genauer untersucht wurde.

Sie startet mit dem Zahlenpaar s0 = 0 und s1 = 1. Zusätzliche Glieder der Folge ergeben sich, indem fortgesetzt die bisherige Folge kopiert und in der Kopie zwischen je zwei Glieder deren Summe eingefügt wird. Die ersten 33 Glieder der Folge sind

0; 1; 1, 2; 1, 3, 2, 3; 1, 4, 3, 5, 2, 5, 3, 4; 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5; 1 …

wobei auch die folgende Stufentafel (Beginn der Folge mit s1 und Unterteilung bei den Semikolons „;“) zur besseren Darstellung verschiedener Eigenschaften benutzt wird:

1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 … 1 7 6 11 5 14 9 13 4 15 11 18 7 17 10 13 3 14 11 … 1 8 7 13 6 17 11 16 5 19 14 23 9 22 13 17 4 19 15 … 1 9 8 15 7 20 13 19 6 23 17 28 11 27 16 21 5 24 19 …

siehe #Eigenschaften der Stufentafel. Die Stern-Brocot-Folge weist einige bemerkenswerte mathematische Besonderheiten auf: Aufeinander folgende Zahlen der Folge sind einander teilerfremd und jedes mögliche Paar positiver, teilerfremder, ganzer Zahlen kommt genau einmal vor; das erlaubt mit ihr die Menge der rationalen Zahlen abzuzählen, siehe #Abzählung der rationalen Zahlen. Die Folge zählt ungerade Glieder im Pascal’schen Dreieck, Wege in Graphen oder Darstellungsweisen von Hyperbinärzahlen, siehe #Zähleigenschaften. Mit der Folge kann die am besten passende Zahnradpaarung für ein bestimmtes Übersetzungsverhältnis gefunden werden, was A. Brocot als erster erkannte,Die Anwendung wird beispielsweise beschrieben in: siehe #Stern-Brocot-Baum. Die größten Glieder in jeder Zeile der Stufentafel bilden die Fibonacci-Folge. Das Vorkommen einer Zahl in der Stufentafel ergibt sich aus der Euler’schen φ-Funktion. Die Position eines Zahlenpaars (a,b) in der Stufentafel hängt mit der Kettenbruch­entwicklung des Bruchs a/b zusammen.

Diese und andere Eigenschaften sowie ihr relativ geringer Bekanntheitsgrad haben Jean-Paul Delahaye veranlasst, die Folge „die verkannte Schwester der Fibonacci-Folge“ zu nennen.

Geschichte Gotthold Eisenstein veröffentlichte im Februar 1850 eine Arbeit über eine Zahlenreihe,

Er konnte einige der #Eigenschaften der Stufentafel angeben und regte M. Stern schon im Januar 1850 dazu an, die Reihe auch zu untersuchen. Stern entsprach 1858 mit seiner Arbeit, wie er schrieb, „leider zu spät, dem Wunsche meines unvergeßlichen Freundes;“ Eisenstein starb 1852 im Alter von nur 29 Jahren. Der Aufsatz von Brocot datiert auf das Jahr 1861.

Definition der Stern-Brocot-Folge mini|Abb. 1: Glieder der Folge aufgetragen über ihre Stelle in der Folge zeigen fraktale Strukturen. Die tiefsten Einschnitte liegen bei Zweierpotenzen.

Die Stern-Brocot-Folge s0, s1, s2,… ist durch das rekursive Bildungsgesetz

s2n= sn s2n+1= sn + sn+1

mit den Anfangswerten s0 = 0    und    s1 = 1

definiert. Das bedeutet in Worten: Die Folge beginnt mit null und eins. Glieder mit einer geraden Nummer sind gleich dem Glied mit der halben Nummer und Glieder mit einer ungeraden Nummer sind gleich der Summe der Glieder mit der halben Nummer ihres Vorgängers und Nachfolgers. Anders ausgedrückt zerlegt man die ungerade Nummer in zwei Teile, die so eng benachbart sind wie überhaupt möglich: eine Zahl und die daran anschließende Zahl. Das Folgenglied ist dann die Summe der Glieder mit diesen Teilnummern. Dieses Gesetz ähnelt dem der Fibonacci-Folge.

Das Bildungsgesetz für die Glieder an ungeraden Stellen kann wegen s2n = sn umgeformt werden in

s2n+1 = sn + sn+1 = s2n + s2(n+1) = s2n + s2n+2

Das entspricht dem eingangs angegebenen Rezept, aus dem Zahlenpaar (0,1) zusätzliche Glieder zu generieren, indem fortgesetzt die bisherige Folge kopiert und in der Kopie zwischen je zwei Glieder deren Summe eingefügt wird; M. Stern nannte das die Entwicklung (0,1).

Die ersten 100 Glieder der Folge sind:

n012345678910111213141516171819sn01121323143525341547n2021222324252627282930313233343536373839sn3857275837451659411710n4041424344454647484950515253545556575859sn3118135127929712513811310711n6061626364656667686970717273747576777879sn49561761151491341511187171013n8081828384858687888990919293949596979899sn314111982113185171219716911211916

Eisenstein und M. Stern betrachteten auch die Entwicklung zweier beliebiger natürlicher Zahlen (m,n). Wenn diese nicht teilerfremd sind, dann enthalten alle Glieder der Folge deren größten gemeinsamen Teiler k. Werden alle Glieder der Folge durch k geteilt, entsteht eine Folge mit teilerfremdem m und n, und nur diese brauchen untersucht zu werden. Die Entwicklung mit teilerfremdem m und n ist als Bruchstück in der Entwicklung (0,1) enthalten, denn in dieser kommen alle möglichen Paare teilerfremder Zahlen vor. Allerdings treten in diesen Bruchstücken nicht mehr alle positiven Zahlen auf, sondern nur solche, die als Summe ganzzahliger Vielfache von m und n darstellbar sind.

Die Stern-Brocot-Folge wurde auch auf Polynome verallgemeinert.

Quantitative Eigenschaften Berechnung der Folgenglieder Neben dem Bildungsgesetz aus der #Definition der Stern-Brocot-Folge gibt es weitere bemerkenswerte Methoden zur Berechnung von Folgengliedern. Der #Zusammenhang mit dem Pascal’schen Dreieck führt auf das explizite Bildungsgesetz

worin die Gaußklammer [·] auf die nächste Ganzzahl abrundet und „mod 2“ den Rest bei der Division durch zwei gibt, also eins bei ungeraden Zahlen und null bei geraden. Für große n erfordert diese Darstellung die Handhabung sehr großer Zahlen; beispielsweise lautet der Binomialkoeffizient .

Die folgenden Methoden basieren auf der mehrfachen Anwendung einer Berechnungsvorschrift: Nach dem Bildungsgesetz ist sk = sk/2, wenn k gerade, oder sk = s(k-1)/2 + s(k+1)/2, wenn k ungerade ist. Durch fortgesetzte Anwendung dieser Formeln werden alle benötigten Folgenglieder und schließlich sn berechnet. Beispielsweise ist s6 = s3 = s1 + s2 = s1 + s1 = 2 Die Anzahl der zu berechnenden Glieder wächst mit dem Logarithmus von n. Aus der Formel für #den nächsten Bruch leitet sich für das auf a, b folgende Glied c = a + b − 2r ab, wo r = a − [a/b]·b der Rest bei Division von a durch b ist (sodass a−r durch b teilbar und 0 ≤ r < b ist, [·] ist die Gaußklammer). Das Glied sn ergibt sich aus n−1 maliger Anwendung der Formel auf s0 und s1. Für n > 1 besteht der Zusammenhang sn = kn−1sn−1 − sn−2 Darin ist kj die größte ungerade Zahl für die j durch 2(kj−1)/2 teilbar ist.A037227 in OEIS

Weitere Formeln können aus den #Zähleigenschaften der Stern-Brocot-Folge abgeleitet werden.

Eigenschaften der Folge

Für die Glieder der Stern-Brocot-Folge gilt: Keine zwei geraden Glieder stehen hintereinander. Bei drei aufeinander folgenden Gliedern ist nicht nur die mittlere von ihnen ungerade; es sind aber auch nicht alle drei ungerade. Die Summe der beiden Nachbarn eines Gliedes ist durch selbiges teilbar. Das auf a,b folgende Paar b,c ergibt sich aus b/c = 1/(1+2[a/b]-a/b), wo die Gaußklammer [ · ] auf die nächste Ganzzahl abrundet. Zwei aufeinander folgende Glieder sind teilerfremd. Die Folge enthält jede Natürliche Zahl und alle möglichen Paare einander teilerfremder Zahlen. Ein bestimmtes Zahlenpaar kommt nur genau einmal in der Folge vor.

Die letzten drei Aussagen bedeuten, dass die Brüche s0/s1, s1/s2, s2/s3, s3/s4, s4/s5,… alle nicht negativen rationalen Zahlen ohne Zweifachnennungen durchlaufen, siehe auch #Abzählung der rationalen Zahlen und #Calkin-Wilf-Baum.

Eigenschaften der Stufentafel

M. Stern entwickelte seine Folge in Reihen, beginnend mit zwei natürlichen Zahlen (m,n), indem er fortgesetzt die Reihe kopierte und in der Kopie zwischen je zwei aufeinanderfolgende Zahlen die Summe derselben einfügte. Dies nannte er Entwicklung (m,n). Die Stern-Brocot-Folge ist die Entwicklung (0,1) und die #Stufentafel entsteht aus der Entwicklung (1,1); die erste Hälfte jeder ihrer Reihen ergibt sich aus der Entwicklung (1,2), die Eisenstein untersuchte. M. Stern definierte: Die Reihe (m,n), die entwickelt wird, ist die nullte Reihe, Jede Zahl einer Reihe ist ein Glied der Reihe und eine Gruppe ist eine Anzahl aufeinander folgender Glieder. Glieder, die aus der Summe ihrer Nachbarn entstanden, heißen Summenglieder, und alle anderen Stammglieder. Die Summenglieder stehen an geraden Stellen und die Stammglieder an ungeraden Stellen jeder Reihe außer der nullten. φ(n) ist die Eulersche φ-Funktion, d. h. die Anzahl der zu n teilerfremden Zahlen, die kleiner oder gleich n sind.

Die Entwicklung (1,1) beginnt mit

p p-te Reihe0 1,1 1 1,2,1 2 1,3,2,3,1 3 1,4,3,5,2,5,3,4,1 4 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1 5 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6,1 ︙︙usw.᨞ ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓…Δ = 011213231435253415473857275837451…

Entfernt man in jeder Reihe die endständige Eins, entstehen die Zeilen der eingangs angegebenen #Stufentafel. Die folgenden Eigenschaften der Reihen trug M. Stern zusammen, wenn nicht anders angegeben: Die Anzahl der Glieder in der p-ten Reihe ist 2p+1. Die Summe der Glieder in der p-ten Reihe ist 3p+1. Die Summe der Quotienten zweier aufeinander folgender Glieder in der Reihe ist (3·2p−1)/2. Die Summe der Kehrwerte der Produkte zweier aufeinander folgender Glieder in der Reihe ist eins. Übereinander stehende Glieder erzeugen eine Arithmetische Folge und die Differenzen in den Folgen ergeben ihrerseits die Stern-Brocot-Folge, vermerkt in der untersten, blau geschriebenen Zeile obiger Tabelle. Jede Reihe ist ein Palindrom, dessen Mitte bei Reihen ungerader Länge eine Zwei ist. Steht in einer Zeile die Gruppe und direkt darunter , dann gilt:

In der vierten Reihe steht beispielsweise 5,4,7 über 6,5,9 in der fünften Reihe, und es stimmt:

Jede Zahl n kommt sooft als Summenglied vor, wie es kleinere Zahlen gibt, die zu ihr teilerfremd sind; diese Anzahl ist φ(n). Eine Primzahl π kommt π−1-mal als Summenglied vor. In Zeile n−1 kommt n zum letzten Mal als Summenglied vor. Ab der n-ten Zeile kommt n in jeder Zeile φ(n) mal als Stammglied vor. Die Zahl n kommt in Zeile p sooft vor, wie die Zerlegung von n in zwei teilerfremde a, b gelingt, sodass die Summe der Teilnenner des zu a/b gleichen Kettenbruchs nicht größer als p ist. Beispielsweise lässt sich die Zahl fünf viermal in einander teilerfremde Zahlen zerlegen:

Entsprechend kommt fünf vor der dritten Reihe keinmal, in der dritten Reihe zweimal und in allen darauf folgenden Reihen viermal vor. Die Gruppe (a,b) steht in der Zeile p = k0+k1+…+km−1, wenn a/b gleich ist zum einfachen Kettenbruch (k0;k1,…,km). Beispielsweise ist in der fünften Reihe, die mit 1,6,5,9,4,11 beginnt:

Die Summe der Teilnenner der Kettenbrüche ist hier in allen Fällen sechs, d. h. eins mehr als die Zeilennummer fünf, so wie es sein muss. Die Gruppe (a,b) kommt in der ersten Hälfte einer Reihe vor, wenn die kleinste positive Zahl c, die mit a multipliziert den Rest 1 bei Division durch a+b ergibt, kleiner als (a+b)/2 ist:

|style="vertical-align: top;"|∃c: |style="text-align: center;vertical-align: top;"| ac ≡ 1 mod (a+b) |style="width: 4em;text-align: center;vertical-align: top;"|und |style="text-align: center;vertical-align: top;"|0 ≤ c < (a+b)/2 |style="width: 4em;text-align: center;vertical-align: top;"|→ |style="text-align: left;vertical-align: top;"|(a,b) kommt in der ersten Hälfte einer Reihe vor. |} So steht die Gruppe (5,9) in der ersten Hälfte der fünften Reihe, weil 5·3 = 15 ≡ 1 mod 14 und 3 < 14/2 = 7. Die Gruppe (9,5) andererseits liegt in der zweiten Hälfte, weil 9·11 ≡ (-5)·(-3) = 15 ≡ 1 mod 14 und 11 > 7.

Zähleigenschaften Zusammenhang mit dem Pascal’schen Dreieck