foobar.c

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

static int pi_1(int idx) {
	int sq, sq2;

	sq = floor(sqrt(idx));
	sq2 = sq * sq;

	return (idx - sq2 < sq) ? (idx - sq2) : sq;
}

static int pi_2(int idx) {
	int sq, sq2;

	sq = floor(sqrt(idx));
	sq2 = sq * sq;

	return (idx - sq2 < sq) ? sq : (idx - sq2 - sq);
}

static void T(int idx);
static void S(int idx);

static void S(int idx) {
	switch (idx & 1) {
	case 0:
		/* S ::= T */
		T(idx / 2);
		break;
	case 1:
		/* S ::= TS */
		T(pi_1(idx / 2));
		S(pi_2(idx / 2));
		break;
	}
}

static void T(int idx) {
	if (!idx) {
		/* T ::= u */
		printf("u");
	} else {
		/* T ::= '(' S ')' */
		printf("(");
		S(idx - 1);
		printf(")");
	}
}

int main(int argc, char **argv) {
	int i, max;

	max = argc > 1 ? atoi(argv[1]) : 64;

	for (i = 0; i < max; ++i) {
		printf("%i %i\n", pi_1(i), pi_2(i));
	}

	for (i = 0; i < max; ++i) {
		printf("%i: ", i);
		T(i);
		printf("\n");
	}
	return 0;
}