OEIS A228297: Need Help to Find Algorithm

[Thomas Okken]

That paper is beyond me, and I'm not familiar with SysRPL, but here's a memoized implementation in C which is quite fast:

Code:

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

int *m = NULL;
int sz = 0;

int a(int n) {
    int r;
    if (n < 0)
        return 0;
    if (n < sz) {
        r = m[n];
        if (r != -1)
            return r;
    } else {
        int i;
        m = realloc(m, (n + 1) * sizeof(int));
        for (i = sz; i <= n; i++)
            m[i] = -1;
        sz = n + 1;
    }
    if (n <= 5)
        r = n;
    else
        r = a(n-a(n-1)) + a(n-1-a(n-2)) + a(n-2-a(n-3)) + a(n-3-a(n-4)) + a(n-4-a(n-5));
    m[n] = r;
    return r;
}

int main(int argc, char *argv[]) {
    int i, n;
    for (i = 1; i < argc; i++)
        if (sscanf(argv[i], "%d", &n) != 1)
            printf("can't parse \"%s\"\n", argv[i]);
        else
            printf("a(%d) = %d\n", n, a(n));
    return 0;
}

If you throw very large arguments at it, you may get a segmentation fault caused by the process running out of stack space. ulimit -s unlimited prevents that, although the program does need O(n) memory, for the stack and the memoization array, so you're going to hit some limit eventually.