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\leq n,j\leq 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}\not =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}\not =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}\not =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}\not =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, … (Folge A005282 in 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\leq \sum _{i=1}^{\infty }{\frac {1}{a_{i}}}\leq 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, … (Folge A025582 in 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}\not =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}\not =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}\not =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

• Steven R. Finch: Mathematical Constants (Section 2.20.2). Cambridge University Press, 2003, ISBN 0-521-81805-2, S. 164: B2-Sequences (Leseprobe auf sites.oxy.edu [PDF]). 
• Richard Kenneth Guy: Unsolved Problems in Number Theory, Volume I, Second Edition. Springer Science+Business Media, New York 1994, ISBN 1-4899-3587-8, S. 228–229: B2-Sequences (eingeschränkte Vorschau in der Google-Buchsuche). 

Weblinks

• Eric W. Weisstein: Mian-Chowla Sequence. In: MathWorld (englisch).
• Mian-Chowla sequence. In: PlanetMath. (englisch)