There is no need for any dynamic allocation.
http://void.wikidot.com/code:hofseq-c
>>8
The nostalgia! I salute you!
I hope you won't mind if I copy and paste your submission here, turning off the space-saving FV indentation style for a less innovative one that, for unknown reasons, some of us still find more readable:
/* hofseq.c by FrozenVoid */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
uint64_t hofseq_ff(uint64_t N) {
uint64_t R = 1, S = 2, P = 1, t = 0;
for (uint64_t i = 1; i < N; i++) {
R += S++;
t = P > 1 ? hofseq_ff(P) : 3;
S += (S == t); P += (t < S);
}
return R;
}
int main(int argc, char**argv) {
uint64_t Num = argc != 2 ? 0 : strtoull(argv[1], NULL, 10);
for(uint64_t i = 0; i < Num; i++) printf("%lu,", hofseq_ff(i+1)); return 0;
}You're essentially trading off memory usage for time complexity (and time complexity did explode with the recursive calls to hofseq_ff, I non-figureofspeechously left the computer and fixed myself a coffee while running ./hofseq_ff 10000 which >>4 computes in a couple of milliseconds.
On a side note, avoiding the use of dynamic allocation while implementing the solution described in >>5 means finding the optimal size of the allocated arrays R and S, and it isn't immediately obvious to me.
>>7
Finally a Lisp solution. Unfortunately I can't try it right now on this computer. And who's running for the shortest now? Where are the Perl Monks?
I can't even figure out the general case for the first two iterations, someone please help?
R1 = 1, from there you derive S1 as the smallest integer not already used in R or S. So S1 = 2 and R2 = R1 + S1.