Mian–Chowla-Folge

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

Für ${\displaystyle n>1}$ ist ${\displaystyle a_{n}}$ die kleinste ganze Zahl, für die jede paarweise Summe ${\displaystyle a_{i}+a_{j}}$ verschieden ist für alle ${\displaystyle i\leq n,j\leq n}$.

Die Folge wurde von Abdul Majid Mian and Sarvadaman Chowla im Jahr 1944 erfunden.^[1][2]

Die Folge startet mit ${\displaystyle a_{1}=1}$.

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

Angenommen, ${\displaystyle a_{3}=3}$. Man betrachtet alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2}$ und ${\displaystyle a_{3}=3}$ und erhält ${\displaystyle 1+1=2,\;1+2=3,\;1+3=4,\;2+2=4,\;2+3=5}$ und ${\displaystyle 3+3=6}$. Die so erhaltenen Summen ${\displaystyle 2,3,4,4,5}$ und ${\displaystyle 6}$ sind aber nicht alle paarweise verschieden, weil ${\displaystyle 1+3=2+2=4}$ ist. Somit muss ${\displaystyle a_{3}\not =3}$ sein.

Angenommen, ${\displaystyle a_{3}=4}$. Man betrachtet alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2}$ und ${\displaystyle a_{3}=4}$ und erhält ${\displaystyle 1+1=2,\;1+2=3,\;1+4=5,\;2+2=4,\;2+4=6}$ und ${\displaystyle 4+4=8}$. Die so erhaltenen Summen ${\displaystyle 2,3,4,5,6}$ und ${\displaystyle 8}$ sind alle paarweise verschieden, somit ist ${\displaystyle a_{3}=4}$.

Angenommen, ${\displaystyle a_{4}=5}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2,a_{3}=4}$ und ${\displaystyle a_{4}=5}$ betrachten und erhält unter anderem ${\displaystyle 1+5=2+4=6}$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =5}$.

Angenommen, ${\displaystyle a_{4}=6}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2,a_{3}=4}$ und ${\displaystyle a_{4}=6}$ betrachten und erhält unter anderem ${\displaystyle 2+6=4+4=8}$, somit sind auch in diesem Fall nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =6}$.

Angenommen, ${\displaystyle a_{4}=7}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2,a_{3}=4}$ und ${\displaystyle a_{4}=7}$ betrachten und erhält unter anderem ${\displaystyle 1+7=4+4=8}$, somit sind auch in diesem Fall nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =7}$.

Angenommen, ${\displaystyle a_{4}=8}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=1,a_{2}=2,a_{3}=4}$ und ${\displaystyle a_{4}=8}$ betrachten. In diesem Fall erhält man die Summen ${\displaystyle 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 ${\displaystyle 8+8=16}$. Es sind alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle 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)

• Die Mian–Chowla-Folge ist per Definition eine unendliche Sidon-Folge.
• Für den Grenzwert der Summe der Inversen der Folgenglieder ${\displaystyle a_{n}}$ der Mian–Chowla-Folge gilt:^[3]

${\displaystyle 2{,}158452685\leq \sum _{i=1}^{\infty }{\frac {1}{a_{i}}}\leq 2{,}15846062}$

Beginnt man die obige Zahlenfolge nicht mit ${\displaystyle a_{1}=1}$, sondern mit ${\displaystyle 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 ${\displaystyle a_{1}=0}$, ${\displaystyle a_{2}=1}$ und ${\displaystyle a_{3}=3}$ schon bekannt.

Angenommen, ${\displaystyle a_{4}=4}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=0,a_{2}=1,a_{3}=3}$ und ${\displaystyle a_{4}=4}$ betrachten und erhält unter anderem ${\displaystyle 0+4=1+3=4}$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =4}$.

Angenommen, ${\displaystyle a_{4}=5}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=0,a_{2}=1,a_{3}=3}$ und ${\displaystyle a_{4}=5}$ betrachten und erhält unter anderem ${\displaystyle 1+5=3+3=6}$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =5}$.

Angenommen, ${\displaystyle a_{4}=6}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=0,a_{2}=1,a_{3}=3}$ und ${\displaystyle a_{4}=6}$ betrachten und erhält unter anderem ${\displaystyle 0+6=3+3=6}$, somit sind nicht alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}\not =6}$.

Angenommen, ${\displaystyle a_{4}=7}$. Dann muss man alle möglichen Summen von ${\displaystyle a_{1}=0,a_{2}=1,a_{3}=3}$ und ${\displaystyle a_{4}=7}$ betrachten. In diesem Fall erhält man die Summen

${\displaystyle 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 ${\displaystyle 7+7=14}$.

Es sind alle erhaltenen Summen paarweise verschieden, es ist also ${\displaystyle a_{4}=7}$.

• Ulam-Folge

• 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). 

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

1. ↑ Abdul Majid Mian, Sarvadaman Chowla: On the B₂-sequences of Sidon. Proc. Nat. Acad. Sci. India, A14, 1944, S. 3–4. 
2. ↑ Folge A005282 in OEIS
3. ↑ Raffaele Salvia: A New Lower Bound for the Distinct Distance Constant. (PDF) Journal of Integer Sequences, Vol. 18, 2015, S. 1–4 (Article 15.4.8), abgerufen am 14. Juni 2024 (Abschnitt 2.2: The reciprocal sum of the Mian-Chowla sequence).