Números de Saint-Exupéry

Reciben este nombre en la página OEIS (http://oeis.org) aquellos números que coinciden con el producto de los tres lados de una terna pitagórica. El primero, como era de esperar, es 60, que es el producto de 3, 4 y 5, elementos de la terna más sencilla que conocemos. El segundo, 480, es el producto de sus dobles, 6*8*10. Siguen infinitos de este tipo (porque también es infinito el número de ternas), y nuestro objetivo en esta entrada es analizar métodos para encontrarlos.

La idea sencilla es ir construyendo ternas y después tomar nota del producto de sus lados. El inconveniente reside en que así no podemos averiguar si un número cualquiera es de este tipo o no. Si nos preguntan si lo es 238772, no vamos a formar todas las ternas hasta llegar a él. Por eso, como en otras ocasiones, recurriremos a una función que nos responda a esa pregunta.

Algoritmo con fuerza bruta

Esta es la aproximación a un problema con la solemos comenzar en este blog. Fingimos no saber nada de la cuestión y emprendemos una búsqueda sin apoyarnos en ninguna propiedad. Usaremos la siguiente función:

Public Function Saint_Exupery(n)

Dim a, b, c, p, r

Dim s$

a = 3: b = 4: c = 5: p = 60 ‘Iniciamos valores con la terna (3, 4, 5)

s = "" ‘Recogerá soluciones

r = Sqr(n) ‘Tope de búsquedas

While a <= r And s = ""

b = a + 1 ‘Segundo cateto

p = a * b * c ‘Posible número de Saint_Exupery

While b <= r And s = ""

c = n / a / b ‘Tercer cateto

If a ^ 2 + b ^ 2 = c ^ 2 Then s = Str$(a) + Str$(b) + Str$(c) ‘Es terna pitagórica y se publica

b = b + 1

Wend

a = a + 1

Wend

Saint_Exupery = s

End Function

Con esta función podemos responder a la pregunta de si 238772 es del tipo buscado, y la respuesta es que no, porque devuelve una cadena vacía. Más adelante veremos una razón más sencilla, y es que no es múltiplo de 60.

También con ella podemos encontrar los primeros números de Saint_Exupery:

En la tabla siguiente, cada número viene acompañado de la terna de la que es producto:

 

Indirectamente, esta es una forma de ordenar ternas por el producto de sus lados.

No es este un algoritmo rápido. Para llegar a estos resultados se han necesitado 1m y 20s. Pronto veremos una simplificación.

Estos números ya están publicados en OEIS, de donde hemos obtenido su definición:

A057096                            Saint-Exupéry numbers: ordered products of the three sides of Pythagorean triangles.

60, 480, 780, 1620, 2040, 3840, 4200, 6240, 7500, 12180, 12960, 14760, 15540, 16320, 20580, 21060, 30720, 33600, 40260, 43740, 49920, 55080, 60000, 65520, 66780, 79860, 92820, 97440, 97500, 103680, 113400, 118080, 120120, 124320, 130560, 131820, 164640

(http://oeis.org/A057096)

Segundo algoritmo

En el algoritmo de fuerza bruta hemos obviado el hecho de que los lados de la terna han de ser divisores del número de Saint-Exupéry buscado. Si tenemos esto en cuenta, la búsqueda se simplifica bastante. Podemos intentar esta variante:

Public Function Saint2(n)

Dim a, b, c

Dim s$

a = 5

s = ""

While a <= n / 2 And s = ""

If n / a = n \ a Then ‘Exigimos que el primer lado sea divisor de n

b = a – 1 ‘Buscamos el siguiente divisor, más pequeño que a

While b > 1 And s = ""

If n / b = n \ b Then

c = n / a / b ‘El tercer divisor se calcula directamente

If a ^ 2 = b ^ 2 + c ^ 2 Then s = Str$(a) + Str$(b) + Str$(c)

End If

b = b - 1

Wend

End If

a = a + 1

Wend

Saint2 = s

End Function

Esta versión constituye una mejora en rapidez, porque tarda 54 segundos en reproducir la misma tabla de arriba.

Tercera versión

A propósito, para que se vea la utilidad de un apoyo teórico, hemos ignorado una propiedad muy popular de las ternas, y es que en cualquiera de ellas hay un múltiplo de 3, uno de 4 y uno de 5, que pueden coincidir o no en un mismo término. Por tanto, el producto de los tres lados será múltiplo de 60. Esto facilita mucho las cosas, porque se puede insertar un condicional del tipo n/60=n\60 o n MOD 60=0, con lo que solo se analizarán los múltiplos de 60.

Con esta mejora, nuestro equipo, con bastantes años sobre él, solo tarda 13 segundos.

Ahora ha llegado el momento de traducir este algoritmo al lenguaje PARI:

saint(n)=my(a=5,b,c,m=0);if(n%60==0,while(a<=n/2&&m==0,if(n%a==0,b=a-1;while(b>=1&&m==0,if(n%b==0,c=n/a/b;if(c<a&&a^2==b^2+c^2,m=1));b-=1));a+=1));m}

for(i=60,60000,if(saint(i),write1("final.txt",i,", "))

No se gana mucha rapidez con él, porque PARI no es muy eficiente cuando se manejan bucles anidados. La ventaja que presenta es que llega fácilmente a números grandes. El listado siguiente llega hasta 60000:

60, 480, 780, 1620, 2040, 3840, 4200, 6240, 7500, 12180, 12960, 14760, 15540, 16320, 20580, 21060, 30720, 33600, 40260, 43740, 49920, 55080, 60000,…

Dos cuestiones

En las búsquedas que hemos emprendido no hemos encontrado un número que sea producto de lados  de dos ternas distintas. Parece ser que su existencia es una cuestión abierta.

Nuestras funciones pueden resolver el llamado “Problema de Napoleón”, planteado por el mismo Saint-Exupéry. No vamos a desarrollar aquí ese problema. Puedes consultar

https://www.apmep.fr/IMG/pdf/Parallelepipede_Plane.pdf

En ese texto se llega a la solución 756, 825 y 1119. Si aplicamos nuestra función saint2 al número 697920300 (ver texto recomendado), nos devuelve al momento esa solución:

(Ver también https://www.antoinedesaintexupery.com/personne/le-probleme-du-pharaon/)