# Help Gödel with his β function [closed]

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 b and 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 Javascript because I am just getting into it :)

Example:

[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

• Welcome to PPCG! This is a nice first question, but I would recommend adding some test cases to make it more clear. – Laikoni Apr 15 '17 at 15:05
• @Tweakimp Even so, a single worked example could help clarify the rather formal definition. – Martin Ender Apr 15 '17 at 15:37
• Related – Peter Taylor Apr 15 '17 at 16:04
• It's not clear what qualifies as "brute force". Obviously an approach which iterates through all pairs (b, c) until it finds one which works would be brute force, and an approach which runs in time linear in the length of the input would not be, but there's a large gap between those. Where is the line drawn? – Peter Taylor Apr 15 '17 at 16:09
• Did someone say Beta? – Beta Decay Apr 15 '17 at 17:27

## JavaScript (ES6), 104 bytes

a=>[c=a.reduce(c=>c*++i,Math.max(...a),i=0),a.reduce(g=(x,k)=>x%m-k?g(x+n,k):(n*=m,m+=c,x),0,n=1,m=c+1)]


Returns [c, b] as an array. The solution it returns isn't minimal in c but I think it is minimal in b for the given c. For 120 bytes this returns solutions minimal in c and in b for the given c:

f=(a,c=1,b=a.reduce(g=(x,k)=>x%m-k?d--?g(x+n,k):0/0:n%m?g(x,k,n+=o):(o=n,d=m+=c,x),0,o=n=1,d=m=c+1))=>1/b?[b,c]:f(a,c+1)


Ungolfed minimal solution solver:

function godel(a) {
for (c = 0;; c++) {
var b = 0, n = 1, i = 0;
for (;;) {
var m = c * i + c + 1;
// Increase b until β(b,c,i) = a[i]
// Adding n won't change output for smaller i
for (j = 0; j < m; j++) if (b % m != a[i]) b += n;
if (j == m) break; // couldn't find a remainder, c too low
i++;
if (i == a.length) return [b, c]; // Result!
// Next time we want adding n to b not to change β(b,c,i)
for (j = 1; n * j % m != 0; j++);
n *= j;
}
}
}

• Great! Would you be so kind and comment the code? :) – Tweakimp Apr 15 '17 at 17:37