Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Recursive algorithm

• To: mathgroup at smc.vnet.net
• Subject: [mg97835] Recursive algorithm
• From: athanase <aeoost at gmail.com>
• Date: Mon, 23 Mar 2009 04:03:36 -0500 (EST)

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 smaller
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:

• Follow-Ups:
  • Re: Recursive algorithm
    • From: Daniel Lichtblau <danl@wolfram.com>