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!

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

Answer 2

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.

Answer 3

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