Kolakoski Sequence

Description
A Kolakoski sequence (A000002) is an infinite sequence of symbols {1, 2} that is its own run-length encoding. It alternates between "runs" of symbols. The sequence begins:

12211212212211211221211212211...
The first three symbols of the sequence are 122, which are the output of the first two iterations. After this, on the i-th iteration read the value x[i] of the output (one-indexed). If i is odd, output x[i] copies of the number 1. If i is even, output x[i] copies of the number 2.

There is an unproven conjecture that the density of 1s in the sequence is 1/2 (50%). In today's challenge we'll be searching for numerical evidence of this by tallying the ratio of 1s and 2s for some initial N symbols of the sequence.

Input Description
As input you will receive the number of outputs to generate and tally.

Output Description
As output, print the ratio of 1s to 2s in the first n symbols.

Sample Input
10
100
1000
Sample Output
5:5
49:51
502:498
Challenge Input
1000000
100000000
Bonus Input
1000000000000
100000000000000

Solution
in C

#include <stdio.h>

enum kval {K22 = 0, K11, K2, K1};

static void
next(enum kval *v)
{
    switch (*v) {
        case K22:
        case K11:
            *v += 2;
            break;
        case K2:
        case K1:
            next(v + 1);
            *v = !(*v % 2) + 2 * (v[1] % 2);
            break;
    }
}

int
main(void)
{
    unsigned long long n;
    enum kval stack[256] = {0};
    unsigned long long counts[2] = {1, 1};

    scanf("%llu", &n);
    for (unsigned long long i = 2; i < n; i++) {
        next(stack);
        counts[*stack % 2]++;
    }
    printf("%llu:%llu\n", counts[1], counts[0]);
}