Hier is iets fantastisch — een machine gemaakt van breuken: \[ \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \] Begin met het getal 2 als seed. Vermenigvuldig de seed telkens met de volgende breuk, todat het product een geheel getal is (in dit geval is dit bij vermenigvuldiging met de breuk $$\frac{15}{2}$$). Neem nu dit geheel getal (15) als de nieuwe seed, en vermenigvuldig die seed opnieuw met elk van de breuken, totdat je opnieuw een geheel getal bekomt. Blijf deze procedure herhalen, en houd bij wanneer de seed een macht van twee is.

De eerste tweede macht ($$2^2 = 4$$) verschijnt na 19 stappen. Vijftig stappen later duikt $$2^3 = 8$$ op. Daarna verschijnt $$2^5 = 32$$ ongeveer 200 stappen verderop. Er ontstaat een patroon: de exponenten zijn 2, 3, 5, 7, 11, 13, …

Zo blijkt dat "alleen al deze veertien breuken een oneindig aantal priemgetallen bevatten, zelfs die waar nog niemand iets van afweet" schrijft Dominic Olivastro. "Er is iets enorm magisch aan." Deze PRIMEGAME techniek is gebaseerd op een Turing-complete esotherische programmeertaal genaamd FRACTRAN¹, die bedacht werd door John Horton Conway².

Opgave

Elke regel van het tekstbestand fractions.txt³ bestaat uit een patroon $$p \in \mathcal{P}$$, gevolgd door een spatie en een woord $$w \in \mathcal{W}$$. De verzameling $$\mathcal{P}$$ bevat alle mogelijke reeksen van breuken. Een breuk wordt voorgesteld als twee natuurlijke getallen die van elkaar worden gescheiden door een slash (/). De getallen voor en na de slash worden respectievelijk de teller en de noemer van de breuk genoemd. In een reeks breuken worden de voorstellingen van de individuele breuken van elkaar gescheiden door één enkele spatie. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel bestaan uit kleine letters. Gevraagd wordt:

1. Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,p\ $$bestaat uit exact 7 breuken$$\,\}$$

     voorbeeld:	4135/326 1/44 1/764 14/1 91/116 1435/3576 38/3 $$\in \mathcal{P}_1$$
     	19/98 671/97 3668/1481 703/841 379/153 $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,$$de noemers van alle breuken in $$p$$ zijn even$$\,\}$$

     voorbeeld:	2781/52 89/8 601/856 43/4 2183/2712 $$\in \mathcal{P}_2$$
     	23/2 297/1822 5966/4005 67/6326 1179/151 $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,p\ $$bevat minstens één breuk waarvan teller en noemer uit exact twee cijfers bestaan$$\,\}$$

     voorbeeld:	3793/1586 27/70 107/88 167/795 61/2 $$\in \mathcal{P}_3$$
     	2687/2548 1657/53 5077/7 7/67 80/121 $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,$$in alle breuken van $$p$$ is het eerste cijfer van de teller gelijk aan het laatste cijfer van de noemer$$\,\}$$

     voorbeeld:	91/379 7/67 6353/596 495/4184 743/2947 $$\in \mathcal{P}_4$$
     	65/36 7/26 1/6 746/9 601/24 441/4924 $$\not \in \mathcal{P}_4$$

   Geef telkens een Unix commando waarin de reguliere expressie gebruikt wordt door een commando uit de grep familie om enkel de regels van het tekstbestand naar stdout te schrijven waarvan het patroon $$p$$ behoort tot $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$.

2. Bepaal als volgt de woorden $$w_1\ w_2\ w_3\ w_4$$ van een geheime boodschap:

   • het woord $$w_1$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P}_2$$

   • het woord $$w_2$$ staat op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P}_3$$

   • het woord $$w_3$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P}_4$$

   • het woord $$w_4$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_4 \cap \mathcal{P}_1$$

   Geef telkens een Unix commando waarin de reguliere expressies voor de verzamelingen $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$ gebruikt worden door commando's uit de grep familie om het woord $$w_j\ (j = 1, 2, 3, 4)$$ op te zoeken in het tekstbestand en uit te schrijven naar stdout. Hierbij is het niet toegelaten om het woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).