recounting rationals

1137 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?

4. Are there other good questions to ask about this?

5. As N changes, the graph looks very self-similar: if we look at 2^10, 2^11, 2^12, up to 2^18, how similar are the plots?  In particular, is there a strange function to which the graphs are "converging"?

6. If we take the sorted list b, and look at the consecutive differences, the gaps will show up as "spikes" in a list plot.  Where are the spikes, and how high are they?

7. Which numbers are latecomers?   How can we identify them?  How should we define a "latecomer"?  Perhaps a latecomer should be a number that occurs later than all numbers smaller than it.  How many latecomers are there up to N?