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

Question

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

Answer 1

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!

Answer 2

Interesting question about Mathematics :)

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
\readarray{brocot}{1}% the real first number
\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  
\ifnum\thecompt<32 \addtocounter{compt}{1}%
\repeat  

\brocot(25)
\end{document}