Ampliación enteros en distintas fracciones egipcias - ¿cuál es la forma óptima?

Question

Sabemos que hay infinidad de formas para representar a $1$ como una suma de las distintas fracciones de unidades (es decir, fracciones egipcias). La más óptima (que es el que menos demoninators y el menor número de fracciones) es:

$$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$$

But how to represent other integers in the same way? The rules are as follows: we can't use $1$ as a denominator and no repetitions are allowed.

So far I found a way, which is surely not optimal: for any integer $un$ we find the closest harmonic number such that $H_n-1<a$. Then we expand the difference by the greedy algorithm. It seems to work so far, but gives horrible fractions:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{15}+\frac{1}{230}+\frac{1}{57960}$$

$$3=\sum _{n=2}^{30} \frac{1}{n}+\frac{1}{200}+\frac{1}{77706}+\frac{1}{16532869712}+\frac{1}{3230579689970657935732}+ \\ +\frac{1}{36802906522516375115639735990520502954652700}$$

For $4$ there is no space here to write the monstrous denominators. However, it definitely consists of $98$ fractions ($81$ of them represent $H_{82}-1$), and the largest denominator contains $142549$ los dígitos.

Lo que es más óptimo formas de ampliar los números enteros en fracciones egipcias?

No existe "la mejor manera", como Martin R notado, ya que se puede optimizar el número de fracciones o los denominadores. Estoy buscando algo mejor que mi actual manera, al menos.

Siempre es posible ampliar cualquier entero de esta manera?

Sé que el algoritmo voraz que termina por cualquier número racional. Y el más pequeño denominador de la diferencia entre el $a$ $H_n-1$ es mayor que $n$ (si elegimos $n$ más grande posible, de modo que la diferencia es positiva), así que creo que la respuesta es sí. Pero no estoy seguro de si este es lo suficientemente riguroso.

---

Vea este enlace que utiliza el mismo método y proporciona el mismo ejemplo para $3$. La acaba de encontrar.

---

Actualización

El uso de @DavidP del consejo y de la identidad para deshacerse de la repetición de fracciones:

$$\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$$

I managed to get another expansion for $2$ with more fractions, but smaller maximum denominator:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{12}+\frac{1}{13}+\frac{1}{18}+ \\ +\frac{1}{19}+\frac{1}{36}+\frac{1}{42}+\frac{1}{43}+\frac{1}{56}+\frac{1}{156}+\frac{1}{342}+\frac{1}{1806}$$

So at least I know there is more than one way.

---

An interesting parameter for optimization seems to be the product of all the denominators, which grows with the size of each individual denominator and with the number of fractions.

Comparing the provided expansions for $2$ we find that the first one is by far the most optimal.

---

Update 2:

For unit fractions with composite denominators we can create infinitely many 'splitting' formulas, using the following trivial identities:

$$1=\frac{a}{a+b}+\frac{b}{a+b} \\ \frac{1}{ab}=\frac{1}{a(a+b)}+\frac{1}{b(a+b)}$$

The famous identity above comes when $b=1$. This can be continued $m$ times to obtain $2^m$ fractions.

Another case:

$$1=\frac{a}{a+b+c}+\frac{b}{a+b+c}+\frac{c}{a+b+c} \\ \frac{1}{abc}=\frac{1}{ab(a+b+c)}+\frac{1}{bc(a+b+c)}+\frac{1}{ac(a+b+c)}$$

This can also be continued. If $b=c$, we obtain a $3$ term splitting for $1/ab$:

$$\frac{1}{ab}=\frac{1}{ab(a+b+1)}+\frac{1}{b(a+b+1)}+\frac{1}{a(a+b+1)}$$

And so on, for a larger number of terms.

Some examples:

$$\frac{1}{6}=\frac{1}{10}+\frac{1}{15}$$

$$\frac{1}{12}=\frac{1}{21}+\frac{1}{28}=\frac{1}{16}+\frac{1}{48}$$

And a neat example:

$$\frac{1}{2}=\frac{10}{20}=\frac{10}{40}+\frac{10}{50}+\frac{10}{200}=\frac{1}{4}+\frac{1}{5}+\frac{1}{20}$$

---

In any case, I've obtained yet another expansion for $2$, but now with very small denominators:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{9}+\frac{1}{10}+\frac{1}{15}+\frac{1}{18}+\frac{1}{20}+\frac{1}{21}+ \\ +\frac{1}{27}+\frac{1}{30}+\frac{1}{54}+\frac{1}{63}+\frac{1}{70}$$

And yet another, with even smaller denominators and shorter:

$$2=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{12}+\frac{1}{14}+\frac{1}{18}+\frac{1}{24}+\\+\frac{1}{27}+\frac{1}{28}+\frac{1}{36}+\frac{1}{54}$$

For this I used another identity for even denominators:

$$\frac{1}{2a}=\frac{1}{2a(2a+3)}+\frac{1}{a(2a+3)}+\frac{1}{2a+3}$$

---

Actualización 3:

Decidí que tiene más sentido para optimizar el tamaño del denominador, después de todo. Porque en cualquier caso particular, el número de fracciones está restringido por el tamaño de la mayor denominador.

Aquí está el mejor resultado fue capaz de llegar para $3$ (la secuencia de los denominadores es de siempre):

$$\{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,22,23,24,27,28,32,36, \\ 38,44,52,54,56,63,72,76,80,88,91,120,231,608,759,1518\}$$

See also an awesome sequence of denominators for $5$ proporcionado por Greg Martin en los comentarios de Jack D'Aurizio la respuesta:

{2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26,27,28,29,30,31,32,33,34,35,36,38,39,40,41,42,43,44,45,46,48,49,50,51,52,53,54,55,56,57,58,60,62,63,64,66,67,68,69,70,72,73,75,76,78,80,81,82,83,84,87,90,91,92,93,94,95,96,97,98,99,104,105,108,110,112,115,116,117,119,120,121,123,126,127,128,129,130,131,132,134,136,137,140,141,143,144,145,146,147,148,150,152,153,154,156,159,160,161,162,165,166,168,169,170,171,174,176,177,178,180,182,183,185,187,190,192,195,196,198,200,201,204,205,206,207,208,209,210,212,213,215,217,220,221,222,224,225,228,230,231,232,234,235,238,240,242,244,245,246,247,249,252,253,254,255,258,260,261,264,266,268,270,272,273,274,275,276,279,280,282,285,286,287,288,290,292,294,295,297,299,300,301,304,306,308,309,310,312,315,318,319,320,322,323,324,325,329,330,336,338,340,341,342,345,348,350,351,352,354,355,356,357,360,363,364,365,368,371,372,374,377,378,380,384,385,388,390,391,396,399,400,402,403,405,406,408,411,412,413,414,416,418,420,425,427,429,432,434,435,437,438,440,442,448,450,455,456,459,460,462,464,465,468,469,475,476,480,483,484,485,493,494,495,496,497,504,506,508,510,511,513,520,522,524,525,527,528,532,534,535,540,544,546,548,550,551,552,558,560,561,567,570,572,575,576,580,581,582,585,589,594,595,598,600,605,608,609,612,616,620,621,623,624,627,630,635,638,640,642,644,646,648,650,651,660,663,665,667,672,675,676,680,682,684,685,690,693,696,700,702,704,713,714,715,720,721,725,726,728,736,741,744,748,749,754,756,759,760,762,765,770,775,780,782,783,786,792,798,800,805,806,810,812,816,819,825,828,832,836,837,840,845,847,850,855,858,864,868,870,874,880,884,891,896,897,899,900,910,912,917,918,920,924,928,930,935,936,945,950,952,957,960,966,969,975,986,988,990,992}

Answer 1

Hay muchos algoritmos de descomposición de algunos $\frac{p}{q}\in\mathbb{Q}^+$ $$ \frac{p}{q}=\sum_{a\in A\subset\mathbb{Z}^+}\frac{1}{a}$$ por ejemplo, el algoritmo voraz, pero la respuesta a tu pregunta depende fuertemente de lo que significa óptimo. Si lo que quieres decir con el menor número de términos, la pregunta no es trivial en absoluto: de hecho, es un problema abierto. De todos modos lo que no es difícil de demostrar por inducción que el algoritmo voraz o el algoritmo basado en la identidad de $\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$ se detiene en algún punto de $\frac{p}{q}\in\mathbb{Q}^+$.

Aquí es una representación de la $2$ me encontré por la combinación de los dos enfoques: $$ 2 = \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{10}+\frac{1}{12}+\frac{1}{15}+\frac{1}{40}+\frac{1}{140}$$ Ha $12$ términos, $A=\{2,3,4,5,6,7,8,10,12,15,40,140\}$ $\prod_{a\in A}a\approx 4\cdot 10^{11}.$

Otra representación con doce términos está dado por $A=\{2,3,4,5,6,7,8,9,10,15,230,57960\}$$\prod_{a\in A}a\approx 7.2\cdot10^{14}$.

Sin embargo, el otro está dado por $A=\{2,3,4,5,6,7,8,9,12,14,63,2520\}$$\prod_{a\in A}a\approx 10^{13}$.

Después de una larga búsqueda, encontré también una representación de $3$ sólo con $33$ términos, dado por $A=[2,18]\cup[20,28]\cup\{30,32,33,34,864,199836,7813587600\}$.