Total number of times a number can be halved such that it remains a whole number

Question

I am a newbie and while studying prime factors came across this question:

How many times can you halve a number, such that it remains whole?

E.g. : 12 => 2 32 => 5

Here, the number can be very very large, i.e. number> 10^20. However, as long as there's a mathematical formula, it should not matter.

Also, what would be the answer if i had to divide by 3 or 5 or x, instead of 2?

I found this similar question, but could not understand the answer well. Can anyone help me with the answer to this? Thank you!

Hey welcome to MSE! Good luck with your studies. Check out common questions at your level too as well as the community guidelines. With that said, it is not too hard to check how many times a number can be halved. — Benjamin Wang, Jun 11 '20 at 08:23
Since the similar question you link to answers your question entirely, it would be better if you posted another question asking what exactly your doubts are about the answer in that question. — Matheus Andrade, Jun 11 '20 at 08:23
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. — José Carlos Santos, Jun 11 '20 at 08:39

score 1 · Answer 1 · answered Jun 11 '20 at 08:23

1

For primes, this number is called "valuation of $n$ with respect to $p$" , it is the exponent corresponding with $p$ in the prime factorization of $n$.

answered Jun 11 '20 at 08:23

Peter

84,454

score 1 · Answer 2 · answered Jun 11 '20 at 08:42

As said by Peter, this is the multiplicity of $2$ (more generally $p$) in the prime factorization of $n$. I didn't find a standard notation for this.

Anyway, from a computational point of view, establishing the full prime factorization would be overkill. I would proceed by dividing the number $n$ by $p$, then the quotient by $p^2$, then the quotient by $(p^2)^2$ and so on, until I get a nonzero remainder. Then perform a dichotomic search between the beforelast cumulated power of $p$ and the last one, until I find the largest power of $p$ that results in no remainder. The whole procedure would take like $O(\log n)$ divisions.

score 0 · Answer 3 · answered Jun 11 '20 at 13:33

This is not an answer, but maybe it gives some insight.

I wrote and ran some Mathematica code:

k = 2;
ParallelTable[{n, 
  Length[NestWhileList[Floor[#/k] &, n, 
     Length[IntegerDigits[Floor[#]]] > 1 &]] - 1}, {n, 10^(20), 
  50 + 10^(20)}]

Now, in the code, I compute the number of divisions it took to result into a one-digit number. In order to do this, I take two numbers $n\in\mathbb{N}$ and $k\in\mathbb{N}$ and I divide the number $n$ by the number $k$, when the resulting number $n/k\in\mathbb{N}$ we can divide by $k$ again, but when $n/k\in\mathbb{Q}$ I take the floor-function of that fraction.

Running the code for $10^{20}\le n\le10^{20}+50$ and $k=2$ gave me the following table:

{{100000000000000000000, 64}, {100000000000000000001, 
  64}, {100000000000000000002, 64}, {100000000000000000003, 
  64}, {100000000000000000004, 64}, {100000000000000000005, 
  64}, {100000000000000000006, 64}, {100000000000000000007, 
  64}, {100000000000000000008, 64}, {100000000000000000009, 
  64}, {100000000000000000010, 64}, {100000000000000000011, 
  64}, {100000000000000000012, 64}, {100000000000000000013, 
  64}, {100000000000000000014, 64}, {100000000000000000015, 
  64}, {100000000000000000016, 64}, {100000000000000000017, 
  64}, {100000000000000000018, 64}, {100000000000000000019, 
  64}, {100000000000000000020, 64}, {100000000000000000021, 
  64}, {100000000000000000022, 64}, {100000000000000000023, 
  64}, {100000000000000000024, 64}, {100000000000000000025, 
  64}, {100000000000000000026, 64}, {100000000000000000027, 
  64}, {100000000000000000028, 64}, {100000000000000000029, 
  64}, {100000000000000000030, 64}, {100000000000000000031, 
  64}, {100000000000000000032, 64}, {100000000000000000033, 
  64}, {100000000000000000034, 64}, {100000000000000000035, 
  64}, {100000000000000000036, 64}, {100000000000000000037, 
  64}, {100000000000000000038, 64}, {100000000000000000039, 
  64}, {100000000000000000040, 64}, {100000000000000000041, 
  64}, {100000000000000000042, 64}, {100000000000000000043, 
  64}, {100000000000000000044, 64}, {100000000000000000045, 
  64}, {100000000000000000046, 64}, {100000000000000000047, 
  64}, {100000000000000000048, 64}, {100000000000000000049, 
  64}, {100000000000000000050, 64}}

Total number of times a number can be halved such that it remains a whole number

3 Answers3