3

How many times can I divide a number by another until I get a fractional number.

For e.g. I can divide 100 by 2 two times before I get a fractional number i.e. 12.5. Is there any formula that given a number N and another number x I can get the no. of times x will divide N before we get a fractional number.

EDIT :- It is given that x is a prime number and comes at least once in the prime factorization of N. We are also given all the prime factors of N but not their powers.

EDIT :- I think the only solution will be to repeatedly divide the N by x and check if it is fractional or not as told by Arthur

Chief VOLDEMORT
  • 151
  • 1
  • 1
  • 7

3 Answers3

1

Any natural number admits a prime factorization (which is unique up to the order of the factors). You can divide $n$ by a prime $p$ as many times as this prime appears in this factorization (as many times as the corresponding power). Example: $100=2^2 \cdot 5^2$. It follows that we can divide $100$ twice by $2$ or twice by $5$ before getting to a fractional number. Unfortunately there is no formula to find the prime factorization of a number.

Mathematician 42
  • 12,591
1

There isn't a formula, per se, since this depends entirely on the prime factorisations of $N$ and $x$, and we don't have a good way to get those.

That being said, if we have the prime factorisations: $$ N = 2^{N_2}\cdot3^{N_3}\cdot5^{N_5}\cdots\\ x = 2^{x_2}\cdot3^{x_3}\cdot5^{x_5}\cdots $$ (where most of the exponents $N_p$ and $x_p$ are $0$), then you can divide $N$ by $x$ the following number of times, without getting decimals: $$ \min\left\{\left\lfloor\left.\frac{N_i}{x_i}\right\rfloor\,\,\right|\,\,x_i\neq 0\right\} $$ In other words, take all the exponents $x_i$ which aren't $0$, divide the corresponding $N_i$ by those $x_i$, take away the decimal part, so you're only left with integers, then take the smallest of those integers.

For instance, $100 = 2^2\cdot 5^2$ and $2 = 2^1$. So we take all the exponents of the latter (which is $1$), take the corresponding exponents from the former (which is $2$), calculate $\frac21 = 2$, strip away the decimals, and we see that we may divide $100$ by $2$ two times without getting decimals.

For a more involved example, where it's easier to see which part corresponds to what, let's look at dividing $360 = 2^3\cdot 3^2\cdot 5^1$ by $12 = 2^2\cdot 3^1$. The non-zero exponents of $12$ are $2$ and $1$ (with bases $2$ and $3$, repsectively). The corresponding exponents of $360$ are $3$ and $2$, respectively.

So, we calculate $\frac32 = 1.5$ and $\frac21 = 2$, strip away all decimals to get $1$ and $2$, take the smallest one of these (which is $1$), and we see that we can divide $360$ by $12$ once without getting decimals (we get $30$), but not twice (we would get $2.5$).

Responding to the edit: If we know that $x$ is prime, then that makes the above a lot easier: only one of the exponents of $x$ is non-zero (namely $x_x$), and that is equal to $1$, so the answer is actually just $N_x$. However, if we don't have $N_x$, then really, the easiest (and as far as I know only) way to get it is to divide by $x$ repeatedly and check.

Arthur
  • 199,419
  • Thanks for the solution. I know the prime factors of N but not their powers. Can it solved without using the powers? – Chief VOLDEMORT Jan 03 '18 at 08:24
  • @ChiefVOLDEMORT If you don't have $N_x$, then, as far as I know, the only way to get it is just to divide by $x$ repeatedly and see how many times you can do it without getting any decimals. You wanted an alternative way to tell what $N_x$ is given just $N$ and $x$, and I don't know that there is one. – Arthur Jan 03 '18 at 08:26
0

One 'closed-form', but computationally inefficient, formula for the number of times the integer N is divisible by the nonzero integer x (before becoming fractional) is,

$$\sum_{i=1}^{\infty}\underbrace{\lim_{j\to\infty}\cos\left(\frac{\pi N}{x^{i}}\right)^{2j}}_{\text{$1$ if $x^i|N$, else $0$}}$$

The numbers that are divisible by $x$ are $\ldots,-x,0,x,2x,3x,\ldots$ so the indicator function for divisibility by $x$ is an $x$-periodic function equal to $1$ at the multiples of $x$ and $0$ everywhere else. That periodic indicator function can be constructed using the sinusoid $\cos(\pi t)^2$, which is equal to $1$ at the integers but otherwise takes values in $[0,1)$. Taking the limit, $\lim_{j\to\infty}\cos(\pi t)^{2j}$ gives $1$ or $0$ exactly and is therefore the indicator that $t$ is an integer. When rescaled, it can indicate that $t$ is a particular multiple. Therefore, $\lim_{j\to\infty}\cos\left(\frac{\pi N}{x^i}\right)^{2j}$ is the indicator that $x^i$ divides $N$. Summing this over all positive integer exponents $i$ counts the powers of $x$ that $N$ is a multiple of, that is, how many times $x$ divides $N$.

A similar technique can be used to construct the Dirichlet function as a double pointwise limit.

Incidentally, at $N=0$, the formula becomes $\sum 1 = \infty$ since $0$ is divisible infinitely many times by any nonzero $x$.

Jam
  • 10,325