Mian–Chowla-Folge

In der Mathematik ist die Mian–Chowla-Folge (englisch Mian–Chowla sequence) eine Folge von ganzen Zahlen, die den Anfangswert $a_1=1$ hat und wie folgt rekursiv definiert ist:

Für $n>1$ ist $a_n$ die kleinste ganze Zahl, für die jede paarweise Summe $a_i+a_j$ verschieden ist für alle $i\le n,j\le n$.

Die Folge wurde von Abdul Majid Mian and Sarvadaman Chowla im Jahr 1944 erfunden.

Berechnung

Die Folge startet mit $a_1=1$.

Angenommen, $a_2=2$. Man betrachtet alle möglichen Summen von $a_1=1$ und $a_2=2$. Man erhält die Summen $a_1+a_1=1+1=2,a_1+a_2=1+2=3$ und $a_2+a_2=2+2=4$. Die so erhaltenen Summen $2,3$ und $4$ sind alle paarweise verschieden, somit ist tatsächlich $a_2=2$.

Angenommen, $a_3=3$. Man betrachtet alle möglichen Summen von $a_1=1,a_2=2$ und $a_3=3$ und erhält $1+1=2,1+2=3,1+3=4,2+2=4,2+3=5$ und $3+3=6$. Die so erhaltenen Summen $2,3,4,4,5$ und $6$ sind aber nicht alle paarweise verschieden, weil $1+3=2+2=4$ ist. Somit muss $a_3=3$ sein.

Angenommen, $a_3=4$. Man betrachtet alle möglichen Summen von $a_1=1,a_2=2$ und $a_3=4$ und erhält $1+1=2,1+2=3,1+4=5,2+2=4,2+4=6$ und $4+4=8$. Die so erhaltenen Summen $2,3,4,5,6$ und $8$ sind alle paarweise verschieden, somit ist $a_3=4$.

Angenommen, $a_4=5$. Dann muss man alle möglichen Summen von $a_1=1,a_2=2,a_3=4$ und $a_4=5$ betrachten und erhält unter anderem $1+5=2+4=6$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=5$.

Angenommen, $a_4=6$. Dann muss man alle möglichen Summen von $a_1=1,a_2=2,a_3=4$ und $a_4=6$ betrachten und erhält unter anderem $2+6=4+4=8$, somit sind auch in diesem Fall nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=6$.

Angenommen, $a_4=7$. Dann muss man alle möglichen Summen von $a_1=1,a_2=2,a_3=4$ und $a_4=7$ betrachten und erhält unter anderem $1+7=4+4=8$, somit sind auch in diesem Fall nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=7$.

Angenommen, $a_4=8$. Dann muss man alle möglichen Summen von $a_1=1,a_2=2,a_3=4$ und $a_4=8$ betrachten. In diesem Fall erhält man die Summen $1+1=2,1+2=3,2+2=4,1+4=5,2+4=6,4+4=8,1+8=9,2+8=10,4+8=12$ und $8+8=16$. Es sind alle erhaltenen Summen paarweise verschieden, es ist also $a_4=8$.

Insgesamt besteht die Mian–Chowla-Folge aus folgenden Gliedern:

1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, … (Vorlage:OEIS)

Eigenschaften

• Die Mian–Chowla-Folge ist per Definition eine unendliche Sidon-Folge.
• Für den Grenzwert der Summe der Inversen der Folgenglieder $a_n$ der Mian–Chowla-Folge gilt:

$2,158452685\le \sum _{i=1}^{\mathrm{\infty }}\frac{1}{a_i}\le 2,15846062$

Ähnliche Zahlenfolge

Beginnt man die obige Zahlenfolge nicht mit $a_1=1$, sondern mit $a_1=0$, belässt aber die Rekursion gleich, so erhält man die folgende Zahlenfolge:

0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, … (Vorlage:OEIS)

Die einzelnen Glieder sind jeweils um 1 kleiner als bei der obigen Mian–Chowla-Folge.

Beispiel:

Seien $a_1=0$, $a_2=1$ und $a_3=3$ schon bekannt.

Angenommen, $a_4=4$. Dann muss man alle möglichen Summen von $a_1=0,a_2=1,a_3=3$ und $a_4=4$ betrachten und erhält unter anderem $0+4=1+3=4$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=4$.

Angenommen, $a_4=5$. Dann muss man alle möglichen Summen von $a_1=0,a_2=1,a_3=3$ und $a_4=5$ betrachten und erhält unter anderem $1+5=3+3=6$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=5$.

Angenommen, $a_4=6$. Dann muss man alle möglichen Summen von $a_1=0,a_2=1,a_3=3$ und $a_4=6$ betrachten und erhält unter anderem $0+6=3+3=6$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also $a_4=6$.

Angenommen, $a_4=7$. Dann muss man alle möglichen Summen von $a_1=0,a_2=1,a_3=3$ und $a_4=7$ betrachten. In diesem Fall erhält man die Summen

$0+0=0,0+1=1,0+3=3,0+7=7,1+1=2,1+3=4,1+7=8,3+3=6,3+7=10$ und $7+7=14$.

Es sind alle erhaltenen Summen paarweise verschieden, es ist also $a_4=7$.

Siehe auch

• Ulam-Folge

Literatur

• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld
• Vorlage:PlanetMath