Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 4 down vote favorite

My background is procedural programming, so I find this construction quite natural. Is there a way to get rid of the While? 

gd[n_, k_] := Block[{d = k + 1}, While[0 != Mod[n, --d]]; d]
gd[n_, d_List] := 
      Block[{j = Length[d] + 1}, While[0 != Mod[n, d[[--j]]]]; d[[j]]]  

k = 4; n = 25;
gd[n, k]
gd[n, Range[1, k]]
d = Join[{1}, Table[Prime[j], {j, 1, PrimePi[k]}]];
gd[n, d]

My trial division requires the greatest divisor $\leq$ the square root. The $n$ mod $1$ is the terminating step. Whatever the final format, I will need to describe it for a math paper.

Edit The revised functions as recursions:

gd[n_, k_] := If[Mod[n, k] == 0, k, gd[n, k - 1]]
fd[n_, d_List] := If[Mod[n, d[[1]]] == 0, d[[1]], fd[n, Delete[d, 1]]]

Edit The second function as it will be described in my paper:

$$f(n,D)\text{:=} \begin{array}{ll} \lbrace & \begin{array}{ll} n \bmod d_{1}=0 & d_{1} \\ n \bmod d_{1}\neq 0 & f(n,\text{Delete}(D,1)) \\ \end{array} \\ \end{array} $$

share|improve this question
Do you want the greatest proper divisor or the greatest prime divisor? If the former, check for primes beginning at 2 and take the cofactor of the first one that divides your number. If the latter, start at sqrt(n) and work downward, again checking only primes. Either way, precompute your primes and store their differences; that gives you the increment/decrement to use as you go up/down the list. – Daniel Lichtblau Dec 18 '12 at 15:15
@DanielLichtblau, I put the new functions in the OP. The second one allows me to use a list of divisors, which can be primes or all numbers below the square root. – Fred Kline Dec 19 '12 at 0:35
A bit long for a comment, but...your fd[] will require both deep recursion/iteration and also has quadratic complexity. Much more efficient to use Map or Scan. I show by way of example. In[658]:= $IterationLimit = Infinity; fd[n_, d_List] := If[Mod[n, d[[1]]] == 0, d[[1]], fd[n, Delete[d, 1]]] In[659]:= e1 = Prime[8000]*Prime[9000]^2; rng = Prime[Range[20000, 1, -1]]; In[661]:= Timing[fd[e1, rng]] Out[661]= {4.630000, 93179} In[662]:= fd2[n_, d_List] := Scan[(If[Mod[n, #] == 0, Return[#]]) &, d] In[663]:= Timing[fd2[e1, rng]] Out[663]= {0.010000, 93179} – Daniel Lichtblau Dec 19 '12 at 15:44
@Daniel I often see unformatted code in your comments. Are you aware that you can wrap the code in backticks to get code? – Mr.Wizard♦ Dec 20 '12 at 12:24

2 Answers

up vote 9 down vote accepted 
     gd[n_, k_] := If[Mod[n, k] == 0, k, gd[n, k - 1]]
share|improve this answer
Very nice! Should be easy to explain in the paper. – Fred Kline Dec 18 '12 at 2:44
up vote 6 down vote

Here's a functional way to do the first definition for gd:

f[n_, k_] := NestWhile[# - 1 &, k, Mod[n, #] != 0 &]

I'll leave the second one to you. In general, whenever you encounter repeated application of a particular function, think of Nest (use Fold, for more general cases). Combined with a While loop, you need NestWhile, which is what I used above.

Test this with your function for a bunch of test cases:

With[{list = RandomInteger[{1, 100}, {100, 2}]}, gd @@@ list == f @@@ list]
(* True *)
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.