Challenge #12 solution, part II

Yes, that’s right, that Challenge #12, posted one year, five months, and a day ago. You see, I have this nasty habit of starting things and not finishing them… well, better late than never!

Question two of the aforementioned challenge asked this:

Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most twice? Say $h(n)$ denotes the number of different ways to write n as a sum of powers of two with at most two copies of each power allowed. What can you say about the function h?

These representations using at most two copies of each power of two are sometimes called hyperbinary representations. For example, 11 can be written as $2^3 + 2^1 + 2^0$ or as $2^2 + 2^2 + 2^1 + 2^0$ . It turns out these are the only hyperbinary representations of 11, so $h(11) = 2$ .

How to analyze this? We can use a similar approach to that outlined in the solution to part III (which asked a similar question, but allowing any number of copies of each power of two). First let’s think about odd numbers, that is, numbers of the form $2n + 1$ . Any representation of an odd number must include an odd number of copies of $2^0$ (otherwise the sum won’t be odd!), but since at most two copies are allowed, there must be exactly one copy of $2^0$ . If we take away the $2^0$ and divide everything else by two, we get a valid representation of $n$ . The reverse works as well: if we start with any valid representation of $n$ , multiply everything by two, and add a copy of $2^0$ , we get a valid representation of $2n + 1$ . This means that

$h(2n+1) = h(n)$ .

What about even numbers? A valid representation of $2n + 2$ has either two copies of $2^0$ , or none. If it has none, we can simply divide by two to get a valid representation of $n + 1$ (and vice versa); if two, we can take away the copies of $2^0$ and then divide by two to get a representation of $n$ , and vice versa. Therefore,

$h(2n+2) = h(n+1) + h(n)$ .

These two equations, $h(2n+1) = h(n)$ and $h(2n+2) = h(n+1) + h(n)$ , along with the fact that $h(0) = 1$ , are enough to completely characterize $h(n)$ . We can easily compute $h(n)$ for the first few values of $n$ :

1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1…

It’s immediately striking, of course, that $h(n)$ isn’t strictly increasing: that is, just because $m > n$ doesn’t mean $h(m) > h(n)$ . In fact, even as the values of $h(n)$ continue to get bigger on average, there are still some values of 1 hiding in there. In fact, $h(0) = h(1) = h(3) = h(7) = h(15) = 1$ , and the obvious conjecture is that $h(2^k - 1) = 1$ for every $k \geq 0$ .

The next thing we notice, after staring a bit, is that the $h(n)$ sequence contains a lot of palindromes! Every section sandwiched in between two 1’s seems to read the same forwards and backwards. Let’s make some graphs so we can see these patterns more easily: below I’ve made graphs showing $h(n)$ as $n$ goes from 1 to 100, 1000, and 10000, respectively.

Pretty! We can clearly see the symmetric structure here, and the way that it occasionally (every $2^k - 1$ ) jumps back down to 1.

Here’s another way to think about building the sequence. We start with the first two elements:

$1,$ $1$

Now we copy the red part onto the end of the sequence (the copy will be blue), leaving a blank space in front of each blue number:

$1$ , $1$ , $\underline{\phantom{x}}$ , $1$

Now we fill in each blank (in green) by adding the two numbers on either side of it:

$1$ , $1$ , $2$ , $1$

Now the blue and green part becomes the new red part:

$1,1$ , $2$ , $1$

Now we repeat! Copy the red part to the end, leaving a blank in front of each copied number:

$1,1$ , $2$ , $1$ , $\underline{\phantom{x}}$ , $2$ , $\underline{\phantom{x}}$ , $1$

Fill in each blank by adding the two numbers on either side:

$1,1$ , $2$ , $1$ , $3$ , $2$ , $3$ , $1$

And again: blue and green become the new reds, copy the red numbers to the end with a blank in front of each:

$1,1,2,1$ , $3$ , $2$ , $3$ , $1$ , $\underline{\phantom{x}}$ , $3$ , $\underline{\phantom{x}}$ , $2$ , $\underline{\phantom{x}}$ , $3$ , $\underline{\phantom{x}}$ , $1$

And fill in the blanks by adding:

$1,1,2,1$ , $3$ , $2$ , $3$ , $1$ , $4$ , $3$ , $5$ , $2$ , $5$ , $3$ , $4$ , $1$

And so on. It takes a little bit of thought, but it can be seen that the method I’ve described here is really just a different way of expressing the equations $h(2n+1) = h(n)$ and $h(2n+2) = h(n+1) + h(n)$ ! But thinking about it this way makes it apparent why a 1 always shows up at $h(2^k - 1)$ , and also why we end up with palindromes.

I’ll stop there for now; in an upcoming post I’ll bring things full circle by showing how these numbers relate to the Calkin-Wilf tree of
rationals.

About Brent

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

View all posts by Brent →

15 Responses to Challenge #12 solution, part II

JM says:

September 19, 2009 at 5:30 pm

Thanks for the post. I find this number sequence interesting. The further along you go in the sequence, the maximum value gets larger but the minimum is always 1.
Jason Dyer says:

September 19, 2009 at 7:00 pm

Well, goodness, you made the post. What will I hassle you about now?

That does remind me to try using that tree structure from the other post on your problem #3, because if it’s possible to generate it in a similar way it might answer the asymptotic growth problem you mention.
Brent says:

September 20, 2009 at 10:51 am

JM: Interesting, isn’t it? In fact, not only does 1 occur infinitely many times; EVERY number does! That is, no matter where you are in the sequence, there will always be another 2, and another 3, and so on…

Jason: Don’t worry, I’m sure you’ll be able to find *something* to hassle me about. 😉 What “tree structure” are you talking about? I’m not sure which post you’re referring to.
Jason Dyer says:

September 20, 2009 at 1:30 pm

My comment to your challenge.
http://www.mathlesstraveled.com/?p=113&cpage=1#comment-15872
JM says:

September 20, 2009 at 4:36 pm

A couple more observations:

The highest number between two 1’s is always a Fibbonocchi number, and is the next highest Fibbonocchi number from the one before it.

The most common number (I think) is 5, because 5 is the first number to appear 4 times between a set of 1’s, and 4 is (I think) the maximum.
Brent says:

September 20, 2009 at 9:41 pm

Jason: ah, right, I remember that now, it’s quite clever. Actually, maybe I’ll take another post to describe your solution, with some accompanying pretty pictures. =)
Dave says:

September 22, 2009 at 5:36 pm

Hey Brent,

Thanks for posting this long awaited solution. I don’t know if you ever saw it, but I started to try to solve this problem back in March 2009 and I left several (somewhat long-winded) responses. After reading your solution and seeing how simple and elegant it is, I’m embarrassed I didn’t think about it that way. However, if you don’t mind taking a look at my attempt, I’d like to know if there is some connection between the pattern I saw and the actual solution. Thanks for continuing to produce a really interesting site!
Brent says:

September 22, 2009 at 8:43 pm

Hi Dave,

Don’t be embarassed; sometimes it’s the simple, elegant solutions which are the hardest to see! I can assure you that I went down many convoluted rabbit trails the first time I thought about this problem.

Anyway, I do remember your comments but must confess that I never read them in great detail. I will take a look and let you know of any connections I can see!
Brent says:

September 24, 2009 at 11:52 am

Dave,

After looking more carefully at your comments on that old post, I am happy to report that your explorations were very much related to the solution I posted here. Most, if not all, of the conjectures you made are absolutely correct, and you also uncovered some interesting structure and questions that I hadn’t thought about. I hope to write up some of this in detail in an upcoming post!
Dave says:

September 27, 2009 at 6:25 am

Thanks for your time and attention. I look forward to the upcoming posts.
Pingback: Walking Randomly » Carnival of Maths #58
Pingback: More hyperbinary fun « The Math Less Traveled
Pingback: Hyperbinary conjecture seeking proof for a good time, long walks on the beach « The Math Less Traveled
Pingback: The hyperbinary sequence and the Calkin-Wilf tree « The Math Less Traveled
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled

Comments are closed.