Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's given that we have a set of all natural numbers from 1 to $n$. If we decide to group the numbers into sets according to the property that a set has the numbers: $${x, 3x, 5x, \dots, (2k+1)x, \dots}$$

Can we prove that we only need to require the sets that start with $x=2^m$ (for $m$ a positive integer or zero) to contain all the numbers from 1 to $n$?

THE SETS

In other words, the first set is: $${1, 3\cdot 1 = 3, 5\cdot 1=5, \dots}$$

The second set is: $${2, 3\cdot 2 = 6, 5\cdot 2= 10, \dots}$$

The third set is: $${4, 3\cdot 4 = 12, 5\cdot 4 = 20,\dots}$$

The fourth set is: $${8, 3\cdot 8 = 24, 5\cdot 8=40,\dots}$$

And so on...

EDIT

I've dropped the "no induction" requirement.

share|improve this question
    
I've included more advanced tags in case the proofs require more advanced math. –  Matt Groff Apr 11 '13 at 22:26
1  
Isn't this just the fact that every number is of the form $2^n M$, where $n \ge 0$ and $M$ odd? –  Aryabhata Apr 11 '13 at 22:58
    
@Aryabhata: I didn't think of that... Could you please write up a more formal proof? I would really appreciate it! It's for an algorithm I'm working on, and I asked this question because I'm in search of a proof for the algorithm, as I plan on writing a paper on it. I'm not sure how to prove that $M$ is unique in your $2^n M$ factorization. –  Matt Groff Apr 11 '13 at 23:33
    
I just added an answer. Is that enough? –  Aryabhata Apr 11 '13 at 23:36
    
@Aryabhata: Is there any way to prove that $M$ is unique? Sorry to fuss, but I'm really hoping that this may be a big breakthrough, and thoroughness will be expected. By the way, thanks! –  Matt Groff Apr 11 '13 at 23:38

2 Answers 2

Unique factorization, and the fact that $2$ is the only even prime, tells us that every positive integer is of the form

$$2^n M$$

where $n$ and $M$ are unique with $M$ odd.

Thus it is enough to start with powers of $2$ (including $2^0$).

share|improve this answer
    
Thanks for the idea! –  Matt Groff Apr 12 '13 at 0:28

You can argue by contradiction I guess. Suppose your starting set does not contain $2^m$ for some $m\in\mathbb{N}$. Then, you have no hope in getting $2^m$ (as even though you might have $(\mbox{odd number}) \times 2^n$ for some $n<m$, odd multiples of this number will not give you $2^m$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.