How do I create an algorithmic Tikz code to obtain a list of numbers which is conditionaly defined by a recurence relation?

Suppose, our initials are $a_{1,0}=0$, $a_{1,1}=1$ and $a_{1,j}=0$ for $j<0$. For given an integer $n$, define

$$a_{i,j}=\begin{cases} a_{i-1,\frac{j}{2}} & \text{ if j is even},\\ a_{i-1,\frac{j-1}{2}}+a_{i-1,\frac{j+1}{2}} & \text{ if j is odd} \end{cases}$$


while $2\leq i \leq n$ and $0\leq j \leq 2^{i-1}$. How can I write an algorithmic TikZ code to generate the following list (e.g.$n=6$):

The complete code:

\documentclass{article}
\usepackage{amsmath}
\usepackage{tikz}
\begin{document}
Suppose, our initials are $a_{1,0}=0$, $a_{1,1}=1$ and $a_{1,j}=0$ for $j<0$. For given an integer $n$, define

$$a_{i,j}=\begin{cases} a_{i-1,\frac{j}{2}} & \text{ if j is even},\\ a_{i-1,\frac{j-1}{2}}+a_{i-1,\frac{j+1}{2}} & \text{ if j is odd} \end{cases}$$

while $2\leq i \leq n$ and $0\leq j \leq 2^{i-1}$
\end{document}


I want the following output:

0 1

0 1 1

0 1 1 2 1

0 1 1 2 1 3 2 3 1

0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1

0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1

-
Welcome to TeX.SE. Can you port what you have tried so far and exactly what you have had difficulty with? – Peter Grill Jan 29 '12 at 21:18
Why do you want to do this with TikZ? I don't see where the drawing comes into play. – Loop Space Jan 30 '12 at 8:35
@Andrew TikZ has several libraries that don't do any drawing but may still be useful for applications in general. For example, the option parsing library. For this application, the mathematical library may be useful, but it can be done without TikZ of course. – Marc van Dongen Jan 30 '12 at 9:43
@MarcvanDongen: Oh, I agree that it can be done with the tools of TikZ, and I probably would do it that way. But it seems to me that it doesn't have to be done with TikZ and others might know of ways to do it without which are more elegant/load fewer packages. Specifically saying TikZ in the question title seems to preclude those solutions, and I wondered if there was a reason why TikZ was preferred as it might be useful background information on the question. – Loop Space Jan 30 '12 at 10:36
In fact, I would like to draw a tessellation of Poincare disk. This algorithm is a part of it! – Farey Jan 30 '12 at 12:08

It's not a TikZ solution but a LuaLaTeX one.

% !TEX encoding   = UTF-8
% !TEX program    = LuaLaTeX
% !TEX spellcheck = en_GB
\documentclass{article}

\usepackage{luacode}
\usepackage{amsmath}
\usepackage{xcolor}

\begin{document}
Suppose, our initials are $a_{1,0}=0$, $a_{1,1}=1$ and $a_{1,j}=0$ for $j<0$. For given an integer $n$, define
$a_{i,j}=% \begin{cases} a_{i-1,\frac{j}{2}} & \text{ if j è pari},\\ a_{i-1,\frac{j-1}{2}}+a_{i-1,\frac{j+1}{2}} & \text{ if j è dispari} \end{cases}$

while $2\leq i \leq n$ and $0\leq j \leq 2^{i-1}$

\noindent
\begin{luacode*}
---------------------------
-- Variables declaration --
---------------------------
local N    = 6
local A    = {}

--------------------
-- Initialization --
--------------------
A[1]    = {}
A[1][0] = 0
A[1][1] = 1

-----------------------------------
-- Computations and tex.printing --
-----------------------------------
tex.print(A[1][0].." "..A[1][0].."\\\\")
for i=2,N do
A[i] = {}
for j=0,2^(i-1) do
if math.ceil(j/2)==math.floor(j/2) then
A[i][j] = A[i-1][j/2]
else
A[i][j] = A[i-1][(j-1)/2]+A[i-1][(j+1)/2]
end
tex.print(A[i][j])
end
tex.print("\\\\")
end
\end{luacode*}
% TO TEST
\rule{\textwidth}{1pt}
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1
\end{document}


Enjoy!

-
Very nice demonstration of when the Lua part of Lua(La)TeX becomes the simpler option. – Loop Space Jan 30 '12 at 14:02

In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond precisely to the positive rational numbers, whose values are ordered from left to right as in a search tree.(Wikipedia)

Brocot-tree

Your list of numbers are the numerators of the rational numbers of Brocot tree.

We can get these numbers with a mono-dimensional list or array. It's possible to build manually this list but some useful tools exist like some tools in pgfplots to work on lists and arrays but here I want to try arrayjobx. This is a recent update of arrayjob.

Well it's more easy to use Maple, Mathematica, Maxima or Lua but for the fun I prefer TeX. The next code is not optimized. I used the first ideas ...

We need to define the list :

I have not read all the doc of arrayjobx but I think the first element has an index =1.

\documentclass[11pt]{scrartcl}
\usepackage{arrayjobx,tikz}

\begin{document}
\parindent=0pt
\newcounter{compt}\setcounter{compt}{2}% we need a counter
\newarray\brocot
\expandarrayelementtrue% idon't know if this macro is necessary
0\ \brocot(1)\ % I don't try \brocot(0)
\makeatletter
\loop
\ifodd\thecompt% iseven is possible with tikz iseven comes from tkz-berge
\pgfmathtruncatemacro{\tmpabrocot}{(\thecompt-1)/2}%
\checkbrocot(\tmpabrocot)%
\let\@tempa\cachedata
\pgfmathtruncatemacro{\tmpbbrocot}{(\thecompt+1)/2}%
\checkbrocot(\tmpbbrocot)%
\let\@tempb\cachedata
\pgfmathtruncatemacro{\tmpbrocot}{\@tempb+\@tempa}%
\brocot(\thecompt)={\tmpbrocot}% perhaps we can use a better code
\brocot(\thecompt)\ %
\else
\pgfmathtruncatemacro{\tmpbrocot}{\thecompt/2}%
\checkbrocot(\tmpbrocot)%
\brocot(\thecompt)={\cachedata}%
\brocot(\thecompt)\ %
\fi

Perhaps better is to use : pgfplotsliststructureext.code.tex for tikz/pgfplots solution – Alain Matthes Feb 1 '12 at 9:42