I'm going to be presenting (some of) stuff next month at Gathering for Gardner 13, and I'd like to be able to tie things up with a pretty bow (whether or not I include the proof in my six-minute presentation). So I'll show you how to count up to twelve in base 2&3 (using the digits 0,1,2,3,4), and I'll show you why numbers sixteen and higher can't be expressed in base 2&3, and then maybe one of you will figure out what's happening with thirteen, fourteen, and fifteen. The game in base 2&3 is to find a radix expansion that represents the counting number n regardless of whether the radix is taken to be 2 or 3. E.g., 2r+4+4/r+4/r^2+4/r^3+... equals twelve when you put r=2 or r=3, so 24.444... represents twelve in base 2&3. (2r+4+4/r+4/r^2+4/r^3+... is a Laurent series in 1/r, which is why I brought the word "Laurent" into my original phrasing of the problem. But, aside from this being overly nerdy and unmotivated, I phrased it wrong: once you get past n=4, you need a Laurent SERIES, not a Laurent polynomial.) Anyway, here's the way to (start to) count: One is 1.000... Two is 2.000... Three is 3.000... Four is 4.000... Five is 11.222... Six is 12.222... Seven is 13.222... Eight is 14.222... Nine is 21.444... Ten is 22.444... Eleven is 23.444... Twelve is 24.444... To see what goes wrong with n greater than or equal to sixteen, suppose n equals f(r) = a_d r^d + ... + a_1 r + a_0 + b_1 / r + b_2 / r^2 + b_3 / r^3 + ... for both r=2 and r=3, where each digit a_i or b_i is 0, 1, 2, 3, or 4, and the leading digit a_d is non-zero. First I'll show that in order for f(r) to take a value greater than (or equal to) sixteen when r=2, we'll need d to be 2 or higher. Then I'll show that when d is 2 or higher, the values taken by f(r) when r=2 and r=3 can't be the same. To start, note that f(r) is bounded by 4 r^d + 4 r^(d-1) + ... = 4 r^d / (1 - 1/r) = 4 r^(d+1) / (r - 1), which equals 2^(d+3) when r = 2. If d is 1, this upper bound on n is 16. So if n is greater than sixteen, we'll need d to be 2 or higher. (The boundary case n = 16 requires slightly more care; you need to check that 4r+4+4/r+4/r^2+4/r^3+... doesn't equal 16 with r=3.) Now suppose d > 1; let's show that f(3) - f(2), rather than being 0, is positive. Write f(3) - f(2) = a_d (3^d - 2^d) + ... + a_1 (3 - 2) + a_0 (1 - 1) + b_1 (1/3 - 1/2) + b_2 (1/9 - 1/4) + ... a_d (3^d - 2^d) is at least 1 (3^2 - 2^2) = 5, and the other terms involving the a-digits are non-negative. The only way f(3) - f(2) could be 0 is if the terms involving the b-digits add up to 5 or greater. But this can't happen, since the maximum possible value of b_1 (1/2 - 1/3) + b_2 (1/4 - 1/9) + ... is 4 (1/2 - 1/3) + 4 (1/4 - 1/9) + ... = 2. So if n is sixteen or greater, you can't represent n in base 2&3. Note that we could fix the problem of representing any specific counting number (like sixteen) by enlarging our digit set, but this just kicks the can down the road: the same argument shows that there's going to be a counting number (roughly three times the maximum digit, I think) that can't be represented. Can anyone find a nice way to see that when the allowed digits are 0 through 4, you can't count past twelve in base 2&3? Jim Propp On Sun, Mar 19, 2017 at 1:22 PM, James Propp <jamespropp@gmail.com> wrote:
I don't think I did a good job of making this problem intriguing, so let me start again.
Here's how we write the first few counting numbers in a system I call "base one-or-two":
One = 1 Two = 2 Three = 10.2 Four = 11.2 Five = 12.2 Six = 21.12 Seven = 22.12 Eight = 111.1112 ...
The way you derive the representation of n from the representation of n-1 is by adding 1 in the units place (immediately to the left of the radix point) and then apply a strange sort of carrying to any digit that is 3 or greater: reduce the digit by 3, and then increase the digit to its left by 1 and the digit to its right by 2.
For example, to get eight from seven, write 23.12 -> 30.32 -> 102.32 -> 103.04 -> 110.24 -> 110.312 -> 111.032 -> 111.104 -> 111.1112.
It can be shown that the carrying procedure always terminates and the result that you get doesn't depend on the choices you make along the way. (You have choices when there's more than one digit that is 3 or greater.)
What's nice about the result that you get is that it gives n in BOTH unary and binary. E.g., 1*4 + 1*2 + 1*1 + 1*1/2 + 1*1/4 + 1*1/8 + 2*1/16 equals eight, and so does 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1. (You can think of evaluating the polynomial x^2+x+1+1/x+1/x^2+1/x^3+2/x^4 at both x=1 and x=2.)
So this algorithm gives a nice way to prove that for every positive integer n, there is a way to write n as a sum of n powers of 2 (where the exponent is allowed to be zero or negative), such that each power of 2 is used at most twice.
Part of what's going on is that when you're allowed to replace 3x^k by x^(k+1) + 2*x^(k-1), you're modding out the ring of polynomials by the polynomial x^2 - 3x + 2, which has 1 and 2 as roots.
It's fun to explore variants of this number system. Base one-or-three is similar, as is base one-or-m for any positive integer m you like.
In "base two-or-three", you mod out by x^2 - 5x + 6, which means that when you see a digit that is 5 or greater, you may reduce the digit by 5 and then increase the digit to its left by 1 and the digit to its right by 6. This will lead to an infinite cascade of further carries, but it can be shown that every digit position eventually stabilizes (though some care must be taken defining "eventually" in the correct way). It's fun to see what happens when you write the numbers one through twelve in base two-or-three.
When you get to thirteen, though, something unlucky happens: "an infinite amount of mass goes out to the right", and so you end up with an expansion whose binary value is thirteen but whose ternary value is only twelve.
My question is, for what positive integers n is there some way to represent n as a sum of powers of 2, each of which is used at most four times, that also represents n when each power of 2 is replaced by the corresponding power of 3? I believe that only the n's for which this can be done are 1 through 12.
Jim Propp
On Sat, Mar 18, 2017 at 1:00 AM, James Propp <jamespropp@gmail.com> wrote:
#1. Puzzle: Show that for every positive integer n less than thirteen, there exists a Laurent polynomial p(x) with coefficients in {0,1,2,3,4} satisfying p(1/2) = p(1/3) = n. (Hint: Use an iterative construction n -> n+1.)
#2. Problem: Show that this NOT the case for thirteen or any larger positive integer. (I don't know how to prove this.)
If #1 seems tricky, here's a simpler version: Show that for every positive integer n there exists a Laurent polynomial p(x) with coefficients in {0,1,2} satisfying p(1) = p(2) = n. Equivalently, show that every positive integer n can be written as the sum of n powers of 2, each of which may appear at most twice (where "power of 2" means "2^k for some k in Z").
Jim Propp