Recounting the Rationals
- Recounting the Rationals, part I
- Recounting the Rationals, part II (fractions grow on trees!)
- Recounting the Rationals, part III
- Recounting the Rationals, part IV
- Recounting the Rationals, part IVb: the Euclidean Algorithm
- Challenge #12: sums of powers of two
- Challenge #12 solution, part II
- More hyperbinary fun
- Hyperbinary conjecture seeking proof for a good time, long walks on the beach
- The hyperbinary sequence and the Calkin-Wilf tree
Here’s the latest progress on the hyperbinary sequence. We’re trying to figure out the inverse relation of the function 
: given a particular number 
, where does it occur in the hyperbinary sequence? That is, what are the values of 
for which 
?
There are infinitely many, but in a previous post I argued why we only need to find occurrences at even positions of the sequence, which we call primary occurrences. I have no idea how easy or hard it is to give a general method for finding all primary occurrences. But some progress has been made:
- Brendan proved by induction that
and 
. These correspond to the numbers that occur right next to 1 in the sequence (we saw earlier that 
). - Brendan also proved that
. This is impressive, since this pattern certainly isn’t obvious (at least, it wasn’t to me!). - Fergal Daly conjectured that the number of primary occurrences of is
. 
denotes the so-called Euler totient function; is defined to be the number of positive integers smaller than which are relatively prime to . An explanation of this fact, if it is true (and it really looks like it might be!) would probably go a long way towards finding a general method for computing 
!
Can anyone find a proof of Fergal’s conjecture?
