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]

```

• Prev by Date: Re: Incompatible units?
• Next by Date: Re: Commutators with boson operators
• Previous by thread: Re: Re: Recursive algorithm
• Next by thread: solving nonlinear simultaneous equations