Author 
Topic: New Number System? (Read 1262 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


New Number System?
« on: Jul 28^{th}, 2014, 10:47pm » 
Quote Modify

Does there exist a set S of nonnegative integers, such that every nonnegative integer is represented as s + 2t in a unique way (s, t are of course elements of S).


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: New Number System?
« Reply #1 on: Jul 29^{th}, 2014, 12:53am » 
Quote Modify

Yes, {0} Edit: oh wait, you mean every nonnegative integer, not just the ones in S... Apologies.

« Last Edit: Jul 29^{th}, 2014, 12:54am by dudiobugtron » 
IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: New Number System?
« Reply #2 on: Jul 29^{th}, 2014, 1:29am » 
Quote Modify

New answer: No. Outline of proof by construction: We can construct the set by finding (in size order) each integer we can't currently represent from members of S, and adding them to S. So, the set must containt 0 (0+2*0) and 1 (1+2*0), after which we can represent 2 (0+2*1) and 3 (1+2*1). We then need to add 4 and 5, which are otherwise unrepresentable, so the set is {0,1,4,5,...}. With these we can represent all the numbers up to 15 (5+2*5), and so need to add 16 and 17 to the set. Because we had such a big gap, we also need to add 20, and 21. We're now safe again up to 36 and 37 which need to be added. So the set is now {0,1,4,5,16,17,20,21,36,37,...}. But this is where we get our contradiction; as 44 can be represented as 36+2*4, or 4+2*20. Thus, unless I have made an error in my construction (you're welcome to construct it for yourself to check), no such set S exists. There is undoubtedly a more elegant way of proving it, though!


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: New Number System?
« Reply #3 on: Jul 29^{th}, 2014, 1:47am » 
Quote Modify

on Jul 29^{th}, 2014, 1:29am, dudiobugtron wrote:We're now safe again up to 36 and 37 which need to be added. 



IP Logged 



gotit
Uberpuzzler
Gender:
Posts: 804


Re: New Number System?
« Reply #4 on: Jul 29^{th}, 2014, 6:59am » 
Quote Modify

Once you add 16, you need not add 36 (4 + 16 * 2)


IP Logged 
All signatures are false.



rmsgrey
Uberpuzzler
Gender:
Posts: 2866


Re: New Number System?
« Reply #5 on: Jul 29^{th}, 2014, 7:42am » 
Quote Modify

hidden:  {0, 1, 4, 5, 16, 17, 20, 21} gives you [0,63].  It's easier to see what's going on if you use binary: hidden:  {0, 1, 100, 101, 10000, 10001, 10100, 10101, ...}  it's immediately obvious that S is all the numbers with unset even bits  and any number can be broken down uniquely into its odd bits and its even bits  the odd bits giving a number in S, and the even bits twice a number in S.  So the set S does exist .


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: New Number System?
« Reply #6 on: Jul 29^{th}, 2014, 4:01pm » 
Quote Modify

on Jul 29^{th}, 2014, 6:59am, gotit wrote:Once you add 16, you need not add 36 (4 + 16 * 2) 
 Ah, thanks for spotting that!


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: New Number System?
« Reply #7 on: Jul 29^{th}, 2014, 10:47pm » 
Quote Modify

Nice. Now, when the question was answered in affirmative, let's ask a more general question: For which natural numbers n, m, there exists a set S(n, m) of nonnegative integers, such that every nonnegative integer is represented as ns + mt in a unique way (s, t are elements of S(n, m))?


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2866


Re: New Number System?
« Reply #8 on: Jul 30^{th}, 2014, 6:32am » 
Quote Modify

From my earlier answer, if the numbers are: 1, b>1 then S(1, b) exists and is all numbers of form Sum_{i}{a_{i}b^{2i}} with a_{i} in [0,b) for all i For S to exist, then it must be possible to make 1, which can only be 1+0, which can only be 1*1 + m*0 (or 1*1 + 0*t or some equivalent with n, m swapped) so for s to exist, at least one of n, m must be 1 So, depending on which flavour of natural numbers we're using (including or excluding 0) there are only 1 or 2 cases left: S(1,1) does not exist  if you try constructing S, to make 0 you need to include 0, and to make 1, you need to include 1, but then both s=0, t=1 and s=1, t=0 give 1. If you don't regard that as different, then you can't make 3 without including 2 or 3 in S; including 2 gives you multiple ways to make 2, while including 3 means you then can't make 5 without 4 (giving multiple ways to make 4) or 5 (giving multiple ways to make 6) S(0,1) does not exist  S needs to have an infinite number of members to make enough combinations for the infinite number of numbers, but that means that there's an infinite number of ways of making 0 (0*s+1*0 for any s).


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: New Number System?
« Reply #9 on: Jul 31^{st}, 2014, 8:39am » 
Quote Modify

Nothing to add, rmsgrey. Excellent analysis.


IP Logged 



