69 55 54 bytes
1 0v ^(# 0 (1+0)#)!
If a standard compliant interpreter is used, this takes input and output as byte values. To actually use decimal numbers on STDIN/STDOUT, you'd need the Python interpreter with
NUMERIC_OUTPUT = True and an additional option
NUMERIC_INPUT = True.
The skeleton of the program is
?1-( 1 -
We read the input
N onto the first voice and decrement it to get
N-1. We also initialise the second voice to
1. Then we loop
N-1 one times, each iteration of which gets the next value of the sequence on the second stack. At the end we print the
The idea of the program is to put each element of the sequence in a queue on the third voice, and to decrement the head of that queue in each iteration. When the head reaches
0, we increment the value of the sequence and remove that
Now the issue is that Prelude uses stacks and not queues. So we need to shift around that stack a bit to use it like a queue.
This copies the current value of the sequence to the first voice (as a temporary copy), pushes a
0 onto the second voice (to mark the end of the queue). And then performs a loop to shift (and thereby reverse) the third stack onto the second. After the loop, we put the copy of the current sequence value on top of the second stack (which is the tail of our queue).
This looks a bit ugly, but essentially it's a loop that shifts the stack back onto the third voice. Since the
) is in the same column as the shifting instructions, the
0 we put on the second voice earlier will also end up on the third voice, so we need to remove it with another
#. Then decrement the top of the 3rd voice, i.e. the head of the queue.
Now it gets a bit annoying - we want run some code when that value is
0, but Prelude's only control structure (the loop) only responds to non-zero values.
Note that the top of the second voice is truthy (since the Golomb sequence does not contain any
0s). So the workload goes into that voice (the latter pair of parentheses). We just need to prevent that from happening if the head of the queue isn't
0 yet. So first we have a "loop" on the third voice which pushes a
0 onto the second voice if the head of the queue is still non-zero. We also put a
0 on the third voice to exit the loop right away. The
# on the third voice then either removes that
0, or removes the head of the queue if that was already zero. Now that second loop is only entered if the head of the queue was zero (and the
0 on the second voice was never pushed). In that case we increment the current value of the sequence and push a
0 to exit the loop. Lastly, there will always be a
0 on top of the stack, which we need to discard.
I told you that logical negation is annoying in Prelude...