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]