4
$\begingroup$

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.

  • 1
    I modified your array in an attempt to make it clearer. Feel free to revert if you don't like it.2013-02-27

2 Answers 2

8

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'.

  • 0
    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)2012-02-08
1

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...

  • 0
    oh i see. Thank you. This book is very interesting. Maybe i will buy it :D2012-02-09