Recordamos que una fracción egipcia unitaria es aquella de
numerador igual a la unidad. Una fracción egipcia en general es una suma de
varias fracciones egipcias unitarias.
Puedes consultar
Lo que nos interesa en esta entrada es encontrar sumas o
diferencias de dos fracciones de este tipo unitarias, cuyo resultado también
sea unitario. En concreto, deseamos encontrar tres valores enteros positivos a,
b y c tales que
Simultáneamente estudiaremos su correspondiente expresión
como diferencia:
Un ejemplo clásico es 1/2=1/3+1/6, o bien 1/3 = 1/2 - 1/6
Existe una solución trivial para cada valor de a y es que
Para evitar esa solución supondremos que b>c en
(podría ser a la inversa,
pero llamamos b al mayor de los dos).
Es evidente que 1/a es mayor que 1/b y 1/c, luego a<b y
a<c. Como hemos supuesto que b es el mayor, tendremos la doble desigualdad a<c<b.
Búsqueda mediante un algoritmo
Siguiendo nuestra metodología habitual, buscaremos
soluciones en primer lugar y después las analizaremos. Si deseamos encontrarlas
fácilmente, será bueno darle protagonismo a b, para que los valores de a
y de c sean menores que él y se
pueda acudir a un doble bucle, en el que c
recorra (en principio) desde 2 hasta b-1 y a desde 1 hasta b-2. Por tanto b>2.
Nos dedicaremos a la diferencia de fracciones, que sabemos que es equivalente a
la cuestión de la suma.
Función sumaegipcias(b)
Hemos comenzado la búsqueda mediante la siguiente función
que devuelve, para cada b, los
valores posibles de a y c. Al ser varias las posibles
soluciones, se devolverán en modo texto, para tener una visión global de todas
ellas. La función que se presenta más abajo usa el hecho de que el valor de b despejado en la condición general es a*c/(c-a).
Su listado es el siguiente:
Public Function sumaegipcias$(b)
Dim a, c, d
Dim s$
s$ = "" ‘Recibirá las
soluciones en modo texto
If b < 3 Then sumaegipcias =
"NO": Exit Function
For c = 2 To b – 1 ‘Bucles de
búsqueda
For a = 1 To c - 1
d = a * c / (c - a) ‘Fracción que ha
de ser entera
If d = Int(d) Then If d = b Then s$ = s$ +
"1/" + Str$(a) + "-" + "1/" + Str$(c) +
" "
‘Si es entera y coincide con b, se recoge en s$
Next a
Next c
If s$ = "" Then s$ =
"NO" ‘Si la cadena está vacía, es que no hay solución
sumaegipcias = s$
End Function
Aplicada esta función a un conjunto de números, por ejemplo
desde el 6 hasta el 15, observamos que no todos admiten esta descomposición:
Sólo la cumplen 6, 12 y 15. El 12 por partida doble. Puedes
verificar estas igualdades (escritas como diferencias, pero podrían ser sumas):
1/6=1/2-1/3, 1/12=1/3-1/4, 1/12=1/4-1/6, 1/15=1/6-1/10
Aquí tienes los valores de b entre 1 y 100 que admiten la descomposición pedida:
6, 12, 15, 18, 20, 24, 28, 30, 35, 36, 40, 42, 45, 48, 54,
56, 60, 63, 66, 70, 72, 75, 77, 78, 80, 84, 88, 90, 91, 96, 99, 100
Estos valores te pueden dar alguna pista. Reflexionamos
sobre ellos:
Escribamos c-a=k,
con lo que el cociente b=a*c/(c-a) se convierte en b=(a+k)*a/k. Así lo analizamos mejor.
El denominador b no puede ser primo
En efecto: Al ser entero (a+k)*a/k puede ocurrir:
Si k divide a a: entonces k1=a/k y b=k1(a+k). b tendría al menos dos factores (si k=a nos encontraríamos con la
solución trivial de más arriba, en la que b=2a y que no consideramos)
Si k no divide a a: Llamemos d=MCD(a,k). Ese valor d no
puede ser 1, pues entonces k sería
primo con a, pero como tiene que
dividir a a+k, dividiría a (a+k)-k=a, lo
que llevaría a una contradicción.
Si d>1, se podría simplificar b=(a+k)*a/k entre d,
resultando los cocientes a’=a/d y k’=k/d: b=(a+k)*a/k=(a+k)*a’/k’, en el que k’
es primo con a’, luego, por el teorema de Euclides, k’ ha de dividir a (a+k),
luego divide a la diferencia a+k-k=a. Así que k’ es un divisor de a. De esa
forma b=a’*p, siendo a’>1 (ver el párrafo anterior) y p=(a+k)/k’>1, luego
no puede ser b primo.
La diferencia c-a=k es menor que a
De la igualdad b=(a+k)*a/k
deducimos b*k=(a+k)*a=c*a, pero sabemos que b>a y b>c, luego la igualdad
solo es posible si k<a<c.
Este largo razonamiento nos ha descubierto que, o bien k divide a a, como es el caso en
1/12=1/4-1/6, en el que k=6-4=2 y divide a 4,
o bien unos factores
de k dividen a a y otros a a+k, ambos mayores que 1. Sería el
caso
1/15=1/6-1/10, en el que k=10-6=4=2*2 y 2 divide a 6 y “el
otro” 2 al 10, resultando b=6*10/4=15.
Más adelante daremos una caracterización de estos números.
Otro
algoritmo
Esta sección la puedes dejar si no te interesa demasiado la
construcción de algoritmos.
Otro planteamiento parte de que según lo anterior, b*k=c(c+k), hay que
buscar un número tal que si lo
multiplico por k, se pueda descomponer en dos factores con diferencia k. Por
ejemplo, 12 multiplicado por 2 da 24 que tiene dos factores, 4*6 diferenciados
en 2.
El valor de c sería una solución de la ecuación c2+kc-bk=0,
es decir:
De esa forma
el valor de c no se obtiene por búsqueda, sino por cálculo. Lo implementamos
como otra función
Public Function sumaegipcias2$(b)
Dim k, c
Dim s$
s$ = ""
If b < 3 Then sumaegipcias2 =
"NO": Exit Function
For k = 1 To b - 1
c = (-k + Sqr(k ^ 2 + 4 * b * k)) / 2 ‘Calculamos
el valor de c
If c = Int(c) And c + k < b Then s$ = s$
+ "1/" + Str$(c) + "-" + "1/" + Str$(c + k) +
" "
Next k
If s$ = "" Then s$ =
"NO"
sumaegipcias2 = s$
End Function
Comprobamos que son equivalentes:
Es más rápida de proceso que la anterior.
Otra
definición de los números encontrados
El listado de los valores de b está publicado, pero con otra definición distinta
Numbers having
divisors d,e with d < e < 2d.
6, 12, 15, 18, 20, 24,
28, 30, 35, 36, 40, 42, 45, 48, 54, 56, 60, 63, 66, 70, 72, 75, 77, 78, 80, 84,
88, 90, 91, 96, 99, 100, 102, 104, 105, 108, 110, 112, 114, 117, 120, 126, 130,
132, 135, 138, 140, 143, 144, 150, 153, 154, 156, 160, 162, 165, 168, 170, 174,
175, 176
Según esto, las soluciones para nuestras diferencias de
fracciones egipcias coinciden con aquellos números que poseen dos divisores a y
b, en los que a<b<2a, es decir, que uno de ellos está comprendido entre
el otro divisor y su doble. Si repasas el listado anterior, todos lo cumplen, e
incluso algunos de ellos son producto de dos divisores de este tipo:
6=2*3, 35=5*7, 42=6*7, …
Entre ellos figuran los números oblongos, 6, 12, 20, 30,
42,…del tipo n(n+1), como puedes comprobar.
Demostramos esta equivalencia:
El contrarrecíproco es fácil de razonar. Si no existen estos
pares de divisores, a<b<2a, cualquier expresión que construyamos similar
a b=(a+k)*a/k, no podría garantizar
que k es menor que a, como demostramos más arriba que era necesario.
Al revés, parto de que existen dos divisores de un número N tales
que a<b<2a
Podemos suponer que son primos entre sí, pues, en caso
contrario, dividimos entre su M.C.D. y seguirán siendo divisores y cumpliendo
a<b<2a. Si son primos entre sí, su producto, que sería el M.C.M, no puede
ser mayor que N (en ese caso el M.C.M. sería N). Así que a*b<=N.
Para mayor claridad, distinguimos dos casos:
N=a*b
Entonces bastará multiplicar ambos por k=b-a, con lo que
tendremos N=a*b=a(a+k)=ak(ak+kk)/k^2, pero k^2 es la nueva diferencia, luego N
tiene la forma deseada de a1(a1+k1)/k1
Por ejemplo, 77=7*11 multiplicamos por 4 y queda
1/77=1/28-1/44=(44-28)/(77*16)=16/(77*16)=1/77, y 1/77=1/28-1/44
70=10*7, diferencia 3, multiplico: 70=30*21/9, luego
1/70=1/21-1/30
N=m*a*b
En este caso el producto de a*b no iguala a N, En ese caso
multiplicamos a y b por mk,
resultando:
N=mamk(amk+mkk)/mkmk y mkk es la nueva diferencia.
Simplificando N=amk(amk+mkk)/mkk, que es del tipo pedido:
Ejemplo: 66 contiene al 2 y al 3, con 2<3<2*2 y se
cumple 66=11*2*3.
Multiplicamos ambos por su diferencia 1 y por m=11,
resultando 22 y 33 y queda
66=22(22+11)/11, es decir
1/66=1/22-1/33
84=2*6*7, con 6<7<2*6. El M.C.D(6,7)=1, k=1, m=2, luego
multiplicamos por 2*1=2, y queda 12 y 14:
84=12*14/2, luego 1/84=1/12-1/14
También podíamos haber usado 4 y 7, con 4<7<2*4, k=3,
m=3, 84=3*4*7, y multiplicamos ambos por 3*3=9, lo que nos llevaría a
1/84=1/36-1/63.
Hemos descubierto esta equivalencia bastante interesante,
pues caracteriza cuándo un valor puede ser denominador en una diferencia de
fracciones egipcias.
No hay comentarios:
Publicar un comentario