Abstract: MATH/CHEM/COMP 2002, Dubrovnik, June 24-29, 2002

 

 

On explicit bijection between non-negative integers and rationals AND Knuth's problem

 

Dragutin Svrtan

 

Department of Mathematics, Faculty of Science and Mathematics, University of Zagreb, Bijenička c. 30, HR-10002 Zagreb, Croatia

 

 

 

We show that a sequence, defined by q0 = 0, q2m = qm/(1 + qm), m > 0, and q2m+1 = 1 + qm generates (without repetitions) all non-negative rational numbers. A shorter recurrence is as follows: 1/qn = qn - 1+ 1 {qn-1}. Then qn - 1= ε2 (n) (=k if n is divisible by 2k but not by 2k+1) leads to a solution of a recent problem of Knuth. A bijective discontinous function h: R0+R+, h(x) = 1/(2x + 1 x) is discovered, which realizes the sequence (qn)n No as one injective trajectory (through 0), since hom(0) = qm, m 0.

A wide Open Problem: Describe explicitly other trajectories of h in various number fields. In terms of the sawtooth function ((x)) one can write 1/h(x) = x 2((x)) + d(x). The inverse of h is given by h-1(x) = 1/x 2((1/x)) - d(1/x). The results above and some conjectures (for quadratic extensions) are done jointly with I. Urbiha.