c++

Golomb's sequence is known as "self describing" -- it almost seems to define itself. It is defined as the sequence of natural numbers such that n appears exactly G(n) times in the sequence. Here are the first few values of G(n) for some n:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
G(n)	1	2	2	3	3	4	4	4	5	5	5	6	6	6	6

The sequence starts at 1, with G(1) = 1.

It's not too hard if you step through it one term at a time.

For n = 1, G(n) is 1. If you look at the sequence (the entire sequence all the way to infinity -- it seems to "know" about itself), 1 appears only 1 time.

For n = 2, G(n) is 2. Looking again at the sequence, the number 2 appears 2 times.

For n = 3, G(n) is 3. You can see that 3 appears 3 times.

And so on and so forth.

Assignment

Write a C++ program that recursively computes each term of G(n) up to and including a given n. You can "hard code" the input value (the program does not need to accept any input) but you will need to set it sufficiently high so you can determine your answer for the second part below.

The formula is:

G(n) = 1 + G(n - G(G(n - 1)))

Remember to think about the base case.

Example Output

The output of your program does not need to exactly match this, but please make sure each term is output on a separate line along with the n for that term.

For n = 15: