Your solution was exactly what I was looking for. As a participant in the new math experiment in California schools in the 1960s my reaction to doing arithmetic in base-5 was similar to Tom Lehrer's. A problem such as this one, I imagine, would have stimulated my interest because the binary representation enables you to do something you wouldn't have been able to do otherwise (unlike computing sums). Here's a slightly more general solution. We are interested in factoring 1/(1 - x) into two infinite Taylor series that have only 0/1 coefficients. We generate such a factorization given an arbitrary sequence of primes, p_0, p_1, p_2, ... . Start by defining f_0(x) = 1 s_0 = 1, and then evaluate the recursion f_(n+1)(x) = f_n(x) c_(p_n)(x^s_n) s_(n+1) = s_n p_n, where c_p(x) = 1+x+ ... x^(p-1) is the p-th cyclotomic polynomial. Your example was derived from the prime sequence 2,2,2, ... . Here's what you get for the sequence 2,3,2,3,2,3, ... f_1 = (1+x) f_2 = (1+x)(1+x^2+x^4) f_3 = (1+x)(1+x^2+x^4)(1+x^6) f_4 = (1+x)(1+x^2+x^4)(1+x^6)(1+x^12+x^24) etc. You can now form factorizations 1/(1-x) = g(x)h(x) as before, by assigning an infinite subset of the factors of f to g and the complement to h. Veit On Sep 28, 2010, at 11:36 PM, Tom Karzes wrote:
Cute problem. Here's the most obvious solution: Have one sequence contain all integers whose binary representation contains zero in all odd bit positions, and the other sequence contain all integers whose binary representation contains zero in all even bit positions:
a: 000000 000001 000100 000101 010000 010001 010100 010101 ... b: 000000 000010 001000 001010 100000 100010 101000 101010 ...
In decimal:
a: 0 1 4 5 16 17 20 21 ... b: 0 2 8 10 32 34 40 42 ...
For this solution, the values in one sequence are double the values in the other.
For any integer, there will clearly be a unique choice from sequence "a" and a unique choice from sequence "b".
I believe any partitioning of the bits will work, as long as each bit is allowed to be non-zero in one and only one sequence.
This easily generalizes to as many sequences as you want. For example, for three, you would simply partition the bits into three sequences.
Tom
Here's a puzzle I made up. In the 1960's it might have been used to get kids interested in "new math".
Find two infinite sequences of non-negative integers
a0, a1, a2, ... b0, b1, b2, ...
such that a0 = b0 = 0, and every non-negative integer can be uniquely expressed as the sum of two integers, one from each sequence.
Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun