The number of ways to write n as a sum of powers of 2, where each summand occurs at most three times, is (n/2) + 1 rounded down. See the 1983 Putnam exam, problem B2 (link goes to a solution, so don't go there if you want to think about the problem yourself!) I learned this from Bruce Reznick's paper "Some binary partition functions".
Of course, if we replace "three" by "one", the analogous problem is trivial -- it's just saying that the binary expansion of an integer is unique. If "three" is replaced by "two", we get an interesting sequence: let b(n) be the number of ways to write n as a sum of powers of two where each summansd occurs at most three times. So for example b(14) = 4, since we can write 14 as 8 + 4 + 2, 8 + 4 + 1 + 1, 8 + 2 + 2 + 1 + 1, or 4 + 4 + 2 + 2 + 1 + 1. I've alluded to this sequence before in comments. Starting with b(0), the sequence of b(n) is
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, ...
and we can make rational numbers out of these by taking b(n)/b(n+1):
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, ...
and it turns out this sequence includes each rational number exactly once! Neil Calkin and Herb Wilf wrote about this in their paper Recounting the rationals, which you should read. I first learned about this paper from Brent Yorgey's series of posts.
Subscribe to:
Post Comments (Atom)
8 comments:
Wow, that's great! I'll have to share this around--it's very interesting.
Phillie is playing the on team that no matter who they play I want to lose.
In fact I'd love to see them lose every game in a season.
This reminds me of the simplest adder used in digital electronics. It has 3 inputs and two outputs. The three input bits are of the same magnitude and can give results of 0, 1, 2, or 3. This requires two bits to code.
The high output bit is called the "carry out", and one of the three inputs is called the "carry in". One can use N of these to add two N-bit numbers.
I suspect that one could also use N of these to correct the binary description of a number which had as much as 3 copies of a given bit.
Also, "each rational number" should presumably be "each positive rational number".
Yeah, it's interesting stuff. I came across that paper in the course of solving one of the problems at projecteuler.net (which is awesome, btw).
I was a little surprised that the solution to the problem included a few obviously wrong statements. From context you could figure out what the author was trying to say, but it was still jarring. (For example, the claim that an even number would not be expressed as the sum of more than two 1's. Um, how about 4 = 1 + 1 + 1 + 1?)
@anonymous 2: Read the problem statement more carefully. The problem only considers representations which use each summand at most three times.
Yes, but the solution wasn't phrased that way. If so, it would have read something like "an even number expressed with at most three ones can only have two". Or even: "In the situations under consideration in this problem, an even number can be expressed as the sum of at most two ones".
As I said, it was easy to understand from context, but at first glance it read like (an obviously wrong)general statement.
Yeah. Papers are way easier to read when they restate the axioms in every sentence that discusses a conclusion.
Post a Comment