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
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
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
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations? a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation. Doesn't that work just as well, with no need for binary? Andy
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
On Wed, Sep 29, 2010 at 10:23 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
No: 5 can be written as 2+3 or 1+4. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Actually, the uniqueness requirement was one integer from *each* sequence, so 5 is uniquely expressed as 0+5 ----- Message from metaweta@gmail.com --------- Date: Wed, 29 Sep 2010 11:07:20 -0700 From: Mike Stay <metaweta@gmail.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] new math To: math-fun <math-fun@mailman.xmission.com>
On Wed, Sep 29, 2010 at 10:23 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
No: 5 can be written as 2+3 or 1+4. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End message from metaweta@gmail.com -----
Another simple decimal pair: a is all numbers composed of 0's and 1's. b is all numbers composed of even digits. -tom On Wed, Sep 29, 2010 at 12:03 PM, <mbgreen@cis.upenn.edu> wrote:
Actually, the uniqueness requirement was one integer from *each* sequence, so 5 is uniquely expressed as 0+5 ----- Message from metaweta@gmail.com --------- Date: Wed, 29 Sep 2010 11:07:20 -0700 From: Mike Stay <metaweta@gmail.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] new math To: math-fun <math-fun@mailman.xmission.com>
On Wed, Sep 29, 2010 at 10:23 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
No: 5 can be written as 2+3 or 1+4. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End message from metaweta@gmail.com -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
Uggh. Never mind. On Wed, Sep 29, 2010 at 1:21 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Another simple decimal pair:
a is all numbers composed of 0's and 1's. b is all numbers composed of even digits.
-tom
On Wed, Sep 29, 2010 at 12:03 PM, <mbgreen@cis.upenn.edu> wrote:
Actually, the uniqueness requirement was one integer from *each* sequence, so 5 is uniquely expressed as 0+5 ----- Message from metaweta@gmail.com --------- Date: Wed, 29 Sep 2010 11:07:20 -0700 From: Mike Stay <metaweta@gmail.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] new math To: math-fun <math-fun@mailman.xmission.com>
On Wed, Sep 29, 2010 at 10:23 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
No: 5 can be written as 2+3 or 1+4. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End message from metaweta@gmail.com -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/
-- Check out Golly at http://golly.sf.net/
You're absolutely right! I didn't express myself very well. The "standard" solutions to this puzzle will seem mysterious when seen as just sequences of integers 0,1,4,5, ... 0,2,8,10, ... Only when rendered in some representation, in this case base-2, does the scheme emerge. By the way, a solution to this puzzle gives a bijection between rationals and integers and would have fit nicely in the set theory chapter of my new math book. On Sep 29, 2010, at 1:23 PM, Andy Latto wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
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).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
Andy
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
="Veit Elser" <ve10@cornell.edu> By the way, a solution to this puzzle gives a bijection between rationals and integers and would have fit nicely in the set theory chapter of my new math book.
Or integers and any pairs (j,k), for instance extensions like j + k sqrt(2). Moreover, as mentioned in a comment to A000695, via repeated application the Moser-de Bruijn sequence gives a fun bijection between lists of integers and integers: f([L1,L2,L3...]) := a(L1)+2*a(f([L2,L3...])), with f([]) <--> 0. This gives many pleasant single-integer encodings. For example partitions, the exponents in prime factorizations, finite continued fractions, etc. --------- Programming puzzle: compute Y=a(n+1) efficiently from X=a(n). Martian solution: Y = (X + 1/3) & -2/3 where & denotes bitwise AND. (Of course this only works on computers where, just as -1 is represented in two's-complement by the infinite dyadic ...1111111111, -2/3 is ...1010101010 and thus 1/3 is ...1010101011.)
Er, do you know of a nice bijection between rationals and pairs of integers? --Rich ----- Quoting Marc LeBrun <mlb@well.com>:
="Veit Elser" <ve10@cornell.edu> By the way, a solution to this puzzle gives a bijection between rationals and integers and would have fit nicely in the set theory chapter of my new math book.
Or integers and any pairs (j,k), for instance extensions like j + k sqrt(2).
Moreover, as mentioned in a comment to A000695, via repeated application the Moser-de Bruijn sequence gives a fun bijection between lists of integers and integers: f([L1,L2,L3...]) := a(L1)+2*a(f([L2,L3...])), with f([]) <--> 0.
This gives many pleasant single-integer encodings. For example partitions, the exponents in prime factorizations, finite continued fractions, etc.
---------
Programming puzzle: compute Y=a(n+1) efficiently from X=a(n).
Martian solution:
Y = (X + 1/3) & -2/3
where & denotes bitwise AND.
(Of course this only works on computers where, just as -1 is represented in two's-complement by the infinite dyadic ...1111111111, -2/3 is ...1010101010 and thus 1/3 is ...1010101011.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
="Veit Elser" <ve10@cornell.edu>
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
One of my favorites, the Moser-de Bruijn sequence, 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257,... http://www.research.att.com/~njas/sequences/A000695, for A, and twice that for B, satisfy this. Of course countless variants can be derived from this. Perhaps I was traumatized by early exposure to "new math"?
participants (8)
-
Andy Latto -
Marc LeBrun -
mbgreen＠cis.upenn.edu -
Mike Stay -
rcs＠xmission.com -
Tom Karzes -
Tom Rokicki -
Veit Elser