While browsing the collection of his local second-hand bookstore, Stefan stumbles upon a dusty leather-bound volume. Curious, he opens the book and notices that it has suffered significant damage at the hands of a previous owner, with some of the text being obscured by black ink blotches. As Stefan leafs through the pages, the following two lines catch his eye — the second of which has fallen victim to two particularly unfortunate blotches:

What numbers are obscured by these two black ink blotches?

Always fond of a challenge, Stefan wonders whether it might be possible to figure out the values of the obscured numbers — assuming, of course, that both lines of numbers follow a consistent pattern. Can you help him out?

Show answer

The left ink blotch obscures the number 395. The right ink blotch obscures the numbers 86637 and 15913.

Assignment

Each line of the riddle transforms a sequence of $$m$$ ($$m > 2$$) natural numbers $$(s_0, s_1, \ldots, s_{m-1})$$ on the left-hand side into a new sequence of $$m$$ natural numbers $$(t_0, t_1, \ldots, t_{m-1})$$ on the right-hand side. For each number $$s_i$$ ($$i = 0, 1, \ldots, m-1$$) on the left-hand side, this is done by multiplying all other numbers on the left-hand side, adding 1, and then dividing the result by $$s_i$$. This yields the corresponding transformed number $$t_i$$ appearing on the right-hand side \[ t_i = \frac{\prod_{k \neq i}s_k + 1}{s_i},\ \ \ i = 0, 1, \ldots, m-1 \] where $$\prod_{k \neq i}s_k$$ represents the product of all numbers $$s_0, s_1, \ldots, s_{m-1}$$ except $$s_i$$. As an illustration , first consider the top line, where all the numbers are visible. For the first number ($$s_0 = 2$$) we find that \[ 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 \] and similarly for the second number ($$s_1 = 3$$) we find that \[ 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 \] and so on for all remaining numbers on the first line.

If exactly one number $$s_i$$ is obscured at position $$i$$ on the left-hand side of a line, we can infer $$s_i$$ from a single transformed number $$t_j$$ on the right-hand side. To do so, we must distinguish two cases:

If positions $$i$$ and $$j$$ are equal, then it follows directly from the above transformation formula that \[ s_i = \frac{\prod_{ k \neq i}s_k + 1}{t_i} \] On the second line of the riddle, number $$s_4$$ at position $$i = 4$$ is obscured, but we know the transformed number $$t_4 = 5$$ at position $$j = 4$$. So we can infer the obscured number as \[ 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 \]
If positions $$i$$ and $$j$$ are different, then we can rewrite the above transformation formula as \[ s_i = \frac{s_j \times t_j - 1}{\prod_{k \neq i,\,k \neq j}s_k} \] where $$\prod_{k \neq i,\,k \neq j}s_k$$ represents the product of all numbers $$s_0, s_1, \ldots, s_{m-1}$$ except $$s_i$$ and $$s_j$$. Since on the second line of the riddle we know the transformed number $$t_0 = 194933$$ at position $$j = 0$$, we can also infer the missing number at position $$i = 4$$ as \[ 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 \] Since on the second line of the riddle we also know the transformed number $$t_3 = 353$$ at position $$j = 3$$, we can also infer the missing number at position $$i = 4$$ as \[ 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 \]

What makes the two number sequences $$(2, 3, 11, 23, 31)$$ and $$(2, 3, 7, 47, 395)$$ on the left-hand side of the riddle so unusual, is that the five right-hand side numbers generated by the above transformation process are also natural numbers. In fact — apart from the order in which the numbers are listed — these are the only two five-number sequences with this property (unless some of the numbers on the left or right are allowed to be equal to 1). Longer sequences that follow the same pattern are also possible — for instance, $$(2, 3, 7, 47, 583, 1223)$$ is such a six-number sequence. By the way, the name Stefan in the riddle was a nod to Štefan Znám¹, who studied number sequences with this property.

We represent a sequence of natural numbers as a sequence (list or tuple) of integers (int). The positions of the numbers in the sequence are numbered from left to right, starting from zero. An obscured number at a given position in the sequence is represented by the value None. Your task:

Write a function product that takes a sequence $$s$$ (list or tuple) of natural numbers (int). The function must return the product (int) of all the numbers in sequence $$s$$. Optionally, the function may take another sequence $$p$$ (list or tuple) with positions (int) of numbers from sequence $$s$$ that should be excluded from the product. The function may assume that the positions in sequence $$p$$ are valid, without having to check this explicitly.
Write a function transform that takes two arguments: i) a sequence $$s$$ (list or tuple) of $$m$$ ($$m > 2$$) natural numbers $$s_0, s_1, \ldots, s_{m-1}$$ (int) and ii) a position $$i$$ (int, $$0 \leq i < m$$). If the transformed number $$t_i$$ is not a natural number (int), the function must raise an AssertionError with the message invalid transformation. Otherwise, the function must return the transformed number $$t_i$$ (int).
Write a function transformation that takes $$m$$ ($$m > 2$$) natural numbers $$s_0, s_1, \ldots, s_{m-1}$$ (int). The function must return a list $$t$$ containing the $$m$$ transformed numbers $$t_0, t_1, \ldots, t_{m-1}$$ (int). If some of these transformed numbers are not natural numbers (int), the function must raise an AssertionError with the message invalid transformation instead.
Write a function ink_cognito that takes two sequences $$s = (s_0, s_1, \ldots, s_{m-1})$$ and $$t = (t_0, t_1, \ldots, t_{m-1})$$ (list or tuple) of $$m$$ ($$m > 2$$) natural numbers (int). Exactly one number is obscured in sequence $$s$$ and at least one number is not obscured in sequence $$t$$, where obscured numbers are represented by the value None. The function must return a tuple with two elements:
1. a new list with the numbers $$s_0, s_1, \ldots, s_{m-1}$$ (int) where the obscured number was completed
2. a new list with the numbers $$t_0, t_1, \ldots, t_{m-1}$$ (int) where the obscured numbers were completed
such that the number sequence $$(s_0, s_1, \ldots, s_{m-1})$$ is transformed into the number sequence $$(t_0, t_1, \ldots, t_{m-1})$$. The function may assume that such a transformation is possible, without having to check this explicitly.

Example

        >>> 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

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

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

>>> 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])