The Hendrie Sequence ``H" is a self-describing sequence defined as follows:
- H(1) = 0
- If we expand every number x in H to a subsequence containing x 0's followed by the
number x + 1, the resulting sequence is still H (without its first element).
Thus, the first few elements of H are:
0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...
You must write a program that, given n, calculates the nth element of H.
Each test case consists of a single line containing the integer n (
0 < n < 263) .
Input is terminated with a line containing the number `0' which of course should not be processed.
For each test case, output the nth element of H on a single line.
4
7
44
806856837013209088
0
2
0
3
16
Problem setter: Derek Kisman, University of Waterloo, Canada