In October 2017 I received a program, {goldstoner.c}, in the format of
the BIGNUM BAKEOFF contest from Arnaldur Bjarnason, .
The main function, A(n, s, d), is first called with s != 0 and d = 0 and
then calls itself recursively with s >= d = 1; calls to A(n, s, d) with
s > d > 0 result in recursive calls with s the same and d increased
by 1, eventually bottoming out when s = d, in which case
A(n, s, d) = n. Following this recursive pattern and with a series of
inductions over the loops in A(n, s, d), it is possible to show that
1 + F[1 + 2(s - d)](n - 1) <= A(n, s, d) <= F[1 + 2(s - d)](2n + 1),
n >= 2, s > d > 0.
Plugging these bounds into the initial call to A(n, s, 0) and making
another series of inductions gives
F[1, 2](n - 1) + 1 <= A(n, s, 0) <= F[1, 2](2n + 1),
n >= 3, s != 0.
The output of {goldstoner.c} is therefore between F[1, 2](98) + 1 and
F[1, 2](199), i.e., between {ioannis.c} and {chan-2.c} in the
BIGNUM BAKEOFF results.
# goldstoner.c #
#include
typedef int I;
I A(I n, I s, I d) {
if (d == s) {
return n;
}
I* a = malloc(n);
I i;
for (i = 0; i < n; ++i) {
a[i] = n;
}
I o = n;
I l = 1;
while (l) {
l = 0;
I i;
for (i = 0; i < n; ++i) {
a[i] += l ? A(a[i] << a[i - 1], !d ? a[i] << a[i - 1] : s, d + 1) : -1;
a[i] = a[i] < 1 ? 0 : a[i];
o <<= a[i];
l = a[i];
}
}
return o;
}
I main() { return A(99, 99, 0); }