The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een rijtje getallen aan het maken bent, maar met een heel specifieke en wat eigenaardige regel. Je begint met de getallen 1 en 2. Daarna moet je het volgende getal kiezen, maar je mag niet zomaar een willekeurig getal nemen. Je moet het kleinste mogelijke getal kiezen dat:

Groter is dan het vorige getal.
Gemaakt kan worden door twee of meer opeenvolgende getallen uit je bestaande rij bij elkaar op te tellen.

Dit is wat wiskundigen de "Hofstadter-rij" noemen. Het klinkt simpel, maar het gedrag van deze rij is al decennia lang een raadsel. De vraag was: Zal deze rij uiteindelijk bijna elk getal bevatten, of laat hij er oneindig veel over?

In dit nieuwe artikel bewijst de auteur, Quanyu Tang, dat deze rij oneindig veel getallen overlaat. Hij lost hiermee een oud raadsel op.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. De "Gierige Bouwer"

Stel je voor dat je een muur aan het bouwen bent met bakstenen. Je hebt al bakstenen met nummers 1 en 2.
Je wilt de volgende baksteen leggen. Je mag alleen een nieuwe baksteen kiezen als je die kunt "bouwen" door een stukje van je bestaande muur (opeenvolgende bakstenen) bij elkaar op te tellen.

1 + 2 = 3 (Dus 3 mag erbij).
2 + 3 = 5 (Dus 5 mag erbij).
1 + 2 + 3 = 6 (Dus 6 mag erbij).

Maar wacht even! Waarom is 4 niet in de rij?

1+2=3 (te klein).
2+3=5 (te groot).
Er is geen combinatie van opeenvolgende getallen die precies 4 oplevert.
Dus 4 wordt "overgeslagen". De rij gaat door met 5, 6, 8, 10... en laat 7, 9, 12, 13, etc. over.

De vraag was: Zal de bouwer ooit stoppen met het overslaan van getallen, of blijft hij er oneindig veel overlaten?

2. Het bewijs: De "Gaten" worden groter

Vroeger dachten veel mensen dat de rij misschien "dicht" zou worden, alsof de gaten uiteindelijk zouden opvullen. Tang bewijst echter het tegenovergestelde.

Hij gebruikt een slimme truc: in plaats van alleen naar de getallen te kijken, kijkt hij naar het verschil tussen het getal in de rij en zijn plaatsnummer.

Het 1e getal is 1 (verschil 0).
Het 2e getal is 2 (verschil 0).
Het 3e getal is 3 (verschil 0).
Het 4e getal is 5 (verschil 1).
Het 5e getal is 6 (verschil 1).
...
Het 20e getal is misschien 30 (verschil 10).

Tang laat zien dat dit verschil (hoeveel de rij "achterloopt" op de natuurlijke rij 1, 2, 3...) altijd groter wordt.
Het is alsof je een trein hebt die steeds sneller rijdt dan de snelweg waar hij op moet blijven. De trein (de rij) neemt steeds meer afstand van de snelweg (de natuurlijke getallen). Omdat de trein steeds verder vooruit springt, laat hij op de snelweg steeds meer lege plekken (de overgeslagen getallen) achter.

Conclusie 1: De rij laat oneindig veel getallen over. De "gaten" worden niet kleiner, ze worden juist groter.

3. Hoe snel groeit de rij? (De snelheidsmeting)

De tweede vraag was: Hoe snel groeit deze rij eigenlijk?
Als de rij heel snel groeit, betekent dat dat er heel veel gaten zijn. Als hij langzaam groeit, zitten de gaten dichter bij elkaar.

Tang heeft een wiskundige formule gevonden die de snelheid van deze "trein" begrenst. Hij zegt: "De rij groeit niet sneller dan een bepaalde macht van het aantal stappen."
Het is alsof je zegt: "Zelfs als deze trein razendsnel gaat, zal hij nooit sneller zijn dan een formule die we kunnen schrijven."
De formule is complex (een beetje als een ingewikkeld recept), maar het belangrijkste is: de rij groeit "polynoommatig". Dat klinkt als een wiskundig woord, maar het betekent simpelweg dat de rij niet exponentieel (zoals 2, 4, 8, 16...) uit de hand loopt, maar in een beheersbaar, zij het snel, tempo groeit.

4. Waarom is dit belangrijk?

Voor wiskundigen is dit een groot feest.

Het raadsel is opgelost: We weten nu zeker dat de Hofstadter-rij niet "vol" wordt. Er zijn oneindig veel getallen die deze specifieke bouwmethode nooit zal kiezen.
De methode is krachtig: De auteur heeft laten zien dat dit niet alleen geldt voor de startgetallen 1 en 2, maar voor elke startreeks van positieve getallen. Het is een universeel principe.
De brug tussen theorie en praktijk: Hij gebruikt moderne wiskunde (over "convexe verzamelingen" en "verschillen") om een oud probleem op te lossen. Het is alsof hij een oude sleutel (de vraag) heeft gevonden die past in een heel nieuw slot (de moderne theorie).

Samenvatting in één zin

Deze paper bewijst dat de "Hofstadter-rij", een getallenlijst die bouwt door opeenvolgende sommen te maken, een "gierige" bouwer is die oneindig veel getallen overlaat, en dat we nu precies weten hoe snel deze rij groeit.

Het is een mooi voorbeeld van hoe wiskunde laat zien dat zelfs in een simpel spelletje met getallen, er diepe, verborgen patronen zitten die wachten om ontdekt te worden.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "THE HOFSTADTER CONSECUTIVE-SUM SEQUENCE OMITS INFINITELY MANY POSITIVE INTEGERS" van Quanyu Tang, geschreven in het Nederlands.

Titel en Context

Titel: De Hofstadter-sequentie van opeenvolgende sommen slaat oneindig veel positieve gehele getallen over.
Auteur: Quanyu Tang.
Onderwerp: Getaltheorie en combinatoriek (specifiek zelfgenererende sequenties en additieve combinatoriek).

1. Het Probleem

Het artikel onderzoekt een specifieke "greedy" (gierige) zelfgenererende rij, bekend als de Hofstadter-sequentie (OEIS A005243). De rij $(a_n)_{n \ge 1}$ wordt gedefinieerd als volgt:

Startwaarden: $a_1 = 1, a_2 = 2$ .
Voor $k \ge 3$ : $a_k$ is het kleinste geheel getal groter dan $a_{k-1}$ dat kan worden geschreven als de som van minstens twee opeenvolgende eerdere termen van de rij.

Formeel:
$a_k = \sum_{i=p}^{q} a_i$
voor zekere $1 \le p \le q \le k-1 $met$ q - p \ge 1$.

De rij begint als: $1, 2, 3, 5, 6, 8, 10, 11, 14, 16, \dots$
Het getal 4 ontbreekt (want $1+2=3 $,$ 2+3=5$), evenals 7, 9, 12, enz.

De centrale vraag (Probleem 1.1): Wat is het asymptotische gedrag van deze rij?
Specifiek wordt de volgende conjecture uit de OEIS (Conjecture 1.2) onderzocht: Slaat de rij oneindig veel positieve gehele getallen over? Numerieke data suggereerde dat de rij "de meeste" getallen bevatte, maar de auteurs vermoedden dat er oneindig veel gaten zijn.

2. Methodologie

Tang gebruikt een combinatie van elementaire getaltheorie, Diophantische vergelijkingen en moderne resultaten uit de additieve combinatoriek.

A. Kwalitatieve Analyse (Onderschatting)

Het doel is te bewijzen dat de rij $a_n$ sneller groeit dan lineair ( $a_n \approx n$ ).

Definitie van de afwijking: Er wordt een nieuwe rij gedefinieerd: $b_n = a_n - n$ . Als $b_n$ onbegrensd is, dan slaat de rij oneindig veel getallen over.
Monotonie: Eerst wordt bewezen dat $(b_n)$ monotoon niet-dalend is voor $n \ge s$ (waar $s$ de lengte van de startsequentie is).
Reductie tot een tegenspraak: De auteurs nemen aan dat $(b_n)$ begrensd is. Dit impliceert dat $a_n$ uiteindelijk lineair wordt: $a_n = n + B$ voor grote $n$ .
Analyse van machten van 2:
- Een cruciaal lemma stelt dat een getal als som van opeenvolgende positieve gehele getallen kan worden geschreven dan en slechts dan als het geen macht van 2 is.
- Als $a_n$ lineair zou zijn, zouden grote machten van 2 ($2^r$) moeten voorkomen in de rij.
- De auteurs analyseren hoe deze machten van 2 kunnen worden geschreven als sommen van eerdere termen. Dit leidt tot een vergelijking van de vorm:
  $2^{r+1} = v^2 + v + E$
  waarbij $v$ en $E$ afhangen van de structuur van de rij.
Diophantische eindigheid: Met behulp van een resultaat van Schinzel en Tijdeman (Corollary 2.3) wordt aangetoond dat de vergelijking $v^2 + v + E = 2^k$ $v^{2} + v + E = 2^{k}$ slechts een eindig aantal oplossingen heeft voor $k > 2$ $k > 2$ . Dit staat in strijd met de aanname dat er oneindig veel machten van 2 in de rij voorkomen als deze lineair zou zijn.
- Conclusie: De aanname dat $b_n$ begrensd is, is fout. Dus $b_n \to \infty$ .

B. Kwantitatieve Analyse (Bovenste Schatting)

Voor de klassieke rij $(1, 2)$ wordt een polynomiale bovenste schatting afgeleid.

Greedy Enumeratie: De rij $(a_n)$ is precies de stijgende enumeratie van alle getallen die als som van $\ge 2$ opeenvolgende termen kunnen worden geschreven.
Prefix-sommen en Convexiteit: De auteurs definiëren prefix-sommen $s_m = \sum_{i=1}^m a_i$ . De verzameling van deze prefix-sommen vormt een convex verzameling (de verschillen tussen opeenvolgende elementen zijn strikt stijgend).
Verschilverzamelingen: Een som van opeenvolgende termen is een verschil van twee prefix-sommen. Het aantal representeerbare getallen tot een bepaalde grens wordt gekoppeld aan de grootte van de verschilverzameling $S_m - S_m$ .
Bloom's Bound: Er wordt een recent resultaat van Bloom (Theorem 4.6) gebruikt voor de grootte van verschilverzamelingen van eindige convexe verzamelingen:
$|A - A| \ge c |A|^{6681/4175 - \eta}$
Recursie en Iteratie: Door deze ondergrens te combineren met de greedy-structuur, wordt een recursieve ongelijkheid voor $a_n$ afgeleid. Door deze recursie te itereren, wordt een polynomiale bovenste schatting verkregen.

3. Belangrijkste Resultaten

Hoofdstelling 1 (Kwalitatief - Theorema 1.4 & Corollary 1.5)

Voor elke eindige startsequentie van positieve gehele getallen:

De rij $b_n = a_n - n$ is monotoon niet-dalend en onbegrensd.
Gevolg: $a_n = n + \omega(1)$ .
Betekenis: De rij slaat oneindig veel positieve gehele getallen over. Dit bevestigt Conjecture 1.2 uit de OEIS.

Hoofdstelling 2 (Kwantitatief - Theorema 1.6)

Voor de klassieke rij (startend met 1, 2) geldt voor elke $\varepsilon > 0$ :
$a_n \ll_\varepsilon n^{4175/2506 + \varepsilon}$

De exponent is ongeveer $1.666$.
Dit is de eerste polynomiale bovenste schatting voor dit probleem.

4. Significatie en Discussie

Bevestiging van een langdurige vermoeden: Het artikel lost een open probleem op dat door Hofstadter zelf en later door de OEIS-community is gesteld. Het bewijst dat de rij niet "dicht" is bij de natuurlijke getallen, ondanks numerieke indrukken dat hij dat wel lijkt te zijn.
Verbinding tussen gebieden: Het werk verbindt de theorie van zelfgenererende rijen met diepe resultaten uit de additieve combinatoriek (convexe verzamelingen en verschilverzamelingen) en Diophantische vergelijkingen.
Gaten in de kennis: Hoewel er een ondergrens ( $a_n > n$ $a_{n} > n$ ) en een bovenste schatting ( $a_n \lesssim n^{1.666}$ $a_{n} ≲ n^{1.666}$ ) zijn, blijft er een aanzienlijke kloof.
- Numerieke data (tot $n=30.000$ ) suggereert dat de groei veel dichter bij lineair ligt, mogelijk met een exponent $\alpha$ rond $1/3 $voor de afwijking$ b_n \approx n^\alpha$.
- De auteurs merken op dat als een vermoeden van Erdős en Hegyvári over de grootte van verschilverzamelingen waar is, de methode zou kunnen leiden tot een schatting van $a_n \le n^{1+o(1)}$ , maar de huidige iteratiemethode levert dit nog niet op.

Samenvatting

Quanyu Tang bewijst wiskundig dat de Hofstadter-sequentie van opeenvolgende sommen oneindig veel gehele getallen overslaat. Dit wordt gedaan door aan te tonen dat de rij sneller groeit dan lineair. Daarnaast wordt een eerste kwantitatieve bovengrens geleverd, wat een belangrijke stap is in het begrijpen van de asymptotische dichtheid van deze fascinerende zelfgenererende rij.