Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I was curious about the following little problem. Suppose $n \in \mathbb{N}$ is some large number and $p$ is a (possibly large) prime, and I want to update $n$ according to

$$n := \begin{cases} n/p, & (n,p) = p; \\ n, & (n,p) = 1.\end{cases}$$

In other words, I want to divide by $p$ if $p$ divides $n$, and not divide by $p$ if $p$ does not divide $n$. Also, I would like to know if a division took place. Of course I could implement this with something like

If[Divisible[n,p], 
  n = Quotient[n,p]; 
  Print["A division took place!"];
];

However, this feels inefficient, since to check divisibility the machine may have already computed $n/p$. Would there be a more efficient way to do this in Mathematica? i.e. A way that uses only $1$ division if $p$ divides $n$ and at most $1$ division if $p$ does not divide $n$?

Also, I'm curious which Mathematica functions would be most suited for these purposes in general. Is there any difference in performance between e.g. Divisible[n,p], Mod[n,p] == 0, IntegerQ[n/p], FractionalPart[n/p] == 0, CoprimeQ[n,p], GCD[n,p] == p?

Thanks in advance.

share|improve this question
    
Divisible seems to be faster than actually doing the division in my computer. But even if it wasn't, as long as it's slightly faster to check for divisibility than doing the division, saving the result and checking if the remainder was 0, whether this is convenient or not depends on how often you will actually put numbers that divide each other... If they are both random big numbers, I'm guessing not often, so you probably already have an efficient solution (without resorting to compiling) –  Rojo Mar 18 '12 at 21:56
3  
QuotientRemainder might be useful. –  Szabolcs Mar 18 '12 at 22:08
2  
If you plan to repeat this until you exhaust powers of p, go with IntegerExponent. –  Daniel Lichtblau Mar 19 '12 at 1:12

1 Answer 1

up vote 8 down vote accepted

To stay with your example:

n = 12; p = 4;
If[
   #2 == 0, n= #1;
   Print["A division took place!"]
   ] & @@ QuotientRemainder[n, p]

A division took place!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.