# Can we prove that we can “sieve” numbers in this way?

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.

• I've included more advanced tags in case the proofs require more advanced math. – Matt Groff Apr 11 '13 at 22:26
• 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

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$).

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$).