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 q₀ = 0, q_2m = q_m/(1 + q_m), m > 0, and q_2m+1 = 1 + q_m generates (without repetitions) all non-negative rational numbers. A shorter recurrence is as follows: 1/q_n = _└q_n - 1_┘+ 1 – {q_n-1}. Then _└q_n - 1_┘= ε₂ (n) (=k if n is divisible by 2^k but not by 2^k+1) leads to a solution of a recent problem of Knuth. A bijective discontinous function h: R₀⁺ → R⁺, h(x) = 1/(2_└x_┘ + 1 – x) is discovered, which realizes the sequence (q_n)_{nÎ No}  as one injective trajectory (through 0), since h^om(0) = q_m, 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.