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$?


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


I've dropped the "no induction" requirement.

  • $\begingroup$ I've included more advanced tags in case the proofs require more advanced math. $\endgroup$ – Matt Groff Apr 11 '13 at 22:26
  • 1
    $\begingroup$ Isn't this just the fact that every number is of the form $2^n M$, where $n \ge 0$ and $M$ odd? $\endgroup$ – Aryabhata Apr 11 '13 at 22:58
  • $\begingroup$ @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. $\endgroup$ – Matt Groff Apr 11 '13 at 23:33
  • $\begingroup$ I just added an answer. Is that enough? $\endgroup$ – Aryabhata Apr 11 '13 at 23:36
  • $\begingroup$ @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! $\endgroup$ – Matt Groff Apr 11 '13 at 23:38

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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