Wanneer Stefan door de collectie van zijn plaatselijke tweedehandsboekenwinkel aan het grasduinen is, stuit hij op een stoffig, in leer gebonden boek. Nieuwsgierig slaat hij het open en merkt dat de vorige eigenaar het boek aanzienlijk beschadigd heeft. De tekst is onleesbaar geworden omdat die hier en daar bedekt is door zwarte inktvlekken. Terwijl Stefan door de pagina's aan het bladeren is, valt zijn oog op deze twee regels, waarvan de tweede deels verborgen zit onder twee grote vlekken:

Altijd in voor een uitdaging vraagt Stefan zich af of het mogelijk zou zijn om de ontbrekende getallen te achterhalen — ervan uitgaande dat beide getallenreeksen hetzelfde patroon volgen. Kun jij hem helpen?

Opgave

Op elke regel in het raadsel wordt een reeks van $$m$$ ($$m > 2$$) natuurlijke getallen $$(s_0, s_1, \ldots, s_{m-1})$$ aan de linkerkant getransformeerd naar een nieuwe reeks van $$m$$ natuurlijke getallen $$(t_0, t_1, \ldots, t_{m-1})$$ aan de rechterkant. Dit gebeurt door voor elk getal $$s_i$$ ($$i = 0, 1, \ldots, m-1$$) aan de linkerkant alle andere getallen aan de linkerkant met elkaar te vermenigvuldigen, daar 1 bij op te tellen, en het resultaat te delen door $$s_i$$. Dit geeft het corresponderende getransformeerde getal $$t_i$$ aan de rechterkant \[ t_i = \frac{\prod_{k \neq i}s_k + 1}{s_i},\ \ \ i = 0, 1, \ldots, m-1 \] waarbij $$\prod_{k \neq i}s_k$$ staat voor het product van alle getallen $$s_0, s_1, \ldots, s_{m-1}$$ behalve $$s_i$$. Laat ons dit eens toepassen voor de bovenste regel van het raadsel, waarop alle getallen zichtbaar zijn. Voor het eerste getal ($$s_0 = 2$$) vinden we dat \[ t_0 = \frac{s_1 \times s_2 \times s_3 \times s_4 + 1}{s_0} = \frac{3 \times 11 \times 23 \times 31 + 1}{2} = 11765 \] voor het tweede getal ($$s_1 = 3$$) vinden we dat \[ t_1 = \frac{s_0 \times s_2 \times s_3 \times s_4 + 1}{s_1} = \frac{2 \times 11 \times 23 \times 31 + 1}{3} = 5229 \] enzoverder voor de andere getallen op de bovenste regel.

Wanneer er aan de linkerkant van een regel juist één getal $$s_i$$ op positie $$i$$ ontbreekt, dan kunnen we $$s_i$$ achterhalen van zodra we minstens één getransformeerd getal $$t_j$$ kennen dat aan de rechterkant staat. Hierbij moeten we twee gevallen van elkaar onderscheiden:

• Als de posities $$i$$ en $$j$$ gelijk zijn, dan volgt uit bovenstaande transformatieformule rechtstreeks dat \[ s_i = \frac{\prod_{ k \neq i}s_k + 1}{t_i} \] Op de onderste regel in het raadsel ontbreekt het getal $$s_4$$ op positie $$i = 4$$, maar kennen we het getransformeerde getal $$t_4 = 5$$ op positie $$j = 4$$. We kunnen het ontbrekende getal dus bereken als \[ s_4 = \frac{s_0 \times s_1 \times s_2 \times s_3 + 1}{t_4} = \frac{2 \times 3 \times 7 \times 47 + 1}{5} = 395 \]

• Als de posities $$i$$ en $$j$$ verschillend zijn, dan kunnen we de bovenstaande transformatieformule herschrijven tot \[ s_i = \frac{s_j \times t_j - 1}{\prod_{k \neq i,\,k \neq j}s_k} \] waarbij $$\prod_{k \neq i,\,k \neq j}s_k$$ staat voor het product van alle getallen $$s_0, s_1, \ldots, s_{m-1}$$ behalve $$s_i$$ en $$s_j$$. Omdat we op de onderste regel in het raadsel het getransformeerde getal $$t_0 = 194933$$ op positie $$j = 0$$ kennen, kunnen we het ontbrekende getal op positie $$i = 4$$ dus ook berekenen als \[ s_4 = \frac{s_0 \times t_0 - 1}{s_1 \times s_2 \times s_3} = \frac{2 \times 194933 - 1}{3 \times 7 \times 47} = 395 \] Omdat we op de onderste regel in het raadsel ook het getransformeerde getal $$t_3 = 353$$ op positie $$j = 3$$ kennen, kunnen we het ontbrekende getal op positie $$i = 4$$ dus ook berekenen als \[ s_4 = \frac{s_3 \times t_3 - 1}{s_0 \times s_1 \times s_2} = \frac{47 \times 353 - 1}{2 \times 3 \times 7} = 395 \]

Wat de twee getallenreeksen $$(2, 3, 11, 23, 31)$$ en $$(2, 3, 7, 47, 395)$$ aan de linkerkant van het raadsel zo bijzonder maakt, is dat de vijf getransformeerde getallen aan de rechterkant ook natuurlijke getallen zijn. Los van de volgorde waarin de getallen opgelijst worden, zijn dit ook de enige twee reeksen van 5 getallen die hieraan voldoen (tenzij we toelaten dat er getallen aan de linker- of rechterkant 1 mogen zijn). Er bestaan ook langere getallenreeksen die hieraan voldoen, bijvoorbeeld de reeks $$(2, 3, 7, 47, 583, 1223)$$ met 6 getallen. De naam Stefan uit het raadsel is trouwens een verwijzing naar Štefan Znám¹ die getallenreeksen met deze eigenschap bestudeerde.

We stellen een reeks natuurlijke getallen voor als een reeks (list of tuple) van getallen (int). Daarbij worden de posities van de getallen in de reeks van links naar rechts genummerd vanaf nul. Een ontbrekend getal op een bepaalde positie in de reeks stellen we voor door de waarde None. Gevraagd wordt:

• Schrijf een functie product waaraan een reeks $$s$$ (list of tuple) met natuurlijke getallen (int) moet doorgegeven worden. De functie moet het product (int) van alle getallen in reeks $$s$$ teruggeven. Aan de functie kunnen optioneel nog één of meer posities (int) doorgegeven worden van getallen uit reeks $$s$$ die niet het in het product mogen opgenomen worden. Hierbij mag de functie ervan uitgaan dat de posities in reeks $$p$$ geldig zijn, zonder dat dit expliciet moet gecontroleerd worden.

• Schrijf een functie transformeren waaraan twee argumenten moeten doorgegeven worden: i) een reeks $$s$$ (list of tuple) met $$m$$ ($$m > 2$$) natuurlijke getallen $$s_0, s_1, \ldots, s_{m-1}$$ (int) en ii) een positie $$i$$ (int, $$0 \leq i < m$$). Als het getransformeerde getal $$t_i$$ geen natuurlijk getal (int) is, dan moet de functie een AssertionError opwerpen met de boodschap ongeldige transformatie. Anders moet de functie het getransformeerde getal $$t_i$$ (int) teruggeven.

• Schrijf een functie transformatie waaraan $$m$$ ($$m > 2$$) natuurlijke getallen $$s_0, s_1, \ldots, s_{m-1}$$ (int) moeten doorgegeven worden. De functie moet een lijst (list) met de $$m$$ getransformeerde getallen $$t_0, t_1, \ldots, t_{m-1}$$ (int) teruggeven. Als daar getransformeerde getallen tussen zitten die geen natuurlijke getal (int) zijn, dan moet de functie in plaats daarvan een AssertionError opwerpen met de boodschap ongeldige transformatie.

• Schrijf een functie ink_cognito waaraan twee reeksen $$s = (s_0, s_1, \ldots, s_{m-1})$$ en $$t = (t_0, t_1, \ldots, t_{m-1})$$ (list of tuple) met $$m$$ ($$m > 2$$) natuurlijke getallen (int) moeten doorgegeven worden. In reeks $$s$$ ontbreekt juist één getal en in reeks $$t$$ is er minstens één getal dat niet ontbreekt, waarbij ontbrekende getallen voorgesteld worden door de waarde None. De functie moet een tuple met twee elementen teruggeven:

  1. een nieuwe lijst (list) met de getallen $$s_0, s_1, \ldots, s_{m-1}$$ (int) waarin het ontbrekende getal aangevuld werd

  2. een nieuwe lijst (list) met de getallen $$t_0, t_1, \ldots, t_{m-1}$$ (int) waarin alle ontbrekende getallen aangevuld werden

  zodat de getallenreeks $$(s_0, s_1, \ldots, s_{m-1})$$ getransformeerd wordt naar de getallenreeks $$(t_0, t_1, \ldots, t_{m-1})$$. De functie mag ervan uitgaan dat een dergelijke transformatie mogelijk is, zonder dat dit expliciet moet gecontroleerd worden.

Voorbeeld

>>> product([2, 3, 11, 23, 31])
47058
>>> product((2, 3, 7, 47, 395), 0)
389865
>>> product([2, 3, 7, 47, 583, 1223], 1, 3)
9982126
>>> product((2, 3, 7, 43, 3263, 4051, 2558951), 0, 2, 4)
1337254054629

>>> transformeren([2, 3, 11, 23, 31], 0)
11765
>>> transformeren((2, 3, 11, 23, 31), 1)
5229
>>> transformeren([2, 3, 11, 23, 31], 2)
389
>>> transformeren((2, 3, 11, 23, 31), 3)
89
>>> transformeren([2, 3, 11, 23, 31], 4)
49
>>> transformeren((2, 3, 4, 5, 6), 3)
29
>>> transformeren((2, 3, 4, 5, 6), 4)
Traceback (most recent call last):
AssertionError: ongeldige transformatie

>>> transformatie(2, 3, 11, 23, 31)
[11765, 5229, 389, 89, 49]
>>> transformatie(2, 3, 7, 47, 395)
[194933, 86637, 15913, 353, 5]
>>> transformatie(2, 3, 7, 47, 583, 1223)
[351869942, 156386641, 28724077, 637157, 4141, 941]
>>> transformatie(2, 3, 7, 43, 3263, 4051, 2558951)
[15272109930890495, 6787604413729109, 1246702851501265, 33038636951629, 5737528889, 3722498629, 9329]
>>> transformatie(2, 3, 11, 25, 29, 1097, 2753)
[36127240463, 16056551317, 1194288941, 231214339, 171829919, 120083, 19067]
>>> transformatie(2, 3, 4, 5, 6)
Traceback (most recent call last):
AssertionError: ongeldige transformatie

>>> ink_cognito([2, 3, 7, 47, None], [194933, None, None, 353, 5])
([2, 3, 7, 47, 395], [194933, 86637, 15913, 353, 5])
>>> ink_cognito((2, 3, 11, None, 31), (None, 5229, 389, None, 49))
([2, 3, 11, 23, 31], [11765, 5229, 389, 89, 49])
>>> ink_cognito([2, 3, 7, 47, 583, None], [None, None, None, None, None, 941])
([2, 3, 7, 47, 583, 1223], [351869942, 156386641, 28724077, 637157, 4141, 941])