8
$\begingroup$

Is there an formula stating the number of times you would have to halve a number to reduce it to some value less than or equal to $1$?

For example, for $6$ it takes three halvings: $6/2=3$, $\ 3/2=1.5$, $\ 1.5/2=0.75$.

Also, is there a representation using the floor function in conjunction?

For example, for $6$ it takes two halvings if we round each intermediate result down: $\lfloor 6/2\rfloor=3$, $\ \lfloor 3/2\rfloor=1$.

  • 1
    How does this question relate to relational algebra?2012-04-08
  • 1
    it's a fair question for cs, but heavy overlap with math2012-04-08
  • 0
    how would your second example behave starting with 7? would it be $\lfloor 7/2 \rfloor = 3, \lfloor 3/2 \rfloor = 1$ ? If so, then I'm not aware of any standard notation... possibly use "iterated" notation similar to what we use for iterated logarithm.2012-04-08
  • 0
    although, even if there isn't a notation that means perform the operation with a floor in it every time, that rounding down might not add up, in which case the answer would be the same whether you take the floor each time, or only at the end, and so it is equivalent to $\lfloor \log_2 n \rfloor$, as @sepp2k said.2012-04-08
  • 2
    This should be on math.se2012-04-08
  • 1
    Voted to close as off-topic. While important in a sense, the question is middle school mathematics material, not computer science.2012-04-08
  • 4
    This is purely a math question, with no link to Computer Science. That Discrete Mathematics is often important for Computer Science does not mean every Discrete Mathematics question is on-topic here. Voted to close as off-topic.2012-04-08

2 Answers 2