# puzzle about array of numbers

Consider an array of numbers
$$\color{#C00000}{1}\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ 2\ 7\ 5\ 3\ 7\ 4\ 5\ 6\ 7\ }\color{#C00000}{1}\\ 1\ \hphantom{7\ 6\ 5\ 4\ 7\ 3\ 5\ 7\ }\color{#C00000}{2}\ \hphantom{7\ 5\ 3\ 7\ 4\ 5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ 5\ 4\ 7\ }\color{#C00000}{3}\ \hphantom{5\ 7\ }2\ \hphantom{7\ 5\ }\color{#C00000}{3}\ \hphantom{7\ 4\ 5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ 5\ }\color{#C00000}{4}\ \hphantom{7\ }3\ \hphantom{5\ 7\ }2\ \hphantom{7\ 5\ }3\ \hphantom{7\ }\color{#C00000}{4}\ \hphantom{5\ 6\ 7\ }1\\ 1\ \hphantom{7\ 6\ }\color{#C00000}{5}\ 4\ \hphantom{7\ }3\ \color{#C00000}{5}\ \hphantom{7\ }2\ \hphantom{7\ }\color{#C00000}{5}\ 3\ \hphantom{7\ }4\ \color{#C00000}{5}\ \hphantom{6\ 7\ }1\\ 1\ \hphantom{7\ }\color{#C00000}{6}\ 5\ 4\ \hphantom{7\ }3\ 5\ \hphantom{7\ }2\ \hphantom{7\ }5\ 3\ \hphantom{7\ }4\ 5\ \color{#C00000}{6}\ \hphantom{7\ }1\\ 1\ \color{#C00000}{7}\ 6\ 5\ 4\ \color{#C00000}{7}\ 3\ 5\ \color{#C00000}{7}\ 2\ \color{#C00000}{7}\ 5\ 3\ \color{#C00000}{7}\ 4\ 5\ 6\ \color{#C00000}{7}\ 1\\$$ The pattern: starting from 1 1, every consecutive natural number n will be inserted between two numbers beside each other whose sum equals n (2 between 1 1, 3 between 1 2, 4 between 1 3, etc )
You can see this pattern displayed above.
My question is: what is a(n) - the number of times we will have to write n in the nth row ?

My attempt: trying to find recursive formula between a(n) and a(n+1), but this seems hard.

-
$a(n)=$number of times you'll have to write $n$, where? The question is abit ambiguous. An illustration will be helpful. –  user21436 Feb 5 '12 at 9:51
Oh sorry i fixed the ambiguity. –  Geralt of Rivia Feb 5 '12 at 10:10
Huh, but isn't it simple: $$a(n)=\begin{cases}1, ~~ n \neq 2\\2~~ \text{otherwise} \end{cases}$$ –  user21436 Feb 5 '12 at 10:13
Holy Cow, I am sorry. –  user21436 Feb 5 '12 at 10:17
I modified your array in an attempt to make it clearer. Feel free to revert if you don't like it. –  robjohn Feb 27 '13 at 16:52

Your initial sequence of numbers consists in the denominators of the very well studied Farey sequence.

For $n\ge 2$ we have : "the number of elements of $F_n$ having denominator $n$ is equal to $\phi(n)$" : the Euler phi function.

A fascinating introduction to Farey sequences with the link to Ford circles may be found in Burger's excellent book 'Exploring the number jungle'.

-
In order to prove each row mentioned is denominators of Farey sequence, i must prove that the fractions add to F(n) is mediant of two consecutive elements in it, using the theorems of that book. From then i can deduce the answer of $\phi(n)$. However i'm having trouble with theorem 2.8 and 2.10 (2.7 is direct consequence of 2.5 and 2.6) –  Geralt of Rivia Feb 8 '12 at 16:57

This was too long for a comment so...

Theorem 2.8 : if $\frac pq\lt\frac rs$ are two consecutive fractions of $F_n\$ then $ps-rq=-1$

Let's use the hint provided in the book : "Prove this theorem by induction on $N$. Assume the statement holds for $N=n$ and consider a rational number $a/b \in [0,1]$ with $b\gt n$. Show that $a/b$ must reside between two consecutive elements of $F_n$. What is the smallest $b$ could possibly be?"

At this point you should admit that $\frac pq\lt\frac ab\lt\frac rs$ with $\frac pq$ and $\frac rs$ consecutive fractions of $F_n$ so that, from Lemma 2.6, $a=\lambda p+\mu r$ and $b=\lambda q+\mu s$ with $\lambda$ and $\mu$ positive integers (for zero we would have $\frac pq=\frac ab$ or $\frac ab=\frac rs$!). In conclusion the smallest possible value of $b$ is $q+s$, further we have $q+s\gt n\$ because else the fraction $\frac{p+r}{q+s}$ would have been inserted earlier!
The only 'free docks' for $b=n+1$ are those for which $q+s=n+1$ (the sum of two consecutive denominators of $F_n$ is $n+1$ or more).
I hope that these indications will help you to prove 2.8 as well as 2.10.

I think that the Euler $\phi\$ result is straightforward in Farey sequences : when you have to consider a new denominator $n\$ (appearing in $F_n\$) then you have only to insert the fractions $\frac an\$ such that $(a,n)=1\$ (and that's what $\phi\$ counts!) because else the fraction simplifies and appeared earlier...

-
oh i see. Thank you. This book is very interesting. Maybe i will buy it :D –  Geralt of Rivia Feb 9 '12 at 4:43