In 1978 liet Nathaniel Hellerstein zich inspireren door onderstaande passage uit de stripreeks Peanuts voor het definiëren van de Linus-reeks¹.

Fragment uit de stripreeks Peanuts dat inspiratie gaf voor de definitie van de Linus-reeks.

De Linus-reeks bestaat uit een opeenvolging van enen en tweeën, waarbij het volgende cijfer telkens gekozen wordt zodat het langst mogelijke herhaalde patroon aan het einde van de reeks vermeden wordt. We starten met het cijfer 1:

1

Als het volgende cijfer nu opnieuw een 1 zou zijn, dan krijgen we een herhaald patroon. Daarom voegen we achteraan het cijfer 2 toe:

12

Als we een 2 kiezen als derde cijfer, dan krijgen we 22 op het einde, wat opnieuw een herhaald patroon vormt. We vermijden dit door te kiezen voor het cijfer 1:

121

En wat nu? Als we het cijfer 2 achteraan zouden toevoegen, dan krijgen we het overmatig ordelijke 1212. Daarom kiezen we opnieuw voor het cijfer 1:

1211

Maar nu zien de enen op het einde er nogal zelfvoldaan uit, dus kiezen we voor 2 als volgende cijfer:

12112

En zo gaan we verder. De regel die we hanteren is om de langste verdubbelde suffix te vermijden: dit is de langst mogelijke herhaalde reeks van cijfers aan het einde van de reeks. Als we bijvoorbeeld op dit punt achteraan de reeks een 1 zouden toevoegen dan krijgen we de reeks 121121, waarbij het einde van de reeks (inderdaad, de volledige reeks) een herhaling vormt van de reeks van drie cijfers 121. Als we echter achteraan een 2 zouden toevoegen, dan krijgen we de reeks 121122, waardoor we achteraan slechts een herhaling van één cijfer (2) krijgen. Daarom kiezen we er in dit geval dus voor om achteraan het cijfer 2 toe te voegen.

Weliswaar was dit niet echt de reeks die het personage Linus in gedachten had in bovenstaande passage uit de strip, maar op zichzelf opent ze wel een heel nieuwe wereld met tal van verrassende eigenschappen², zoals wel eens meer het geval is met dit soort zaken.

Bovendien is het ook mogelijk om een gerelateerde reeks op te bouwen door telkens de lengte van de langst mogelijke herhaalde reeks bij te houden die vermeden wordt in de Linus-reeks. Dit wordt de Sally-reeks³ genoemd.

Opgave

We zeggen dat een string $$v$$ een suffix is van een gegeven string $$s$$ als er een string $$u$$ bestaat zodat $$s = uv$$, of met andere woorden als de string $$s$$ eindigt op de string $$v$$. De lege string en de string $$s$$ zijn per definitie respectievelijk de korste en langste suffix van de string $$s$$.

We zeggen dat een suffix $$v$$ een verdubbelde suffix is van een gegeven string $$s$$ als er een string $$u$$ bestaat zodat $$s = uvv$$.

In deze opgave beschouwen we enkel strings $$s$$ die bestaan uit de cijfers 1 en 2. Gevraagd wordt:

Schrijf een functie lvs waaraan een string $$s$$ moet doorgegeven worden. De functie moet de lengte van de langste verdubbelde suffix van $$s$$ teruggeven.
Schrijf een functie uitbreiding waaraan een string $$s$$ moet doorgegeven worden. De functie moet een tuple met drie elementen teruggeven: i) de lengte van de langste verdubbelde suffix van $$s$$1, ii) de lengte van de langste verdubbelde suffix van $$s$$2, en iii) de string $$s$$1 of $$s$$2 waarvan de langste verdubbelde suffix het kortst is (kies voor $$s$$1 indien de langste verdubbelde suffix van beide even lang is).

Opmerking

Met de string $$s$$1 bedoelen we de string $$s$$ die achteraan aangevuld werd met het cijfer 1. Analoog bekomen we de string $$s$$2 door op het einde van de string $$s$$ nog een cijfer 2 toe te voegen.
Schrijf een functie linus waaraan een getal $$n \in \mathbb{N}$$ moet doorgegeven worden. De functie moet een string $$s$$ teruggeven die de Linus-reeks van lengte $$n$$ voorstelt. Deze string wordt opgebouwd door te vertrekken vanaf de lege string, en telkens achteraan een 1 of een 2 toe te voegen die ervoor zorgt dat de string die zo ontstaat een zo kort mogelijke langste verdubbelde suffix heeft (voeg een 1 toe indien de langste verdubbelde suffix in beide gevallen even lang is). Deze procedure blijf je herhalen totdat je een string van lengte $$n$$ bekomt.
Schrijf een functie sally waaraan een getal $$n \in \mathbb{N}$$ moet doorgegeven worden. De functie moet het $$n$$-de getal uit de Sally-reeks teruggeven. Om dit getal te bepalen vertrekken we van de Linus-reeks van lengte $$n$$, voegen daar achteraan respectievelijk het cijfer 1 en 2 aan toe, en bepalen telkens de lengte van de langste verdubbelde suffix. Het grootste van die twee lengtes is het getal dat door de functie moet teruggegeven worden.

Voorbeeld

        >>> lvs('1211')
1
>>> lvs('1212')
2

>>> uitbreiding('1')
(1, 0, '12')
>>> uitbreiding('12')
(0, 1, '121')
>>> uitbreiding('121')
(1, 2, '1211')
>>> uitbreiding('1211')
(1, 0, '12112')
>>> uitbreiding('12112')
(3, 1, '121122')

>>> linus(0)
''
>>> linus(1)
'1'
>>> linus(6)
'121122'
>>> linus(40)
'1211221211212211211122121122111211221211'

>>> sally(0)
0
>>> sally(1)
1
>>> sally(6)
1
>>> sally(11)
6

Epiloog: AAAAAAAAAAUUGH

In 1947 werkte Charles M. Schulz als kunstleraar op een school in Minneapolis, toen de boekhoudafdeling een mooie roodharige dame met de naam Donna Mae Johnson aanwierf. "Ik vond haar gewoonweg geweldig" zei Schulz. Hij kon niet aan de verleiding weerstaan om zo vaak mogelijk op de tweede verdieping van zijn school te passeren en stripfiguurtjes op haar kalender te tekenen, en in februari 1950 begonnen ze te daten.

Het kleine roodharige meisje is een personage dat nooit te zien is in de stripreeks Peanuts van Charles M. Schulz. Ze is de persoon waarop Charlie Brown verliefd is, als symbool van onbeantwoorde liefde. Ondanks het feit dat ze nooit in de stripreeks te zien is, duikt ze wel op in verschillende televisie-episodes waarin ook haar naam bekend gemaakt wordt: Heather Wold. Charlie Brown merkt haar het meest op als hij buiten zijn boterhammen aan het opeten is, maar hij slaagt er nooit in om zijn moed bijeen te rapen om haar aan te spreken.

Het probleem was echter dat Donna er nog een tweede vriendje op nahield. Een plaatselijke jongen met de naam Alan Wold met wie ze als sinds 1948 samen was. "Ik wist al heel snel in onze relatie dat het Al was die ik wilde", zei ze, "maar tegelijkertijd hield ik ook heel erg veel van Sparky". Op 8 mei 1950 vroeg ze aan haar dagboek "Hoe kan je ooit kiezen tussen die twee?".

Op 14 juni 1950, na het ondertekenen van een contract met een uitgeverij van kranten die zijn humoristische strip Peanuts wilde publiceren, stapte Schulz op haar af en vroeg haar ten huwelijk. Het enige dat ze kon uitbrengen was "Ik wil met niemand trouwen. Ik wil gewoon dat iedereen me met rust laat."

Hij bleef nog drie weken aandringen, maar ze was niet op andere gedachten te brengen. Schulz verhuisde uiteindelijk naar Colorado, trouwde met Joyce Halverson, bouwde met haar een gezin uit, maar bleef voor de rest van zijn leven contact houden met Donna. Op een nacht werd hij door sentiment overvallen toen hij Joni James hoorde zingen over onbeantwoorde liefde:

Dat was de mentale toestand waarin ik verkeerde toen Charlie Brown plots in mijn gedachten opdook, zittend op een speelplaats terwijl hij zijn boterhammen aan het opeten was, en hij kijkt over de speelplaats, en hij ziet een klein roodharig meisje, en van het ene ding kwam het andere, en zo ontstond de volledige reeks.

"Je raakt nooit echt over je eerste liefde heen", zei hij op 75-jarige leeftijd. "Je hele zijn wordt afgewezen wanneer een vrouw zegt 'Je bent het niet waard'."

Bronnen

Balister P, Kalikow S, Sarkar A (2007). The Linus sequence. Combinatorics, probability and computing 19(1), 21-46. ⁴