1
$\begingroup$

Assume that there is a set of ordered integers initially containing number $1$ to a given $n$. At each step, the lowest number in the set is removed, if the number was odd, then we go to the next step and if it was even, half of that number is inserted into the set and the cycle repeats until the set is empty.

My question is, how many steps does it take for a given number $n$ to finish the whole set?

I think it should be something the form of $2k - x$ where $x$ itself is likely a complex expression but I just can't seem to figure it out. Any help would be appreciated. (I got that from trial and error, by the way, no logic or proof behind it, I know that the answer is $\lfloor \frac{n}{2} \rfloor$+"The number of times each even number can be divided by 2", but I just can't find a closed formula)

$\endgroup$
  • $\begingroup$ It will have to do with the number of numbers in the original set that fall into each of the following categories: $(2k+1),(2k+1)2, (2k+1)2^2,(2k+1)2^3,\dots$. Numbers from the first category are removed in a single step. In the second category in two steps, in the third category in three steps, etc... $\endgroup$ – JMoravitz Jan 26 '18 at 21:28
  • $\begingroup$ @JMoravitz Exactly! I got to that and then I couldn't get any further. $\endgroup$ – Arian Tashakkor Jan 26 '18 at 21:35
  • $\begingroup$ Experimentally, this seems to be oeis.org/A005187 . $\endgroup$ – Jair Taylor Jan 26 '18 at 21:40
  • $\begingroup$ @JairTaylor It does check out with the numbers I generated with my program. Does this suggest there doesn't exist a closed formula? $\endgroup$ – Arian Tashakkor Jan 26 '18 at 21:44
  • $\begingroup$ @ArianTashakkor Not necessarily, OEIS doesn't know everything. $\endgroup$ – Jair Taylor Jan 26 '18 at 22:15
2
$\begingroup$

As in this algorithm, the actual order of the set isn't important, we can assign every $n\in\mathbb{N}$ the number of steps it takes till it's sorted out, which is namely how many times you'll have to divide by two till it's odd.

If we use prime factorization, that means if $z$ takes k steps till it's sorted out, it's prime factorization is $z = 2^{k-1} \cdot\, ...$

Now, we know the following:
Every second number has $2^0$ in its prime factorization (every odd number).
Every forth number has $2^1$ in its prime factorization.
Every eigth number has $2^2$ in its prime factorization.
...

So, for a given set $\{1,...,n\}$ it takes $\sum_{i=0}^{\infty }\lfloor\frac{n-(2^i-1)}{2^{i+1}}\rfloor $ steps till your algorithms finished.
Here, $2^i-1$ is here how long we'll have to count from 1 till we reach the first number that has $2^i$ in its prime factorization
(e.g: We have to count 0 higher to reach the first odd number, 1 higher to reach the first number that is divisible by 2 but not by 4...)

You can cut off the sum as soon as the divisor gets greater than the divident, so as rough approximation $log_2(n)$ works out. With that we get: $$\sum_{i=0}^{log_2(n)}\lfloor\frac{n-(2^i-1)}{2^{i+1}}\rfloor $$


Another way to look at the problem is by keeping it a set. If $M$ is a set and $k\in\mathbb{N}$, let us define $$M\cdot k := \{k\cdot m \mid m\in M\}$$ E.g. $\{1,2,3\}\cdot 2 = \{2,4,6\}$

Now we look at how our set looks like if we process it $i$ times, with our procss being:
For every number of the set, if the number is even, half it, if it is odd, remove it.

$i=0$ - The algorithm hasn't run yet, our set is the input set $\{1,..,n\}$.

$i=1$ - Only the even numbers are left $\{2,4,6,..,2\cdot\lfloor\frac{n}{2}\rfloor\} = 2\cdot \{1,2,3,..,\lfloor\frac{n}{2}\rfloor\}$

$i=2$ - Only the numbers divisble by four are left $\{4,8,12,..,4\cdot\lfloor\frac{n}{4}\rfloor\} = 4\cdot \{1,2,3,..,\lfloor\frac{n}{4}\rfloor\}$

...

$i=k$ - Only the numbers divisble by $2^k$ are left $\{2^k,2\cdot 2^k, 3\cdot 2^k, ..., 2^k\cdot\lfloor\frac{n}{2^k}\rfloor\} = 2^k\cdot \{1,2,3,..,\lfloor\frac{n}{2^k}\rfloor\}$

The number of operations our algorithm takes is now simply the sum of the numbers of each set in this chain. So, we get: $$\sum_{i=0}^{\infty} \lfloor\frac{n}{2^i}\rfloor = \sum_{i=0}^{log_2(n)} \lfloor\frac{n}{2^i}\rfloor$$


Finally, we can let this sum look a little more refined:

Let $\{1,..,n\}$ be our set and $n = c_0\cdot 2^0 + c_1\cdot 2^1 +c_2\cdot 2^2+... + c_k\cdot 2^k$ its binary representation. Then the steps the algorithm needs for $\{1,..,n\}$ are equal to running our algorithm on the following sets:

$\{1,2,...,c_i\cdot 2^i\} \text{ where } i\in\mathbb{N}, i\leq k, c_i = 1 $

This let's us erase the $\lfloor \rfloor$-s in our sum, as for every step of the algorithm $ \lfloor\frac{c_i\cdot 2^i}{2^j}\rfloor\}$ is a whole number for $j\leq i$, and for $j>i$, the set is empty.

So, if $c_0\cdot 2^0 + c_1\cdot 2^1 +c_2\cdot 2^2+... + c_k\cdot 2^k$ is the binary represantation of our number, the steps our algorithm needs are: $$\sum_{j=0}^k c_j\cdot\sum_{i=0}^j \frac{2^j}{2^i} = \sum_{j=0}^k c_j\cdot\sum_{i=0}^j 2^{j-i} = \sum_{j=0}^k c_j\cdot (2^{j+1}-1) $$

$\endgroup$
0
$\begingroup$

Let $s(n)$ be the number steps required.

Each number $k$ is acted on $1+\nu_2(k)$ times before being discarded completely, where $\nu_2(k)$ is the highest power of $2$ that divides $k$. For example, $\nu_2(24) =3 $ because $2^3$ divides $24$ but $2^4$ does not.

So $s(n) = \sum_1^n \left(1+\nu_2(i)\right) = n+\sum_1^n\nu_2(i)$

Now $\sum_1^n\nu_2(i)$ is the count of even numbers up to $n$, plus the count of numbers divisible by $4$, plus the count of numbers divisible by $8$, etc. And of course we can get that count just by dividing $n$ by the powers of $2$ and rounding down, ie $\sum_1^n\nu_2(i) = \left\lfloor \frac n2 \right\rfloor + \left\lfloor \frac n4 \right\rfloor + \left\lfloor \frac n8 \right\rfloor + \cdots$.

Where $n=2^k$, this is actually equal to $n{-}1$, and for $n=2^k-1$ of course it is $n{-}k$. So $s(n) = 2n-e$, where $e$ depends on where the number sits between powers of $2$.

A little lateral thinking uncovers that $e$ is actually the digit sum of $n$ in binary.

$\endgroup$

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.