Marxen.c

Marxen.c — заявка Хайнера Марксена на конкурс бигнум бейкофф, целью которого является написание программы на языке программирования C (объёмом не более 512 символов), генерирующей наибольший возможный результат. Он занял второе место в конкурсе, уступив только числу Лоудера.

Программа использует вариант последовательности Гудштейна. Её выходные данные имеют нижнюю границу $f_{\omega^{\omega}}(2\uparrow\uparrow 500)$ и верхнюю границу $f_{\varepsilon_{0} + \omega^{3}}(1000000)$ в быстрорастущей иерархии.

Код

typedef int	J;
J P(J x,J y)	{ return x+y ? x%2 + y%2*2 + P(x/2,y/2)*4 : 0 ;}
J H(J z)	{ return z ? z%2 + 2*H(z/4) : 0 ;}
J I(J f,J e,J r){ return f ? P(P(f,e),r) : r ;}
J M(J x,J e)	{ return x ? I(x%2, M(e,0), M(x/2, e+1)) : 0 ;}
J D(J,J);	 
J E(J f,J e,J r,J b)
{
    return e ? E(1, D(e,b), I(b-1, D(e,b), I(f-1,e,r)), b) : I(f-1,e,r) ;
}
J D(J x,J b)	{ return x ? E( H(H(x)), H(H(x)/2), H(x/2), b) : 0 ;}
J F(J x,J b)	{ return x ? F(D(x,b+1),b+1) : b ;}
J G(J x)	{ return F(M(x,9), 9) ;}
J f(J n,J x)	{ return n ? f(n-1, G(x ? f(n,x-1) : n)) : G(x) ;}
J g(J x)	{ return f(x,x) ;}
J h(J n,J x)	{ return n ? h(n-1, g(x ? h(n,x-1) : n)) : g(x) ;}
J main(void)	{ return h(g(9),9) ;}

Функции, определённые в Marxen.c

В дальнейшем символ оператора / обозначает целочисленное деление, а%b эквивалентно a (mod b).

P(x,y)

1. Если x+y = 0, то P(x,y)=0.
2. Иначе, P(x,y)=x%2 + y%2*2 + 4P(x/2,y/2).

H(z)

1. Если z = 0, то H(z)=0.
2. Иначе, H(z)=z%2 + 2H(z/4)

I(f,e,r)

1. Если f = 0, то I(f,e,r)=r.
2. Иначе, I(f,e,r)=P(P(f,e),r)

M(x,e)

1. Если x = 0, то M(x,e)=0.
2. Иначе, M(x,e)=I(x%2, M(e,0), M(x/2,e+1))

D(x,b)

1. Если x = 0, то D(x,b)=0.
2. Иначе, D(x,b)=E(H(H(x)), H(H(x)/2), H(x/2), b)

E(f,e,r,b)

1. Если e = 0, то E(f,e,r,b)=I(f-1,e,r)
2. Иначе, E(f,e,r,b)=E(1, D(e,b), I(b-1, D(e,b), I(f-1,e,r)), b)

F(x,b)

1. Если x = 0, то F(x,b)=b.
2. Иначе, F(x,b)=F(D(x,b+1),b+1)

G(x)

G(x)=F(M(x,9),9)

f(n,x)

1. Если f = 0, то f(n,x)=G(x).
2. Иначе, если x = 0, то f(n,x)=f(n-1,G(n))
3. Иначе, f(n,x)=f(n-1,G(f(n,x-1)))

g(x)

g(x)=f(x,x)

h(n,x)

1. Если n = 0, то h(n,x)=g(x).
2. Иначе, если x = 0, то h(n,x)=h(n-1,g(n))
3. Иначе, h(n,x)=h(n-1,g(h(n,x-1)))

main()

main()=h(g(9),9)

Это число, полученное программой, и, следовательно, число, отправленное в бигнум бейкофф.