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$
  • 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$ – Benedict W. J. Irwin Feb 22 '18 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$ – Benedict W. J. Irwin Feb 22 '18 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$ – Benedict W. J. Irwin Feb 22 '18 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$ – Michael Feb 22 '18 at 15:52
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$
  • $\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 '18 at 15:22
  • 1
    $\begingroup$ Thank you for such a detailed answer. $\endgroup$ – Igor Feb 22 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.