Kata

In his book, Gödel, Escher, Bach, Douglas Hofstadter describes a sequence of numbers which begins:

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98 ..  (sequence A)

It has the following property:

The sequence, together with its sequence of first differences (the differences between successive terms), lists all positive integers exactly once.

To illustrate this property, write down the first differences of the sequence A:

2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15 .. (sequence B)

and note that together, the sequences A and B list all positive integers.

To calculate more terms we can first extend the sequence B:

2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19 ..

(We omit 18 as it occurs already in the sequence A). Then we can extend the sequence A by using the rule that A(n) = A(n-1) + B(n-1):

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, (98+16) ..

Write a function which will return the nth term of the sequence A.

For example:

hof 0 = 1
hof 1 = 3
hof 2 = 7

etc.

In the tests, values of n up to

100 000

1 000 000

1 000 000

1 000

1_000_000

will be tested.