Hyperbinary conjecture seeking proof for a good time, long walks on the beach

Here’s the latest progress on the hyperbinary sequence. We’re trying to figure out the inverse relation of the function $h$ : given a particular number $n$ , where does it occur in the hyperbinary sequence? That is, what are the values of $k$ for which $h(k) = n$ ?

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 $h(2^k - 2) = k$ and $h(2^k) = k+1$ . These correspond to the numbers that occur right next to 1 in the sequence (we saw earlier that $h(2^k-1) = 1$ ).
Brendan also proved that $h(2^{p+q} - 2^q) = 1 + pq$ . 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 $n$ is $\phi(n)$ . $\phi$ denotes the so-called Euler totient function; $\phi(n)$ is defined to be the number of positive integers smaller than $n$ which are relatively prime to $n$ . 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 $h^{-1}$ !

Can anyone find a proof of Fergal’s conjecture?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

4 Responses to Hyperbinary conjecture seeking proof for a good time, long walks on the beach

Fergal Daly says:

October 12, 2009 at 7:28 pm

I don’t have a solution but I have some interesting stuff and since I have no time and no sign of a solution I thought I’d share what I have and see if anyone else can make progress.

I can get a bunch of things like

h(2^n + 0) = 1n + 1
h(2^n + 2) = 2n – 1
h(2^n + 4) = 3n – 4
h(2^n + 6) = 3n – 5
h(2^n + 8) = 4n – 9
h(2^n + 10) = 5n – 12
h(2^n + 12) = 5n – 13
h(2^n + 14) = 4n – 11
h(2^n + 16) = 5n – 16
h(2^n + 18) = 7n – 23
h(2^n + 20) = 8n – 27
h(2^n + 22) = 7n – 24
…
h(2^n + m) = h(m)n – C

The details are a bit too much for a comment (including some python code). So I’ve posted them over here.
JM says:

October 12, 2009 at 11:14 pm

This sequence is another form of the Calkin-Wilf tree. Making a list of the ratios of adjacent numbers in the sequence in order is equivalent to listing off the fractions on the tree in order.

Keeping that in mind, we can say that the two figures next to a number occurring primarily also appeared next to each other earlier in the sequence. Those two numbers can be a and b, with the number occurring primarily being n.

So, a+b=n. If n=6 for example, a and b could be 1 and 5 or 5 and 1, but not 2 and 4, 4 and 2, or 3 and 3. Why? Because a/b has to occur on the Calkin-Wilf tree, since a and b are next to each other at some point. Brent has already shown that numbers on the tree are in lowest terms, so a and b must be relatively prime. A is relatively prime to b only when it is relatively prime to n, so the number of primary occurrences n has is limited by the number of relatively prime numbers there are less than n. Also, because every rational number appears on the Calkin-Wilf tree, every relatively prime number lower than n will appear as a at some point.

Whew! I hope that wasn’t too complicated. Am I right?
Brent says:

October 13, 2009 at 7:45 am

JM: yes! I came to the same realization last night and actually laughed out loud. =) The funny thing is that this is an elegant proof of the fact that the number of primary occurrences of n is phi(n), which nonetheless doesn’t shed any light on how to compute the inverse relation of h (…or does it?). Sort of sneaky.
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled

Comments are closed.