1
$\begingroup$

I'm new at Mathematica. I need to find all the reminders of a division between two integers - just like column division - and stop until I obtain a reminder equal to one of those already found. For istance: 37/22

In[17]:= Mod[37, 22]

Out[17]= 15

In[20]:= Mod[150, 22]

Out[20]= 18

In[21]:= Mod[180, 22]

Out[21]= 4

In[22]:= Mod[40, 22]

Out[22]= 18

then it stops. I learnt how to use If and Do, but I guess it's not enough and there're better functions to perform this job. Thank you

$\endgroup$
  • $\begingroup$ reference.wolfram.com/language/ref/ContinuedFraction.html ? $\endgroup$ – alancalvitti Nov 25 '14 at 17:04
  • 1
    $\begingroup$ This will need a bit of cleaning. `FixedPointList[QuotientRemainder @@ # &, {773240, 68423}]' $\endgroup$ – Daniel Lichtblau Nov 25 '14 at 17:32
  • $\begingroup$ This is better: In[296]:= NestWhileList[ QuotientRemainder @@ # &, {773240, 68423}, #[[1]] > 0 &] Out[296]= {{773240, 68423}, {11, 20587}, {0, 11}} $\endgroup$ – Daniel Lichtblau Nov 25 '14 at 20:01
2
$\begingroup$

First, an auxiliary function that mimics what your division example, i.e. multiplies the dividend by 10 whenever it is smaller than the divisor, and returns only the remainder.

columnDivRem[a_, b_] /; a < b := QuotientRemainder[10 a, b][[2]]
columnDivRem[a_, b_] := QuotientRemainder[a, b][[2]]

Then the "main" function, without If's or Do's, that repeatedly applies this function to it's own results until one of the remainders is a duplicate, or a zero remainder is found.

columnDiv = Function[{div1, div2},
  NestWhileList[columnDivRem[#, div2] &, 
   div1, ({##} === DeleteDuplicates@{##} && FreeQ[{##}, 0]) &, 
  All, 1000]]

columnDiv[37, 22]
(* {37, 15, 18, 4, 18} *)

NestWhileList's last parameter prevents the function from executing indefinitely, such as in @Daniel Lichtblau`s evil example, by limiting the number of executions to 1000:

columnDiv[773240, 68423]    
{773240,20587,601,6010,60100,53616,57199,<<987>>,67534,59533,47946,499,4990,49900,20039}

Fixed-point version, inspired by @Daniel Lichtblau

columnDivFixed = Function[{div1, div2}, 
  FixedPoint[Append[#, columnDivRem[Last@#, div2]] &, {div1}, 1000,
    SameTest -> (#1 === DeleteDuplicates@#2 || Last@#2 == 0 &)]];
$\endgroup$
  • $\begingroup$ Ack, I posted an improvement that's similar and then saw this. I'll upvote and maybe leave the comment also. $\endgroup$ – Daniel Lichtblau Nov 25 '14 at 20:02
  • $\begingroup$ That OK! I suspect there is still room for a FixedPoint solution... $\endgroup$ – Aisamu Nov 25 '14 at 20:26
  • $\begingroup$ One variant is to use Quiet and drop the last four or so list elements. But it still isn't the same as the "shift by factor of 10 and redivide" regimen which I guess is what was wanted. $\endgroup$ – Daniel Lichtblau Nov 25 '14 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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