Lexicographically earliest sequence with shift-sum property

Question

I use $\mathbb{N}$ to denote the set of non-negative integers.

Let $a: \mathbb{N} \rightarrow \mathbb{N}$ satisfy $a(n+a(n+1)) = a(n) + a(n+1)$. Two trivial examples are $a(n) = 0$ and $a(n) = n$. But if we require $a(n+1) > 0$, we eliminate the former. Now let $a_0$ be the lexicographically earliest sequence of this kind, do we necessarily have

$$\forall n \in \mathbb{N}: a_0(n+1) = \min \{k \mid k \in \mathbb{Z}^+, a_0(n+k) = a_0(n) + k\}$$

and assuming this to be true, can we show $a_0(n) \le n$?

I wrote a program using these assumptions to produce the terms

$$0, 1, 2, 3, 2, 5, 2, 7, 3, 7, 10, 2, 12, 9, 3, 10, 12, 2, 14, 17,$$ $$3, 21, 20, 14, 13, 2, 15, 22, 2, 24, 3, 16, 27, 2, 29, 31$$

which may or may not be the initial terms of $a_0$. All I know for sure is that, for any sequence $a$ with the shift-sum property, there can be no zeros or ones after $n=1$ and no zeros or ones at all if $a(0) \neq 0$, so any help answering these questions will be greatly appreciated.

I have plotted the terms above in GeoGebra here. I don't have any more terms because the program I used to compute them seems to enter an infinite loop after $n = 35$. The program in question can be found here.

---

Edit 1: I am calling the proposition $$\forall n \in \mathbb{N} : a(n+a(n+1)) = a(n) + a(n+1) \text{ and } a(n+1) > 0$$ the shift-sum property. A sequence is said to exhibit the least shift-sum property if $a(n+1)$ is always the least positive integer $k$ such that $a(n+k) = a(n) + k$.

I now realise I have made some undue assumptions about the existence of a lexicographic minimum for some class of sequences, and the existence of sequences with the least shift-sum property described above. I also assumed that $a_0(0) = 0$, however this may not be true even if $a_0$ does in fact exist. Motivated by the discussion in the comments below, I ask the following question to help dispel the confusion.

Do there exist sequences of natural numbers with the least shift-sum property?

---

Edit 2: I have just realised that the output of my program proves that at least one of my initial assumptions is incorrect. In the output we get $a(2) = 2$, but $k = 1$ is actually the least such that $a(n+k) = a(n)+k$, hence the output must rely on a false assumption. Moreover, my program enters an infinite loop because $a(23) = 14$ requires $a(35) = 34$ but $a(24) = 13$ requires $a(35) = 27$.

If a sequence has the least shift-sum property, then two adjacent terms $a(n)$ and $a(n+1)$ can only be consecutive integers if $a(n) = 0$ and $a(n+1) = 1$. This follows from $a(n+1)$ being $a(n) + 1$. Therefore, if both assumptions are true then $a_0$ cannot start $0,1,2$. But there are no other possibilities if $a_0(n) \le n$.

I conjecture that, if $a_0$ does indeed exist, then $a_0(n) \le n$ and that there are no sequences of natural numbers with the least shift-sum property.

Answer 1

(Not a solution. Too long to be a comment.)

This is how I'm thinking of showing that the infimum is a SSP.

• Consider all sequences with SSP.
• Consider the first element, pick the smallest (which turns out to be 0).
  • Focus on sequences with this first element, pick the smallest second element.
• Focus on sequences with these first 2 elements,
  • we do have $a( 0 + a(1) ) = a(0) + a(1)$ by definition, which will uniquely define a subsequent term.
  • Pick the smallest third element.
• Focus on sequences with these first 3 elements,
  • we do have $ a(1 + a(2) ) = a(1) + a(2) $ by definition, which will uniquely define a subsequent term.
  • Pick the smallest fourth element.
• We continue this process iteratively
  • We can always continue this, since there exists at least 1 SSP with those initial $k$ elements, so we can pick the smallest $k+1$ element.
  • At each step, we have $ a( k + a(k+1) ) = a(k) + a(k+1)$.