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