10
$\begingroup$

I've come across a nice little combinatorial problem. Firstly we have vector $(1, 1)$. On each iteration for each two consecutive numbers in the vector we add their sum between them: $$(1, 2, 1)$$ $$(1, 3, 2, 3, 1)$$ $$(1, 4, 3, 5, 2, 5, 3, 4, 1)$$ $$(1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1)$$ ad infinitum.

Here's the question. How many times number $n$ will be written in the final vector? I'v computed the answers for $1, \dots, 15$: $$2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8$$

And this values coincide with the values of Euler's totient function. But how to prove that the answer is always $\phi(n)$? And can one simply derive this idea without explicitly writing first values?

$\endgroup$
4
  • 1
    $\begingroup$ For anyone who wants to explore this with Mathematica, v={1,2,1}; S[v_]:=Table[v[[k]]+v[[k+1]],{k,1,Length[v]-1}]; F[v_]:=Riffle[v,S[v]]; Nest[F,v,n] will give the nth vector $\endgroup$ Feb 22, 2018 at 14:35
  • 1
    $\begingroup$ If we start with the vector $(1,2)$, we seem to end up with $\lfloor n/\tau(n)\rfloor$, i.e. OEIS sequence A078709, where $\tau(n)$ is the number of divisors function. $\endgroup$ Feb 22, 2018 at 14:58
  • 1
    $\begingroup$ Ok, the iteration from $(1,2)$ I just suggested is not true like 1,1,1,1,2,1,3,2,3,2,5,2,6,3,4,4,8,3,9,4, whereas the real sequence A078709 goes like 1,1,1,1,2,1,3,2,3,2,5,2,6,3,3,3,8,3,9,3, so they are not the same, but very close. Your pattern for $\phi(n)$ seems to hold at least to $n=26$ $\endgroup$ Feb 22, 2018 at 15:11
  • 2
    $\begingroup$ These are the denominators in Farey Series. They generate all fractions between $0/1$ and $1/1$. You get the numerators by starting with $0,1$ instead of $1,1$. All these fractions turn out to be in lowest terms, so $\tau(n)$ of them will have $n$ in the denominator. $\endgroup$
    – Empy2
    Feb 22, 2018 at 15:52

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Igor I just completed my answer, so I would be glad if you could check and possibly point out some mistakes, if any. $\endgroup$
    – Stefan4024
    Feb 22, 2018 at 15:22
  • 1
    $\begingroup$ Thank you for such a detailed answer. $\endgroup$
    – Igor
    Feb 22, 2018 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .