Re: Recursive algorithm

*To*: mathgroup at smc.vnet.net*Subject*: [mg97849] Re: Recursive algorithm*From*: Raffy <raffy at mac.com>*Date*: Tue, 24 Mar 2009 05:27:57 -0500 (EST)*References*: <gq7j94$qeg$1@smc.vnet.net>

On Mar 23, 2:03 am, athanase <aeo... at gmail.com> wrote: > hello all, > > i am having headaches trying to produce this recursive > algorithm in mathematica: > > the algorithm devides a reduced fraction r where r > 1 into n steps > in the form (k+1)/k > > 1) try the largest step (k+1)/k (say s) that will fit in r; > 2) find out how to divide r/s into n-1 steps; > 3) try the next biggest step, etc; > 4) until the first step is small enough that n of them are sma= ller > than r, then you are done. > > so for r=8 and n=3 > > the result is > > (2/1,2/1,2/1) > > and for r=7/5, n=2 > > the result is > > (4/3,21/20),(6/5,7/6) > > i have found this algorithm written in another system but attempt to > translate it fails for n>2 > > below is the code; > > sincere thanks for considering this problem, > > athanase > > spsubdiv := proc(r:rational,n:integer) > local i,j,l,s; > if n=1 > then > if numer(r)=denom(r)+1 > then [r] > else ( NULL ) > fi; > else > s := NULL; > for i from floor(1/(r-1))+1 while (1+1/i)^n >= r do > l := [spsubdiv( r/(1+1/i), n-1 )]; > for j to nops(l) do > if op(1,op(j,l)) <= (1+1/i) > then s := s, [(1+1/i),op(op(j,l))]; > fi > od; > od; > s; > fi; > end: I never wrote such code before but I believe this works: athanase[r_, n_Integer] := Join @@ Last@Reap@athanaseAux[n, r]; athanaseAux[1, r_, a___] := If[Numerator[r] == Denominator[r] + 1, So= w [{a, r}]]; athanaseAux[n_Integer, r_, a___] := Block[{i = Floor[1/(r - 1)], s}, While[s = 1 + 1/++i; s^n >= r, athanaseAux[n - 1, r/s, a, s]]]; You could add some conditions on athanase[...] to ensure r > 1 and n > 0. Given Examples: athanase[8, 3] => {{2, 2, 2}} athanase[7/5, 2] => {{4/3, 21/20}, {6/5, 7/6}} Generic Test: SameQ @@ Times @@@ athanase[9/7, 3]