# TikZ - Recursive Arc Drawing

I'm trying to make Farey diagrams similar to those seen here (click) or the screenshot as follows,

Namely, I'd like an example of the one seen on the top of page 6. From there I hope I can figure out how to do the rest. Anyway, I was wanting to do this using TikZ and I was hoping to have some algorithm that could generate these images for n levels deep.

Here is my brute-force attempt:

    \documentclass[tikz]{standalone}
\begin{document}
\begin{tikzpicture}[scale=12]
\draw (0,0) -- (1,0);
\draw (0,0) -- (0,.618);
\draw (1,0) -- (1,.618);
\draw (1,0) arc (0:180:.5);

\draw [dotted] (0,0) -- (0,-.1) node[below]{$\frac{0}{1}$};
\draw [dotted] (1,0) -- (1,-.1) node[below]{$\frac{1}{1}$};

\draw (1,0) arc (0:180:.25);
\draw [dotted] (.5,0) -- (.5,-.1) node[below]{$\frac{1}{2}$};
\draw (.5,0) arc (0:180:.25);

\draw (1,0) arc (0:180:1/6);
\draw [dotted] (2/3,0) -- (2/3,-.1) node[below]{$\frac{2}{3}$};
\draw (2/3,0) arc (0:180:1/12);

\draw (1/3,0) arc (0:180:1/6);
\draw [dotted] (1/3,0) -- (1/3,-.1) node[below]{$\frac{1}{3}$};
\draw (1/2,0) arc (0:180:1/12);

\end{tikzpicture}
\end{document}


which yields

I have to admit, I'm a novice when it comes to TikZ and to programming in LaTeX. So any help, no matter how basic, would be appreciated. Thanks.

-
Interesting question! –  Who is crazy first Mar 16 at 7:34
I mean this is a TeX site not a math site. Not everybody is familiar with these definitions (though I am kind of) –  percusse Mar 16 at 10:26
@percusse: It is the standard mediant definition $\frac{a}{b} \oplus \frac{c}{d} = \frac{a+c}{b+d}$. 1. F1 = { 0/1, 1/1 }, 2. F2 = { 0/1, 1/2, 1/1 }, 3. F3 = { 0/1, 1/3, 1/2, 2/3, 1/1 }, and so on. –  Anon Mar 16 at 10:39

It is not any different than the examples given by other languages. Only a few places where expansion needs to be taken care of. I didn't really go for the code golf but it seems working. And it gets fainter as the recursion depth increases.

\documentclass[tikz]{standalone}
\newcount\recurdepth
\begin{document}
\begin{tikzpicture}[scale=2]
\draw[style=help lines] (0,0) grid[step=0.1cm] (1,0.5);

\def\myrecur#1#2#3#4#5{
\recurdepth=#5
\ifnum\the\recurdepth>1\relax
\edef\tempnum{\number\numexpr#1+#3\relax}%a+b
\edef\tempden{\number\numexpr#2+#4\relax}%c+d
\pgfmathparse{\tempnum/\tempden}\edef\temp{\pgfmathresult}%(a+b)/(c+d)

\node[below=\the\recurdepth*1pt,scale=0.1*\the\recurdepth]at({(\temp)*1cm},0){$\frac{\tempnum}{\tempden}$};
\draw[ultra thin,opacity=\the\recurdepth/10] ({(\temp)*1cm},0) arc (180:0:{((#3/#4)-\temp)*0.5cm});
\draw[ultra thin,opacity=\the\recurdepth/10] ({(\temp)*1cm},0) arc (0:180:{(\temp-(#1/#2))*0.5cm});
\begingroup
\edef\ttempup{\noexpand\myrecur{\tempnum}{\tempden}{#3}{#4}{\the\recurdepth}}
\edef\ttempdown{\noexpand\myrecur{#1}{#2}{\tempnum}{\tempden}{\the\recurdepth}}
\ttempup\ttempdown
\endgroup
\fi
}

\myrecur{0}{1}{1}{1}{6}

\end{tikzpicture}
\end{document}


-
Quite impressive! Would it be also possible with the same kind of code to limit the Farey numbers shown in the figure to the members of one Farey sequence Fm? For example, if there are 5 levels of recursion, how could we manage that only the Farey sequence F5 (0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1) and its diagram were displayed in the figure? I've –  fpast Mar 17 at 9:09
(following the previous comment): As I figure it, it would involve a TeX equivalent of the conditional instruction I use myself in my MetaPost program, but the logical connector or doesn't seem to exist in basic TeX programming. It seems that the etoolbox package offers a solution, I will look into it. –  fpast Mar 17 at 9:20
@fpast it is possible. pgfmath offers OR operation for checking conditionals. So one can check the \tempden value to limit the evaluation but I don't know the definition of Fm. I can have a look if you need it. –  percusse Mar 17 at 9:35
Well, I don't really need it since I'm not the original poster and since my own solution with MetaPost works well, so please don't bother for my sake if it takes too much of your time! But I'm curious about TeX and tikz programming despite (or because) the fact I know very little about them. BTW, to obtain Fm with your code, m being a new parameter, i think it would also suffice in your program to check if the \tempden value is lesser than of equal to m before going into a new recursion. –  fpast Mar 17 at 10:12

Without numbers:

\documentclass[tikz]{standalone}
\begin{document}
\begin{tikzpicture}
\draw [ultra thick] (-8,0) -- (8,0);
\draw [ultra thick] (0,0) circle (8);
\foreach \i in {0,1,2,3} {%
\draw [ultra thick] (90*\i:8) arc (270+90*\i:180+90*\i:8);}
\foreach \i in {0,1,...,7} {%
\draw [very thick] (45*\i:8) arc (270+45*\i:135+45*\i:3.3);}
\foreach \i in {0,1,...,15} {%
\draw [thick] (22.5*\i:8) arc (270+22.5*\i:112.5+22.5*\i:1.6);}
\foreach \i in {0,1,...,31} {%
\draw [thin] (11.25*\i:8) arc (270+11.25*\i:101.25+11.25*\i:0.8);}
\foreach \i in {0,1,...,63} {%
\draw [ultra thin] (5.625*\i:8) arc (270+5.625*\i:95.625+5.625*\i:0.4);}
\end{tikzpicture}
\end{document}


-
Impressing compact algoritm. –  Sveinung Mar 16 at 9:59
@marchetto: Thanks. I appreciate the post. But it doesn't answer the question posed. –  Anon Mar 16 at 10:00
@Anon You did post a screenshot of a figure like this, and wrote "I'm trying to make Farey diagrams similar to ... the screenshot as follows,". This answer did indeed answer the question before the update. If the posted figure was not the desired result, I'd say your question was a bit misleading. –  nordev Mar 16 at 11:09
@nordev: I did no such thing. It was edited by someone else. –  Anon Mar 16 at 11:12
@Anon Oh, sorry, my bad. I just remembered seeing a figure like the above in the question, and wrongly assumed it was part of the original question. To be honest, I got a bit confused as you referred to the figure on top of page 6, which was not the same as the figure posted. Guess this makes it clear why they were not the same :) –  nordev Mar 16 at 11:16

I was wondering the same thing yesterday in the comments of this answer on a close subject. For recursive drawings as this one are (relatively!) easy to do with languages closely related to (La)TeX, but external to it, as MetaPost or Asymptote. For example, here is my "quick and dirty" attempt with MetaPost on the Farey diagram illustrated in the original post. It shows how natural it is with this language to implement a recursive drawing:

input latexmp;
setupLaTeXMP(packages="amsmath", options = "12pt", textextlabel = enable, mode = rerun);

numeric u, m;
u = 20cm; % scale
m = 8; % maximal denominator

% [a/b, c/d]: diameter, n: recursion level
def farey_diagram(expr a, b, c, d, n) =
draw halfcircle scaled ((c/d-a/b)*u) shifted (u*0.5[a/b,c/d], 0);
if (n > 1) and (b+d <= m):
label.bot("$\dfrac{" & decimal(a+c) & "}{"& decimal(b+d) & "}$", u*((a+c)/(b+d), 0));
farey_diagram(a, b, a+c, b+d, n-1); farey_diagram(a+c, b+d, c, d, n-1);
fi;
enddef;

beginfig(1);
draw origin -- (u, 0);
label.bot("$0$", origin); label.bot("$1$", (u, 0));
% starting with 0/1 and 1/1; m levels of recursion needed
farey_diagram(0, 1, 1, 1, m);
endfig;
end.


So does it mean that we should better revert to external programs as MetaPost or Asymptote each time we have to draw something recursively? It would be a bit of a surprise, since I know how powerful (La)TeX packages as PSTricks, Tikz, or mfpic (the one among the three that I regularly use for my personal work) are.

EDIT Having read a bit more about Farey diagrams and series, I've tried to refine my code, only allowing the fractions with denominators lower than or equal to the number of recursion levels. Thus farey_diagram(0, 1, 1, 1, m) typesets the numbers of the Farey series Fm (and only them) and draws the corresponding semicircles.

-
Thanks. I have never used MetaPost before. One more thing to add to my list of things to study up on. –  Anon Mar 16 at 13:25

This is cheating. Utterly, utterly cheating.

It’s a Python script which generates the TikZ necessary to draw a Farey diagram. I use the definition from the Wikipedia page on Farey numbers to generate the successive Farey sequences. This gets processed into a form suitable for TikZ: a list of terms num/denom/nextnum/nextdenom which you can loop over with \foreach. Then some fairly clunky TikZ gets produced and printed.

Configuration:

• last_level is the number of levels which get shown.
• labelled_level determines which level gets fractional labels with dashed lines (can be different from the number of levels so that everything doesn’t overlap horribly)
• label_dist sets how far the labels are set below the diagram. I used the distance from your original.
• tikz_scale defines the [scale] parameter passed to TikZ.
• axis_height defines how high the left and right axes are.

If you run the script, it prints the tikzpicture code, which you can copy and paste into your document. If you prefer, it would be easy to write this out to a file, which you could \input into TeX.

Here’s the script:

last_level = 10
labelled_level = 3

label_dist = 0.1
tikz_scale = 12

axis_height = 0.618

def farey_sequence(n):
"""Returns the nth Farey sequence in ascending order."""
farey_list = []
a, b, c, d = 0, 1, 1, n
farey_list.append("%d/%d" % (a, b))
while c <= n:
k = int((n + b) / d)
a, b, c, d = c, d, k * c - a, k * d - b
farey_list.append("%d/%d" % (a, b))

return farey_list

def tikz_farey_sequence(n):
"""Returns the nth Farey sequence, suitable for processing in TikZ."""
farey = farey_sequence(n)
twinned_pairs = [farey[i] + '/' + farey[i+1] for i in xrange(len(farey) - 1)]
return str(twinned_pairs)[1:-1].replace("'", "")

tikz_lines = [
'\\begin{tikzpicture}[scale=%d]' % tikz_scale,
'',
'\\draw (0,%f) -- (0,0) -- (1,0) -- (1,%f);' % (axis_height, axis_height),
''
]

for lvl in range(last_level):
new_lines = [
'\\foreach \\a/\\b/\\c/\\d in { %s } {' % tikz_farey_sequence(lvl + 1),
'  \\draw (\\a/\\b, 0) arc (180:0:\\c / \\d / 2 - \\a / \\b / 2);']

if lvl == labelled_level:
new_lines.extend([
'  \\draw [dotted] (\\a/\\b, 0) -- (\\a/\\b, -%f) node [below] {$\\frac{\\a}{\\b}$};' % label_dist,
'}',
'\\draw [dotted] (1/1, 0) -- (1/1, -%f) node [below] {$\\frac{1}{1}$};' % label_dist,
''])
else:
new_lines.extend(['}',''])

tikz_lines.extend(new_lines)

tikz_lines.append('\\end{tikzpicture}')

print '\n'.join(tikz_lines)


And here’s an example of the output:

It could probably be improved, but it should do for now.

Somebody with more LaTeX chops than me could probably reproduce this with something like expl3 or etoolbox, but I can’t. I tried, but I don’t know enough LaTeX to do it properly. This could probably be done in TeX alone, but I almost always resort to external programs for this sort of recursive diagram.

-
We are "cheating" the same way, it seems. Although I daresay that MetaPost/Asymptote are closer to LaTeX than Python. :-) Or maybe not? The point is that they are no (La)TeX packages, anyway, since they are distinct programming languages. –  fpast Mar 16 at 13:27
Thanks for thoughtful reply. I typically cheat too when it comes to this sort of problem. After reading you Python script to calculate the Farey numbers, I realized I could have posted my Maple code for handling that. Sorry for the inconvenience. –  Anon Mar 16 at 13:29

A partial answer: I think this produces the sequences correctly. It needs lualatex.

\documentclass[border=5]{standalone}
\usepackage{pgffor}
{\catcode\%=11\gdef\pc{%}}
\directlua{
Rational = {}
Rational.__index = Rational

function Rational.new(p, q)
local a, b, object
a, b = p, q
while b > 0 do
a, b = b, a \pc b
end
object = {p=p/a, q=q/a}
setmetatable(object, Rational)
return object
end

function Rational:toString()
return "" .. self.p .. "/" .. self.q
end

function Rational.__eq(P, Q)
return (P.p == Q.p) and (P.q == Q.q)
end

return Rational.new(P.p*Q.q + Q.p*P.q, P.q*Q.q)
end

function Rational.__sub(P, Q)
return Rational.new(P.p*Q.q - Q.p*P.q, P.q*Q.q)
end

Sequence = {}
Sequence.__index = Sequence

function Sequence.new()
local object = {data={}, n=0}
setmetatable(object, Sequence)
return object
end

function Sequence:get(i)
return self.data[i]
end

function Sequence:append(v)
table.insert(self.data, v)
self.n = self.n + 1
end

function Sequence:toString()
local s, i
s = ""
if self.n > 0 then
s = s .. self.data[1]:toString()
if self.n > 1 then
for i = 2,self.n do
s = s .. "," .. self.data[i]:toString()
end
end
end
return s
end

function farey_sequence(n)
local f1, f2, t1, t2, i, j
f1 = Sequence.new()
f1:append(Rational.new(0,1))
f1:append(Rational.new(1,1))
if n > 1 then
for i = 1,n do
f2 = f1
f1 = Sequence.new()
for j = 1, f2.n-1 do
t1 = f2:get(j)
t2 = f2:get(j+1)
f1:append(t1)
if (t2-t1 == Rational.new(1, t1.q*t2.q)) and t1.q+t2.q <= n then
f1:append(Rational.new(t1.p+t2.p, t1.q+t2.q))
end
end
f1:append(t2)
end
end
return f1
end
}

\def\getfareysequence#1#2{%
\edef#1{\directlua{tex.print(farey_sequence(#2):toString())}}%
}
\begin{document}
\begin{minipage}{4in}
\foreach \i in {1,...,8}{
\getfareysequence\A{\i}
$F_{\i}=\left\{\foreach \n/\d [count=\k] in \A {\ifnum\k>1,\fi\frac{\n}{\d}}\right\}$
\\[.5ex]
}
\end{minipage}
\end{document}
`

-