2
$\begingroup$

I was thinking about possible new algorithms for Egyptian fractions expansion. We know that for any $p,q,m>0$:

$$\frac{p}{q}>\frac{p}{q+m}$$

Here we assume $p<q$ and are coprime.

Now it would make sense to find the smallest $m$ such that:

$$\mod(q+m,p)=0$$

Then we represent the initial fraction as:

$$\frac{p}{q}=\frac{p}{q+m}+\frac{pm}{q(q+m)}$$

Getting everything in lowest terms we obtain:

$$\frac{p_0}{q_0}=\frac{1}{a_0}+\frac{p_1}{q_1}$$

Here $a_0=(q_0+m_0)/p_0$ (an integer) and we repeat the process for $p_1$ and $q_1$.


Experimenting with Mathematica (and pen and paper of course) I noticed a very curious fact - this algorithm gives the exact same expansions as the greedy algorithm! But why? And if it's true, how do we prove it?

Here is the Mathematica code I used. To speed up the process for large denominators and numerators I numerically check FractionalPart instead of using Mod, so far there were no errors related to this approximation.

x=18/23;
p0=Numerator[x];
q0=Denominator[x];
S=0;
While[p0>1&&q0<10^21,
M=Catch[Do[If[FractionalPart[(q0+k)/p0]<10^(-35),Throw[k]],{k,1,q0}]];
p1=Numerator[M p0/(q0(q0+M))];
q1=Denominator[M p0/(q0(q0+M))];
S+=p0/(q0+M);
Print[StandardForm[p0/(q0+M)],"                  ",StandardForm[M p0/(q0(q0+M))],"                  ",M];
p0=p1;
q0=q1]
If[p0==1,S+=p0/q0];
N[(x-S)/x,10]
$\endgroup$
1
$\begingroup$

It is the greedy algorithm. If

$$k-1 < \frac{q}{p} \leqslant k,$$

then $(k-1)p < q \leqslant kp$, and the smallest $m$ such that $q+m \equiv 0 \pmod{p}$ is $kp - q$, thus

$$\frac{p}{q+m} = \frac{p}{kp} = \frac{1}{k}$$

where

$$k = \biggl\lceil\frac{q}{p}\biggr\rceil.$$

$\endgroup$
1
  • $\begingroup$ Oh, thanks. Initially I tried another algorithm $\frac{p}{q} \to \frac{p-m}{q-m}$, it's different from greedy, and doesn't work very well. That's why I moved on to this one $\endgroup$ – Yuriy S Feb 4 '17 at 20:48

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.