エジプト式分数表示

エジプト式分数表示

任意の正の真分数はエジプト式分数で表せる。

(0)貪欲法

ある正の分数を\(\frac{y}{x}\)として、

\[ \sum_{k=2}^{n}\frac{1}{k}\leq\frac{x}{y} \]

を満たす最大の\(n\)を求め、

\[ \frac{x}{y}=\sum_{k=2}^{n}\frac{1}{k}+\left(\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\right) \]

として、第1項の\(\sum_{k=2}^{n}\frac{1}{k}\)を求めるエジプト式分数に加え、第2項の\(\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\)を\(\frac{a}{b}\)とおいてこれをエジプト式分数で表す。
また、このとき、最大の\(n\)を求めたので、

\[ \frac{x}{y}<\sum_{k=2}^{n+1}\frac{1}{k} \]

となり、

\begin{align*} \frac{a}{b} & =\frac{x}{y}-\sum_{k=2}^{n}\frac{1}{k}\\ & <\frac{1}{n+1} \end{align*}

となる。

天井関数と剰余の関係

\[ \alpha=\beta\left\lceil \frac{\alpha}{\beta}\right\rceil +\mod\left(\alpha,-\beta\right) \]

より、\(\frac{a}{b}\)は真分数なので、

\begin{align*} \frac{a}{b} & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }-\frac{\mod\left(b,-a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{\mod\left(-b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{a\left|\sgn\mod\left(b,a\right)\right|-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\\ & =\frac{1}{\left\lceil \frac{b}{a}\right\rceil }+\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil } \end{align*}

となる。
第1項をエジプト式分数に加え、第2項は真分数になるので\(\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil }\)をもう一度\(\frac{a}{b}\)とおいてこれを0になるまで繰り返せばいい。
これは

\[ \frac{1}{m}<\frac{a}{b} \]

となる最小の\(m\)を求めているのと同じであり\(m=\frac{1}{\left\lceil \frac{b}{a}\right\rceil }\)となる。
\(\frac{a}{b}\)は真分数なので

\[ \frac{1}{\left\lceil \frac{b}{a}\right\rceil }>\frac{a-\mod\left(b,a\right)}{b\left\lceil \frac{b}{a}\right\rceil } \]

となり、単位分数\(\boldsymbol{\frac{1}{\left\lceil \frac{b}{a}\right\rceil }}\)が再度加わることはないので重複はない。
また

\begin{align*} \frac{1}{\left\lceil \frac{b}{a}\right\rceil } & <\frac{1}{\frac{b}{a}}\\ & =\frac{a}{b}\\ & <\frac{1}{n+1} \end{align*}

より、先に求めたエジプト式分数の単位分数と重複するとこはない。
また分子だけを考えると、\(a\rightarrow a-\mod\left(b,a\right)\)となり負にはならずに小さくなっていき、いずれ0になるので有限個の単位分数で表せる。

(0)-2

ある正の分数を\(\frac{a}{b}\)とする。

\(a=1\)のとき、

\begin{align*} \frac{1}{b} & =\frac{b+1}{b\left(b+1\right)}\\ & =\frac{1}{b+1}+\frac{1}{b\left(b+1\right)} \end{align*}

となるので、\(2\leq b\)のときエジプト式分数で表せる。

\(b=1\)のときは\(\frac{1}{2}\)が重複してしまうので、もう一度適用して、

\begin{align*} 1 & =\frac{1}{2}+\frac{1}{2}\\ & =\frac{1}{2}+\frac{1}{2+1}+\frac{1}{2\left(2+1\right)}\\ & =\frac{1}{2}+\frac{1}{3}+\frac{1}{6} \end{align*}

とすればいい。
これを繰り返し使えば任意\(m\)以降の単位分数で表すことが出来る。
すなわち、

\[ \frac{1}{b}=\frac{1}{m}+\cdots \]

とできる。

\(a=k\)のときエジプト式分数で表せると仮定すると、\(a=k+1\)のとき、

\[ \frac{k+1}{b}=\frac{k}{b}+\frac{1}{b} \]

となるが、\(\frac{k}{b}\)は仮定よりエジプト式分数で表され、有限個の単位分数の和なので、\(\frac{1}{b}\)を重複しないようにそれ以降のエジプト式分数で表せばいい。
これより、\(\frac{k+1}{b}\)はエジプト式分数で表せるので、数学的帰納法より任意の正の分数はエジプト式分数で表せる。

\(\frac{5}{121}\)を貪欲法によりエジプト式分数で表すと、

\begin{align*} \frac{5}{121} & =\frac{1}{\left\lceil \frac{121}{5}\right\rceil }+\frac{5-\mod\left(121,5\right)}{121\left\lceil \frac{121}{5}\right\rceil }\\ & =\frac{1}{25}+\frac{4}{3025}\\ & =\frac{1}{25}+\frac{1}{\left\lceil \frac{3025}{4}\right\rceil }+\frac{4-\mod\left(3025,4\right)}{3025\left\lceil \frac{3025}{4}\right\rceil }\\ & =\frac{1}{25}+\frac{1}{757}+\frac{3}{2289925}\\ & =\frac{1}{25}+\frac{1}{757}+\frac{1}{\left\lceil \frac{2289925}{3}\right\rceil }+\frac{3-\mod\left(2289925,3\right)}{2289925\left\lceil \frac{2289925}{3}\right\rceil }\\ & =\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{2}{1747920361825}\\ & =\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{\left\lceil \frac{1747920361825}{2}\right\rceil }+\frac{2-\mod\left(1747920361825,2\right)}{1747920361825\left\lceil \frac{1747920361825}{2}\right\rceil }\\ & =\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225} \end{align*}

となるが、

\[ \frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363} \]

と、もっと簡単なエジプト式分数がある。

ページ情報

タイトル

エジプト式分数表示

URL

https://www.nomuramath.com/edr7z20e/

SNSボタン