Gödel's β function takes three natural numbers as arguments.
It is defined as
β(x,y,z) = rem(x, 1 + (z + 1) · y) = rem(x, (z · y + y + 1) )
where rem(a, b) denotes the remainder after integer division of a by b.
The β Lemma now states that:
For any sequence of natural numbers (k_0, k_1, … , k_n), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = k_i.
Gödel needs help to find
c for any given input
(k_0, k_1, … , k_n), k_i ∈ ℕ.
Write a function that takes in an array of length
n, filled with natural numbers, and gives a possible
b,c output that fulfilles the Lemma for the array.
Do not get solutions by brute force!
(In my totally unprofessionall opinion, it is brute force when you first get a number and then do the calculation. That is guessing the number and then looking if the guess was correct. What I want to be coded here is a solution which calculates the numbers and does not have to check whether they fulfill the lemma because they were calculated to do so. )
Construct them with the equations and information given.
Shortest code wins, bonus points if you do it in
[5, 19, 7, 8] -> (1344595, 19) 1344505 % (1 + (0 + 1) * 19) = 5 1344505 % (1 + (1 + 1) * 19) = 19 1344505 % (1 + (2 + 1) * 19) = 7 1344505 % (1 + (3 + 1) * 19) = 8