# recounting rationals

## 587 days ago by calkin

N=10^6 a=[1] for i in srange(1,N): if is_even(i): a.append(a[i/2]+a[i/2-1]) else: a.append(a[(i-1)/2])
first_occur={1:1}
first_occur.has_key(2)
 False False
for i in srange(N): if first_occur.has_key(a[i])==False: first_occur.update({a[i]:i})
list_plot_loglog(first_occur)
list_plot(first_occur)

The sequence 1,1,2,1,3,2,3,1,... gives rise to the sequence of fractions

1/1

1/2 , 2/1

1/3 , 3/2 , 2/3 , 3/1

1/4 , 4/3 , 3/5 , 5/2 , 2/5 , 5/3 , 3/4 , 4/1

How can we look at just the left half of the tree?

This is the half that hangs from the node labeled 1/2.

N=10^2 a=[1,2] for i in srange(2,N): if is_even(i): a.append(a[i/2]+a[i/2-1]) else: a.append(a[(i-1)/2])
print a
 [1, 2, 3, 2, 5, 3, 5, 2, 7, 5, 8, 3, 8, 5, 7, 2, 9, 7, 12, 5, 13, 8, 11, 3, 11, 8, 13, 5, 12, 7, 9, 2, 11, 9, 16, 7, 19, 12, 17, 5, 18, 13, 21, 8, 19, 11, 14, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 13, 11, 20, 9, 25, 16, 23, 7, 26, 19, 31, 12, 29, 17, 22, 5, 23, 18, 31, 13, 34, 21, 29, 8, 27, 19, 30, 11, 25, 14, 17, 3, 17, 14, 25, 11] [1, 2, 3, 2, 5, 3, 5, 2, 7, 5, 8, 3, 8, 5, 7, 2, 9, 7, 12, 5, 13, 8, 11, 3, 11, 8, 13, 5, 12, 7, 9, 2, 11, 9, 16, 7, 19, 12, 17, 5, 18, 13, 21, 8, 19, 11, 14, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 13, 11, 20, 9, 25, 16, 23, 7, 26, 19, 31, 12, 29, 17, 22, 5, 23, 18, 31, 13, 34, 21, 29, 8, 27, 19, 30, 11, 25, 14, 17, 3, 17, 14, 25, 11]

Assignment: figure out how to list all the fractions that appear on the tree hanging from 1/2 instead of 1/1.

Let us try to compute the matrix representing the fraction in the kth position of the tree hanging off a/b: if the fraction is

$\frac{ea+fb}{ga +hb}$

then the matrix is

$M_k = \begin{pmatrix} e & f\\ g& h \end{pmatrix}$

The matrices $M_k$ satisfy the recurrences

$M_{2k+1} = \begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} M_k$

$M_{2k+2} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} M_k$

N=2^18 M=[matrix(2,2 ,[1,0,0,1])] a=[2] for i in srange(1,N): if is_even(i): A=M[(i-2)/2] A = matrix(2,2,[1,1,0,1])*A M.append(A) else: A=M[(i-1)/2] A = matrix(2,2,[1,0,1,1])*A M.append(A) val=matrix(1,2,[0,1])*A*matrix(2,1,[1,2]) a.append(val[0,0])
#list_plot(a)
first_occur={2:1}
for i in srange(N): if first_occur.has_key(a[i])==False: first_occur.update({a[i]:i})
list_plot_loglog(first_occur)

What does this picture show us?  There appear to still be some gaps in the positions in which first occurences happen.  Remember, the vertical axis is showing where the first occurence of n takes place.

We see it even more clearly in the list_plot with non-log scales: the gaps are more noticeable.

list_plot(first_occur)
b=first_occur.values()
list_plot(b)
b.sort()
b[:10]
 [1, 1, 3, 5, 9, 11, 15, 17, 19, 21] [1, 1, 3, 5, 9, 11, 15, 17, 19, 21]
list_plot(b)
print len(b) print b[-1],N
 4596 240929 262144 4596 240929 262144
len(first_occur)
 4596 4596

Questions:

1. Where are the gaps in the sorted list of positions where first occurrences happen?  Are powers of 2 involved?  How long are the biggest gaps? Where on the tree do these positions correspond to?

2. In the list of numbers which first occur in the first N values of the sequence, which numbers are "missing"?  Which numbers are "latecomers" in the sequence a[n].

3. How fast does the list of numbers which first occur in the first N values of the sequence grow as a function of N?