a[n] is a[n] terms from term = a[n]+1

[Dean Hickerson]

Leroy Quet (qqquet at mindspring.com) asked:

> You have a sequence where:
> a[1] = 1;
> and either a[n -a[n]] = a[n]+1
> or
> a[n +a[n]] = a[n]+1
>
> such that a[n -a[n]] is chosen whenever it is not equal
> to any positive integer <= a[n] already.
>
> The sequnce begins, with 0 representing "empty" a[n]'s:
>
> 1, 2, 5, 3, 0, 0, 4, 6, 17, 15, 13, 11, 9, 7, 0,
> 0, 0, 0, 0, 0, 8, 10, 12, 14, 16, 18,...
>
> (If I didn't err...)
>
> Does this sequence continue forever (so that no a[n] = more than one
> different value at once, of course)?

No, it doesn't.

I find it easier to work with the inverse function b[n], defined by b[n]=m
iff a[m]=n.  This satisfies the recurrence

              /  b[n]-n  if this is positive and does not occur among the
              |          values b[1], ..., b[n];
    b[n+1] = <
              |
              \  b[n]+n  otherwise.

We have:

       n  1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
    b[n]  1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25  9 26 44 63 43 64 42 19

But now b[24]-24 = -5 and b[24]+24 = 43, neither of which is available as
a value for b[25].

> And if you are free to choose
>
> a[n -a[n]] = a[n]+1
> or
> a[n +a[n]] = a[n]+1,
>
> then is it possible to get a sequence without any zeros at all?

I don't know.  It's a cute question:  Can you take a walk on the positive
integers, starting at 1 and always moving (either left or right) a distance
n on your n-th step, so that you hit every positive integer exactly once?

Dean Hickerson
dean at math.ucdavis.edu