13
\$\begingroup\$

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
\$\endgroup\$

closed as unclear what you're asking by Peter Taylor, NoOneIsHere, Wheat Wizard, Blue, xnor Apr 15 '17 at 18:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    \$\begingroup\$ Welcome to PPCG! This is a nice first question, but I would recommend adding some test cases to make it more clear. \$\endgroup\$ – Laikoni Apr 15 '17 at 15:05
  • 4
    \$\begingroup\$ @Tweakimp Even so, a single worked example could help clarify the rather formal definition. \$\endgroup\$ – Martin Ender Apr 15 '17 at 15:37
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Apr 15 '17 at 16:04
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Peter Taylor Apr 15 '17 at 16:09
  • 6
    \$\begingroup\$ Did someone say Beta? \$\endgroup\$ – Beta Decay Apr 15 '17 at 17:27
3
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Great! Would you be so kind and comment the code? :) \$\endgroup\$ – Tweakimp Apr 15 '17 at 17:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.