Euler function and sums

Solution 1:

Let's first name the vectors $v_1, v_2$ and so on.

First of all we can note that consecutive numbers in the vector are coprime by induction. The base case is trivial. Now assume it holds for $v_{n-1}$ and consider $v_n$. Let $a,b$ are consecutive number in $v_n$. Then because of the way numbers are added to the vectors we have $a,|b-a|$ or $b, |a-b|$ appearing as consecutive numbers in $v_{n-1}$. WLOG let it be the first option. But then $\gcd(a,b) = \gcd(a,|b-a|) =1$. Hence the proof.

Now let's notice that a number $n$ can appear in the vector if $a,b$ appear as consecutive integer in a vector and $a+b = n$. But from above we have that neither of $a,b$ can share a common factor of $n$. Now using induction on $n$ we'll prove that such a combination of consecutive integers $(a,b)$ can appear only in a unique vector. The base case for $n=1,2,3$ is true. Now assume that we have consecutive integers $a,b$ appearing in different vectors, namely $v_i$ and $v_j$ such that both sum to $n$. WLOG let $a<b$. Then going back in $v_{i-1}$ and $v_{j-1}$ we have the consecutive integers $a, b-a$ in both vectors. But this contradicts the inductive hypothesis as both pairs sum to $b<n$.

From here we can conclude that an integer $n$ will be at most $\phi(n)$ in the final vector. Now it remains to show that each combination of $a,b$ s.t. $\gcd(a,b) = 1$ appears as consecutive integers at some point.

[UPDATE]

Similar as above we'll prove the last claim by induction on $n$. The base cases $n=1,2,3$ are trivially true. Now assume the claim holds for all numbers less than $n$. Now let $a,b$ be any integers such that $a+b=n$ and $\gcd(a,b)=1$ and WLOG $a<b$. We know that they will appear in $v_i$ if and only if $a,b-a$ appear as consecutive integers in $v_i$. But by the inductive hypothesis we have that $a,b-a$ does appear as consecutive integers in a unique vector. Therfore $a,b$ appear too and in a unique vector. Hence the proof.

SUMMARY: We can count the pairs of the consecutive integers by their left member and summarizing from above we have that if $a<n$ and $\gcd(a,n) = 1$, then eventually the integers $a,n-a$ will appear only once in the vectors. Note that the case $n-a,a$ is counted by using $n-a$. Therefore each integers appears $\phi(n)$ times in the final vector.